Description
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.
SA|ABD|0BB
A0|BAA
BBB|1|2|
C CD|0
DD1|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.
SAB|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.
-
(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.
-
-
L = { anb2n : n 0 }
-
-
-
L = { w : na(w) = 2nb(w) }
-
-
-
L = { wcwR : w {a,b}* }
-