QUIZ #2 SOLUTIONS

1.
        0       1
{a,b}S  {a,b}   {c,d}
{c,d}F  {e}     {c,d}
{e}     {a,b}   {a,b}

(for the make-up quiz :
        0       1
{a,b}S  {a,b}   {c,d}
{c,d}F  {e}     {c,d}
{e}     {a,b}   {a,b}
)

2.
a.)
In CNF form:

S -> DY or XC
X -> AX or a
Y -> BY or b
A -> a
B -> b
C -> DY
D -> d

b.)
In GNF Form:

S -> aXDY or aDY or dY
X -> aX or a
Y -> bY or b
D -> d

c.)
PDA:
start state (and only state) = q
start stack symbol = S
accept on empty stack

(q, a, S) = (q, XDY) 
(q, a, S) = (q, DY)
(q, d, S) = (q, Y)
(q, a, X) = (q, epsilon)
(q, a, X) = (q, X)
(q, b, Y) = (q, epsilon)
(q, b, Y) = (q, Y)
(q, d, D) = (q, epsilon)

3.
Use the CKY algorithm to decide a membership problem for CFG G

    S -> aYX 
    X -> aX | b
    Y -> Ya | b

To run the CKY algorithm, we need to convert the grammar into the Chomsky
normal form:

    S -> AZ
    X -> AX | b
    Y -> YA | b
    Z -> YX
    A -> a

The two CKY tables:

   a     b     a     a     b


   A     X,Y   A     A     X,Y
   X     Y     -     X
   -     Y     X
   -     Z
   S


   a     b     a     b     a

   A     X,Y   A     X,Y  
   X     Y     X     Y
   -     Z     -
   S     -
   -

Thus abaab is in the language L(G), whereas ababa is not.

Note: Without converting G into CNF, the CKY algorithm doesn't work. Some of
you managed to fill in CKY tables like the ones shown, without the Z
nonterminal. You could do this "by hand", not using the CKY, so it was not 
considered as using the CKY (partial credit awarded). 



5.
(a) Use the homomorphism h(a)=a, h(b)=b, h(c)=c and h(d)=e (epsilon) to
map the given language to the language consisting of strings of equal number
of a's , b's & c's. Since this language is not a CFL, the former cannot be a
CFL.
(in the make-up extended the homomorphism described above to h(e)=epsilon)

(b) CFL. The grammar is
	S->aSc | aBc
	B->bB | b

(c) Let L be the giving language.
	L intersect a+b+ = {a^n b^(n*n) | n > 0} which is given not to
  be a CFL. Hence L is not a CFL.
(in the make-up , first use the homomorphism which swaps "a" and "b" and
then use the above reasoning.)