Description
Q1. For a given language L = {anb2n | n ³ 0 is even}.
- [8] Give a CFG that accepts L.
- [6] Show the sequence of derivations for the acceptance of aaaabbbbbbbb by G in (1).
- [6] Draw a derivation tree for aaaabbbbbbbb.
Q2. Construct a CFG for the following languages where n, m, k ³ 0.
- [10] L1 = { anbn | n is a multiple of 3 }
- [10] L2= { anbmck | k = n+m }
- [10] L3 = { anbm | n = m –1 }
- [10, optional] L4 = { anbmck | n=m or m £ k }
Q3. Give the language L that is generated by the given grammar, in a formal expression.
S ® aaSbb | SS | l.
e.g.) L = { w ÃŽ {a, b}* | na(w) = 2nb(w) }
Q4. Find an s-grammar for L = {anb2n | n ³ 2}.
Q5. For a grammar G with the productions where G = ( {S, A, B}, {a, b}, S, P ) with productions
S ® AB | bbbB,          A ® b | Ab,     B ® a..
- Â Show that the grammar G is ambiguous.
- Â Give language L that is generated by G, L = L(G), in a formal expression (including a regular expression).
- Can you construct an unambiguous grammar that is equivalent to G? Otherwise, show that G is inherently ambiguous.
Q6. In the given grammar G, generate the simplified equivalent grammar by eliminating the following productions through (1) – (3).
G = ( {S, A, B, C}, {a, b}, S, P ) with productions
S ®bAA | bB,    A ® aA | aaC ,  B ® bbB | l,      C ® A
- Â Eliminate the l-productions
- Â Eliminate the Unit-productions from (1)
- Â Eliminate the useless productions (2), so that give the simplified equivalent grammar.
- Give the language L that is generated by this grammar, L = L(G), in a formal expression (including a regular expression).
Q7. Convert the given grammar into Chomsky Normal Form (CNF).
S ® AB | aB,     A ® abb | l ,     B ® bbA
Hint: Eliminate the l-productions and/or any unit-production prior to their conversion into CNF.
Q8. [10] Convert the given grammar into Greibach normal form.
S ® aSb | ab | bb