## Description

Q1. For a given language L = {*a*^{n}*b***^{2n}** |

*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*|^{n}b^{n}*n*is a multiple of*3*} - [10] L2= {
*a*|^{n}b^{m}c^{k}*k*=*n+m*} - [10] L3 = {
*a*|^{n}b^{m}*n =**m –*1 } - [10, optional] L4 = {
*a*|^{n}b^{m}c^{k}*n=m*or*m*£*k*}

Q3. Give the language L that is generated by the given grammar, in a formal expression.

S ®* aa*S*bb *| SS | l.

e.g.) L = { *w* Î {*a, b*}* | *n _{a}*(

*w*) = 2

*n*(

_{b}*w*) }

Q4. Find an s-grammar for L = {*a ^{n}b^{2n}* |

*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* | A*b*, 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 ®*b*AA | *b*B, A ® *a*A | *aaC* , B ® *bb*B | *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 | *a*B, A ® *abb* | *l* , B ® *bb*A

__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 ® *a*S*b* | *ab* | *bb*