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)*}

, ,
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)*}

EDIT

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?

#### 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: http://cs.stackexchange.com/a/50618/31129 where I explain some common mistakes.