Problem $4$

Let $L1=\{a^{n}c{b}^n$:$n1\}$ be a context free language.

a$.$ Give a context$-$free grammar G$1$ that derives L$1.[$Do this by modifying the grammar $S$aSb$|||$

b$.$ Hand draw a parse tree for $w=$ aaacbbb using grammar G$1.$ Paste your parse tree into Homework $5.$

c$.$ Give a context$-$free grammar G$2$ that derives $\{$:$a^{n}cc{a}^n$:$n0\}$

$[$Do this by modifying the grammar you found in

Part a$]$

d$.$ Give a leftmost derivation of the string $w=$ aaccaa from G$2.$ Use one step per line. Make one replacement per line and always underline the variable being replaced.

e$.$ Give a context$-$free grammar G$3$ that derives L$3a^{n}cc{a}^n$:$n0$ Find a parse tree for G$3$ for $w=$ accaaaccaacccc. Use the technique from the slides from Chap $5\mathrm{.}1$ b for creating the starclosure of $L=\{a^{n}cc{a}^n$:$n0\}$