Exercise $23$ Incorrect Pumping Lemma proofs

$(5$ points$)$

In the following, two Pumping Lemma proofs are given. However, these proof attempts contain some

mistakes. For this task, take the role of our tutors and figure out what mistakes have been made in

these proofs, and why what you found actually is a mistake.

$($Note: The mistakes we are looking for are serious logical mistakes and not just notation nitpicking.

That said, subtasks $($a$)$ and $($b$)$ contain one mistake each, and $($c$)$ contains two or three mistakes

$($depends on how you count it$).)$

$($Note: You have to find the mistakes. It is not necessary that you write down a correct proof for these

languages, and it's also not sufficient in order to obtain points.$)$

$($a$)$ Proof attempt: $L=\{a^k{a}^k|kin{N}_0\}$ is not regular

We choose the word $x=a^n{a}^n.$ Then $|x|=2nn$ and xinL. We consider all decompositions

$x=$uvw where $|v|1,|uv|n$ :

$u=a^k,v=a^l,w=a^{n-k-l}{a}^n$ where $k0,l1,k+ln$

For each decomposition there exists an index i such that $u{v}^{i}w!$inL :

$i=2,$ then $u{v}^{2}w=a^k{a}^{2l}{a}^{n-k-l}{a}^n=a^{n+l}{a}^n!$inL, since $l1,$ therefore $n+ln.$

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

$($b$)$ Proof attempt: $L=\{a^k{b}^l|kl,k,lin{N}_0\}$ is not regular

We choose the word $x=a^n{b}^n.$ Then $|x|=2nn$ and xinL. We consider all decompositions

$x=$uvw where $|v|1,|uv|n$ :

$u=a^k,v=a^l,w=a^{n-k-l}{b}^n$ where $k0,l1,k+ln$

For each decomposition there exists an index i such that $u{v}^{i}w!$inL :

$i=2,$ then $u{v}^{2}w=a^k{a}^{2l}{a}^{n-k-l}{b}^n=a^{n+l}{b}^n!$inL, since $l1,$ therefore $n+ln.$

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

$($c$)$ Proof attempt: $L=\{w(w{)}^R|win{}^{**}\}$ is not regular ${?}^1$

We choose the word $x=a{b}^n{b}^{n}a.$ Then $|x|=2n+2n$ and xinL $($mirror axis between the

two $b-$blocks$).$ We consider all decompositions $x=$uvw where $|v|1,|uv|n$ :

${?}^1(w{)}^R$ is $w$ read backwards, i$.$e$.$ here we have the set of all words that are some $\{a,b\}$ sequence followed by the same

sequence in reverse, or put differently: words of even length that can be mirrored in the middle.

$($the $a$ is not in $uu=,v=a{b}^n,w=b^{n}a$

$($the $a$ is $,$ in $uu=a{b}^k,v=b^l,w=b^{n-k-l}{b}^n$a where $k0,l1,k+l+1n$

For each decomposition there exists an index i such that $u{v}^{i}w!$inL :

$i=0,$ then $u{v}^{0}w=b^{n}a!$inL, because the word contains only one $a,$ i$.$e$.$ an odd number of

as $($i$.$e$.$ there is some $a$ in the word that does not have a mirror image in the other half of

the word$)$

$i=3,$ then $u{v}^{3}w=a{b}^k{b}^{3l}{b}^{n-k-l}{b}^{n}a=a{b}^{k+3l+n-k-l}{b}^{n}a=a{b}^{n+2l}{b}^{n}a!$inL, since because of

$l1$ we have $n+2ln$

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