$1.(25$ marks$)$ Provide the rules for context$-$free grammars that generate the following languages.

$($a$)$ L$1=\{$w in $\{$a$,$ b$\}$

$$

$|$ w starts and ends with ba and contains at least one other occurrence of

ba somewhere in between$\}$

$($b$)$ L$2=\{$a

pb

qc

rd

s

$|$ p$,$ q$,$ r$,$ s in Z

nonneg, p $=4$s$,$ q $>$ r$\}$

$($c$)$ L$3=\{$w in $\{0,1\}$

$$

$|$ n$0($w$)>=2$ and n$1($w$)>=1\}$

$($d$)$ L$4=\{$a

nx $|$ n in Z

nonneg, x in $\{$b$,$ c$\}$

$$

$,|$x$|>=$ n $+2\}$

$[$For example, the strings aaabccbc and cbc are in L$4,$ but the strings aacbc, aaabbc and

aabacccc are not.$]$

$($e$)$ L$5=\{$a

ib

jc

k

$|$ i $=$ j or j $=$ k; i$,$ j$,$ k in Z

nonneg$\}$

$[$For example, the strings aabbcccc, aaaaabc, abc, ccc and $$ are in L$5,$ but the strings

abbccc and abacc are not.$]$