Grammar:

S -> 0 T 0

S -> 1 T 1

T -> 00

T -> 11

a) Draw the Table containing the right side of the Grammar Rules

0 1

--------------------

S |

T |

If the top of the stack is a non-terminal, replace it with the table entry

(based on the next char).

If the top of the stack is a terminal, match the stack and pop.

go to the next char.

Right now S is on the stack.

Each snap shot you draw will be made of the remaining string and the stack.

b) Parse the string 0 1 0 0 1 0 using the table.

Each time the stack changes, draw a new snap shot.

String: 0 1 0 0 1 0 $

Stack: $S

Write success or reject.

c) Parse the string 1 0 1 using the table.

Each time the stack changes, draw a new snap shot.

String: 1 0 1 $

Stack: $S

Write success or reject.