EXERCISES

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\}.$

$6.$ Find an s$-$grammar for $L=\{a^n{b}^{n+1}$:$n1\}.$

$7.$ Let $G=(V,T,S,P)$ be an s$-$grammar. Give an expression for the maximum size of $P$ in terms of $|V|$ and $|T|.$

$8.$ Show that the following grammar is ambiguous:

$SAB|aaaB,||$

$Aa|Aa||$

$Bb.$

solve$3,4,6,8$