Q$1.$ Consider the following Grammars $.$ Identify the cause of ambiguity &

Simplify

Symbol of the

A$.$ P$1=\{$S $->$ ab $/$ bSa $/$ aSb$/$ A $/$ SS$\}$

B$.$ P$2=\{$S $->$ A$/$ bb$,$ A $->$ B$/$b$,$ B $->$ S$/$a$\}$

C$.$ S $->$ Aa$,$ S $->$ B$,$ B $->$ A$,$ B $->$ bb$,$ A $->$ a$,$ A $->$ bC$,$ A $->$ B

Q$2.$ Show that the following grammar is Ambiguous or not. If ambiguous,

identify the cause of ambiguity and simplify it

S $->$ AaB$/$ aaB; A $->$ D; B $->$ bbA $/\backslash$lambda ; D $->$ E; E $->$ F ; F $->$ aS

Q$3.$ Convert the following Grammar to CNF

E $->$ E $+$ T $/$ T ; T $->($E$)/$ a;

Q$4.$ Construction of the PDA for the language

L $=\{$ a $,$ subject to the following conditions

n

b

m

c

p

$/,$ m $,$ n$,$ p $>0\}$

I. n $=$ m $+$ p

II$.$ m $=$ n $+$ p

III. p $=$ n $+$ m

Q$5.$ Construct a PDA that accepts:

i$.$ Odd Palindrome

ii$.$ Even Palindrome

Q$6.$ Convert the following Grammar into Grammar into Greibach Normal

Form

I. S $->$ aAbB; A $->$ a; B $->$ b

II$.$ S $->$ aA; A $->$ B; B $->$ CD$/$b; C $->$ c; D $->$ d

Q$7.$ Using Pumping Lemma proof that the following language is not Context

Free:

a$.$ L $=\{$a$^$n

b

n

c

n

$/$ n $>0\}$

b$.$ L $=\{$a

n

b

n$+1$

c

n$+2$

$/$ n $>0\}$

c$.$ L $=\{$a

n

b

$2$n

c

$3$n

$/$ n $>0\}$