A) Show a Computation with 1 1 2 2 (I Know I Wrote 1 2 2 1 on the Assignment)

Homework # 6

#1. Given M:

a)  Show a computation with 1 1 2 2 (I know I wrote 1 2 2 1 on the assignment)

[1, 1122, l] à [1, 122, X] à [1,22, XX ] à [2,2,X] à [2, l, l]

b)  Show a computation with 1 2 2 2

[1, 1222, l] à [1, 222, X] à [2,22, l] à

c)  What is L(M)?

It looks like {1n2 n | n > 0}

#2. Create a PDA to accept:

{w e {0,1}* | w has the same number of 0's as 1's}

With thanks to Matthew Hinds:

#3. Convert the expression grammar:

E à E + T | T

T à T * F | F

F à (E) | x

to a PDA. Show the grammar derivation of a + b*c and the PDA computation of a + b * c.

First, I'll convert to Greibach Normal Form (just by "eyeballing" the grammar from #4)

E à TE'

E' à e |+TE'

T à FT'

T' à e | *FT'

F à (E) |x

Becomes:

E à (ERT'E' |xT'E'

R à )

E' à e | + TE'

T à (ERT' | xT'

T' à e | *FT'

F à (ER |x

The pda then is (with q an initial state, p a final state):

d(q,(,e) = {[p,ERT'E']}

d(q,x, e) = {[p,T'E']}

d(p,), R) = {[p, e]}

d(p,e,E') = {[p, e]}

d(p,+,E') = {[p,TE']}

d(p,(,T) = {[p,ERT']}

d(p,x,T) = {[p,T']}

d(p,e,T') = {[p, e]}

d(p,*,T') = {[p, FT'}

d(p,(,F) = {[p,ER]}

d(p,x,F) = {[p, e]}

#4. Remove the direct left recursion from the expression grammar.

E à TE'

E' à e | +TE'

T à FT'

T' à e | *FT'

F à (E) |x

#5. Suppose X/Y = {w | wu e X for some u e Y}. Show that when X is context-free and Y is regular, X/Y is context-free (hint: start with a PDA for X and construct a PDA for X/Y)

This problem (and its solution) come from the text by Sipser. It will be interesting to see what you did with it!

We extend the PDA for X, MX, into one for X/Y by:

when MX finishes its input, it starts up in parallel the finite state machine for Y and

It can choose to stop if both the pda and the fsm are in a final state. Here are the details:

Consider the PDA MX for X & the fsm MY for Y,

We create a PDA MX/Y for X/Y as follows:

The states of MX/Y are the product of the states for MX and MY

Suppose p and q are states of MX and MY respectively, y a stack symbol of MX and a either in S or e.

Then MX might have a transition

d(p,a,y) = (p',action)

and MY might have a transition d(q,a) = q'

Then MX/Y would have a transition:

d ((p,q),e,y) = ((p',q'), action)

The accepting states of MX/Y are states (p,q) where p is an accepting state of MX and q is an accepting state of MY .

Create a copy MX' of MX/Y, but change it so that no states of MX' are accepting

and it starts in MY 's initial state. When the input is consumed, MX' transitions from

state p in MX to state (pq,q1) in MX/Y without altering the stack.

So if wx is in X with x in Y, there is an accepting sequence in MX on wx and an accepting sequence in MY on x.

So now by construction there is a sequence of transitions of MX' on w followed by a sequence of transitions of MX/Y on x that will cause MX/Y to accept. Similarly, given an accepting sequence of transitions on MX/Y on w, we can map these back to transitions on M and read off x such that wx is in X and x is in Y.