0
$\begingroup$

The alphabet is $\{a, b\}$

Hi, I tried this:

Assume to the contrary that $L$ is regular. Let $p$ be the pumping length given by the pumping lemma. Let $s$ be the string $a^{p}ba^{p}$. Because $s$ is a member of $L$ and $s$ has length more than $p$, the pumping lemma guarantees that $s$ can be split into three pieces, $s=xyz$, satisfying the three conditions of the lemma:

1. for each $i\ge0,xy^{i}z\in L,$

2. $|y|>0, and$

3. $|xy| \le p.$

$x=a^{s}, y=a^{t},z=a^{p-s-t}ba^{p}$

for $i=0,$ $xy^{0}z \in L$

I don't understand how to solve it.

Thanks.

$\endgroup$
-1
$\begingroup$

Z = uvw.

We’ll define x = 0^(p+1)1^(p+1)0^(p)1^(p).....000111001101.

we’ll define Z = x^R • x (Reverse of x concatenated with x).

Z is clearly in L (notice how I defined x so that Z is definantly bigger than 4).

Now, no matter what v is (obviously within the constraints of the pumping lemma), if we take i = 0 the word produced will not be in L (this is easily proven using the zero’s at the beginning of x).

$\endgroup$
  • $\begingroup$ I don’t understand why this post was deleted, I thought concise and correct answers are optimal. $\endgroup$ – Euclid Aug 19 '18 at 8:49
  • $\begingroup$ @Leucippus (forgot to tag) $\endgroup$ – Euclid Aug 19 '18 at 13:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.