World's most popular travel blog for travel bloggers.

[Solved]: Show this language is non-regular using pumping lemma: B = {ww | w ��� {a,b,c,...,z)*}

, , No Comments
Problem Detail: 

The question I'm working from is:

Prove whether or not a finite automation exists that recognises the following language:

B = {ww | w ∈ {a,b,c,...,z)*}


So I believe this is a non-regular language. My understanding of pumping lemma is not great but this was my solution:

S = apbapb

Where S is a valid string in the language and p is the pumping length.

S = aaaabaaaab for example when p = 4

S = xyz // s can be split into xyz components

| x y | <= p

SO y must be all a's before the first b e.g. a | aaa | baaaab

xy2z = aaaaaaabaaaab

xy2z is not in B

Therefore B is not regular

Apparently though this is wrong, please could someone explain why / how to obtain the right answer?

Asked By : user44576

Answered By : Renato Sanhueza

Your proof using the pumping lemma is wrong. You choose a pumping lemma constant $p=4$ but what happens if $p=5$ works? The pumping lemma tell us that there exists a constant $p$. Now you have to try all the remaining possible values of $p$.

I recommend you to study carefully the pumping lemma first. It is a bad idea to try using it without understanding it. After that if you want to assimilate it more you can check this answer: where I explain some common mistakes.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback