Linz Section $5\mathrm{.}2$ exercises $1-5$

Note: for one of the following, no S$-$grammar exists. Determine which one does NOT have a corresponding S$-$grammar, and explain why.

Show that

$SaS|bS|cA$

$AaA|bS|$

is an s$-$grammar.

$2.$ Show that every s$-$grammar is unambiguous.

$3.$ Find an s$-$grammar for $L(aa{a}^{**}b+a{b}^{**}).$

$4.$ Find an s$-$grammar for $L=\{a^n{b}^n$:$n2\}.$

$5.$ Find an s$-$grammar for $L=\{a^n{b}^{2n}$:$n2\}.$