Prove that the language is nonregular using the Pumping Lemma:

80 Views Asked by At

{$x_1 a x_2$ such that $x_1, x_2$ are in {a,b}* and |$x_1$| = |$x_2$|}.

My understanding is that there is a number p where if any string s in the language has length of at least p, then s = uvw.

1) For each i $\ge$ 0, then u$v^i$w is in the language

2) |v| > 0

3) |uv| $\le$ p.

Now, I actually don't know how to approach the problem, because if the length of $x_1$ and $x_2$ are the same, then the string s should be of odd length. Is there a way to construct the string so that it doesn't divide by 2 (besides it being |s|= 2k+1 for some number k)? And how would I prove it using contradiction?

Any help would be appreciated.

1

There are 1 best solutions below

0
On

HINT: Let $L$ be the language, and suppose that $L$ is regular. Let $p$ be the pumping length, and let $s=b^pab^p$. Clearly $s\in L$, so by the pumping lemma there are $u,v,w\in\{a,b\}^*$ such that $s=uvw$, $|uv|\le p$, $|v|\ge 1$, and $uv^kw\in L$ for each $k\ge 0$.

First explain why $v=b^r$ for some $r>0$. Use that observation to show that $uv^kw\notin L$ if $k\ne 1$. This contradiction shows that in fact $L$ cannot be regular after all.