0
$\begingroup$

So I have a pumping lemma question A{www|w ∈ {a,b}*} I have the correct answer but I'm not fully sure how it works. I'll give the answer just so people know what I'm going with

Assume A is REG let p be the pumping length x ∈ A, x=a^p b, a^p b, a^p b.... |s|=3p+3 where each a^p b is a w

Let s = xyz a split such that 1)sum of i>=0 s'=xy'z ∈ A 2)|x|>0 , 3)|xy| <=p

By (3) y contains only a's and by (2) y contains at least 1 a. Let s'=xyyz, Then s=a^+ ba^p ba^p b,

1)s' ∈ A as it contains contradiction t>p ie. A not an element of REG

$\endgroup$
  • $\begingroup$ You might want to learn how to post using mathematical notation. This site supports MathJax and $\LaTeX$. $\endgroup$ – hardmath Jan 20 '16 at 22:59
0
$\begingroup$

you want to prove that $\mathcal L=\{www|w\in\{a,b\}^*\}$ is not regular

The word the you chose: $x=a^pba^pba^pb$

$|x|=3p+3>p$ so we can use the pumping lemma

so $x=uvw$ etc...

Note that

$\underbrace{aaaaa...b}_{\text{p+1 latters}}\underbrace{aaaaa...b}_{\text{p+1 latters}}\underbrace{aaaaa...b}_{\text{p+1 latters}}$


So since that $|uv|\leq p$ uv can be here:

$\overbrace{aaa...}^{\text{uv}}b,aaaa....b,aaaa....b$

Or here:

$aaaa....b,aaaa....b,\overbrace{aaa...}^{\text{uv}}b$

Or here:

$aaaa....b,\overbrace{aaa...}^{\text{uv}}baaaa....b$

Or here:

$aaaa...\overbrace{.b,aa}^{\text{uv}}aa...b,aaaa....b$

Or here:

$aaaa....b,aaaa..\overbrace{.b,a}^{\text{uv}}aaa...b$

Now if you choose $i=2$ the word is not in $\mathcal L$

$\endgroup$

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.