Context Free Grammars

$])$:$\}$

$A,,1A|lon|$

$[,B,$

Give a leftmost derivation for string $10101$

Give a parse tree for string $1001$

The language of this grammar is a regular language, can you find an equivalent regular expression for this language?

$($b$)$ In each case below, indicate what language is generated by the context$-$free grammar. The alphabet is $=\{0,1\}$

$S0S|1S|lon$

$S0S|0|$

In the following questions the alphabet is $=\{0,1\}$ :

$($c$)$ Write a grammar for the language $\{0^i{1}^j|i,j0\}.$

$($d$)$ Write a grammar for the language $\{0^i{1}^j|i>j\}.$

$($e$)$ Write a grammar for the language $\{0^n{1}^m{0}^m{1}^n|n,m0\}.$

$($f$)$ Write a grammar for the language $|),(vin{}^{**}$ and $\{$:$|u|=|v|\}.$

$($g$)$ Let $B$ be the collection of strings that contain at least one $1$ in their second half. In other words, $|),(vin{}^{**}1{}^{**}$ and $\{$:$|u||v|\}.$

Give a CFG that generates B$.($HINT: Start with the grammar that you used for question $f$ and modify it$).$

$($h$)$ Given context$-$free grammars for languages $L_1$ and $L_2$ with start variables $S_1$ and $S_2$ respectively. Give the grammar for $L_1{L}_2,$ the grammar for $L_1$@$L_2,($the concatenation$),$ and the grammar for $L_1^{**}.$