[SOLVED] CSCI435 Home Assignment 4

Q1. For a given language L = {aⁿb²ⁿ | 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 = { aⁿbⁿ | n is a multiple of 3 }
• [10] L2= { aⁿb^mc^k | k = n+m }
• [10] L3 = { aⁿb^m | n = m –1 }
• [10, optional] L4 = { aⁿb^mc^k | 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}* | n_a(w) = 2n_b(w) }

Q4. Find an s-grammar for L = {aⁿb²ⁿ | 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