Exercise $1($Ex$.1,$ Chapter $4$ of $[$Martin; $2011]).$ In below, say what language $($a subset of $\{$a$,$ b$\}*)$ is generated by the context$-$free grammar with the indicated productions.Exercise $3($Ex$.28,$ Chapter $4$ of $[$Martin; $2011]).$ Draw an NFA accepting the language

generated by the grammar with productions and prove it is minimal

$S$abA$|bB|aba$

$Ab|aB|bA$

$BaB|aA$

Exercise $4($Ex$.38,$ Chapter $4$ of $[$Martin; $2011]).$

In each case below, show that the grammar is ambiguous, and find an equivalent unambiguous

grammar.

b$.$

$S$ABA

$AaA|$

$BbB|$

c$.S$aSb$|aaSb|$

Exercise $5($Ex$.50,$ Chapter $4$ of $[$Martin; $2011]).$

Given the context$-$free grammar $G,$ find a CFG $G\text{'}$ with no $-$productions and no unit productions

that generates the language $L(G)-\{1\}.$

a$.G$ has productions

$S$ABA

$AaA|A$

$BbB|A|$

S $->$T T

T $->$ aT $|$ T a $|$ b

Exercise $2($Ex$.10,$ Chapter $4$ of $[$Martin; $2011]).$

Find context$-$free grammars generating the languages below.

$\{$aibj $|$ j $<mtext\; id="EditorElement\_1817056"></mtext><mn\; id="EditorElement\_1817057">2</mn>$i$\}$

Exercise $3($Ex$.28,$ Chapter $4$ of $[$Martin; $2011]).$ Draw an NFA accepting the language generated by the grammar with productions and prove it is minimal

S $->$ abA $|$ bB $|$ aba

A $->$ b $|$ aB $|$ bA

B $->$ aB $|$ aA

Exercise $4($Ex$.38,$ Chapter $4$ of $[$Martin; $2011]).$

In each case below, show that the grammar is ambiguous, and find an equivalent unambiguous grammar.

b$.$ S $->$ ABA

A $->$ aA $|\backslash$Lambda

B$->$bB $|\backslash$Lambda

c$.$ S $->$ aSb $|$ aaSb $|\backslash$Lambda

Exercise $5($Ex$.50,$ Chapter $4$ of $[$Martin; $2011]).$

Given the context$-$free grammar G$,$ find a CFG G$$ with no $\backslash$Lambda $-$productions and no unit productions that generates the language L$($G$)\{\backslash$Lambda $\}.$

a$.$ G has productions

S $->$ ABA

A $->$ aA $|\backslash$Lambda

B$->$ bB $|\backslash$Lambda