$($a$)$ Convert the given regular expression into a context$-$free grammar.

$a(ba{)}^{**}+$#$a^{**}b$

Let $=\{a,b,$#$\}.$ Consider the following languages over $.$ Recall that for a string $w,|w|$ denotes the length

of $w.$

$L_1=\{a^{4i}$ where $i0\}$

$L_2=\{b^{2j}$ where $j0\}$

$L_3=\{x$#$y,$ where $xin{L}_1,yin{L}_2$ and $|x|=|y|\}$

Now solve the following problems.

$($b$)$ Your Friend writes the following context$-$free grammars for the language $L_1.$ Choose the correct grammar

for $L_1.$ There could be more than one correct grammar.

$($i$)$

$S$ASA$|$

$Aaa$

$($ii$)$

$S$AAS$|$

$Aaa|$

$($iii$)$

$S$AAAAS$|$

$Aa$

$($iv$)$

$SaP|aQ|$

$PaR$

$RaQ$

$QaS$

$($c$)$ Write down a string of any length in $L_0.$

d$)$ Give a context$-$free grammar for the language $L_3.$