Context$-$free Grammars:

$1-$ Show a context$-$free grammar for each of the following languages L:

a$)\{$anbm : m $$ n$,$ m$-$n is odd$\}$

b$)\{$w in $\{$a$,$ b$\}*$ : each even length prefix of w contains at least twice as many a$$s as b$$s$\}.$

$2-$ Let L be the language generated by the following context$-$free grammar:

S $$ R T

R $$ a R $|$ a R b $|$

T $$ b T $|$ b T a $|$

a$)$ List the first six strings in L$,$ in lexicographic order.

b$)$ Give a clear formal description of L $($using set notation, as in question #$1).$

$3-$ For each of the following languages L$,$ state whether L is regular or context$-$free but not regular. If L

is regular, show a regular grammar for it$.$ Otherwise, show a context$-$free grammar.

a$)$ b$)\{$w in $\{$a$,$ b$\}*$ : w $=$ x $($aa$)*$ xR$,$ for some string x in $\{$a$,$ b$\}*\}$

$\{$w in $\{$a$,$ b$\}*$ : w does not contain any substring of three consecutive a$$s$\}$

$4-$ Consider the following grammar for a fragment of English:

S $$ NP VP

NP $$ the Nominal $|$ a Nominal $|$ Nominal $|$ ProperNoun $|$ NP PP

Nominal $$ N $|$ Adjs N

N $$ pizza $|$ omelets $|$ pepperoni $|$ eggs $|$ whisk $|$ bacon

ProperNoun $$ Kim$|$ Dominos

Adjs $$ Adj Adjs $|$ Adj

Adj $$ green $|$ deepdish $|$ fluffy $|$ greasy

VP $$ V $|$ V NP $|$ VP PP

V $$ like $|$ likes $|$ beat $|$ beats $|$ sell $|$ sells

PP $$ Prep NP

Prep $$ with

Give an example of a sentence that is ambiguous with respect to this grammar. Show two parse

trees for your sentence.