Proof by pumping lemma

289 Views Asked by At

Let's say that we have to prove that $L = \{ww^Rv |w,v\in \Sigma^*\}$ is irregular.

I would take a string such that $w = baba^m$ and $w^R=a^mbab$ and $v = a$

and then I would pump divide $w$ into $xy, x = bab$ and $y = a$

According to the pigeonhole principle, because $a^m$ size can be infinite and the number of state is equal to the number of transitions - $1$, there must be a loop for y. if $|y|$ is greater than 1 then $w^R$ is not the reverse of $w$, thus we've proven the language is not regular.

Questions:

Is this correct? It won't work for $w = baba$ and $w^R = abab$, right?

1

There are 1 best solutions below

0
On BEST ANSWER

Better you don't succeed: the language is regular. Any string can be written $x = \epsilon \epsilon^R x$.