HW 4 30 points

1. (5 pts)  Convert the grammar below to CNF.

G = (V,T,S,P) where
V={S,A,B,C,D}
T={0,1,2}

and P is given below.

SA|ABD|0BB
A0|BAA
BBB|1|2|
C    CD|0
DD1|DD


2. (10 pts) Consider the CNF grammar  G = (V,T,S,P) where

V = {S, A, B, C, D }, T = { a, b, c }, S = S and P is given below.
SAB|AD|AC
A  AA | a
B  BB | AB | b
C  AC | DC | c
D  DD | b | c

Use the CYK algorithm to determine if the strings w1 = babbc and w2 = aaaabb are in the language L(G).

Show the DP table. If the string is in L(G) construct the parse tree.

    3. (15 pts) Construct npda’s that accept the following languages on = {a, b }. Give both a verbal explanation on how your npda works and the formal definition including the transition function and/or transition graph. You must use JFLAP. Submit the transition graph in the HW pdf and the JFLAP code file for each problem.

        a) L = { anb2n : n   0 }

        b) L = { w : na(w) = 2nb(w) }

        c) L = { wcwR : w   {a,b}* }