Exercise $21$ Pumping Lemma for beginners

$(8$ points$)$

Show by means of the Pumping Lemma for regular languages, that the following languages are not regular:

$($a$)L_1=\{a^{2k}{b}^k|kin{N}_0\}$

$($b$)L_2=\{b{a}^{k}c{a}^{k}b|kin{N}_0\}$

$($c$)L_3=\{a^k{b}^{(k^2)}|kin{N}_0\}$

Your proof should have the following form:

Let $n$ be an arbitrary natural number. We choose the word $x=.$ Then xinL and $|x|n$ holds. We can decompose $x$ in the following ways, such that $|uv|n,|v|1$ :

$u=$

$v=$

$w=$

where

$u=$

$v=$

$,w=$

where

$u=$

$v=$

$,w=$ where

For every decomposition there is an index i such that $u{v}^{i}w!$inL. For the decompositions mentioned above, we choose the indices as follows:

$1$

$i=q,,$ such that $u{v}^{i}w=!$inL, because

$i=,$ such that $u{v}^{i}w=|!$inL$||,$ because

$i=,$ such that $u{v}^{i}w=$

$!$inL, because

According to the Pumping Lemma $L$ is therefore not regular.

$($Note: The number of different decompositions depends on the chosen word and the way of describing the decompositions.$)$

$($In total, there are $20$ points in this exercise sheet.$)$