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?

  • 1
    $\begingroup$ the task can indeed be solved by finding a regular expression for $B$ but maybe it can be solved by proving that $B$ is not regular $\endgroup$ – phs Jan 7 '16 at 19:46
  • 1
    $\begingroup$ I don't see a question here. What are you asking? If you want us to solve the exercise for you, that's off-topic. $\endgroup$ – David Richerby Jan 7 '16 at 19:50
  • 1
    $\begingroup$ We are trying to hint that perhaps the language isn't regular after all. $\endgroup$ – Yuval Filmus Jan 7 '16 at 20:34
  • 1
    $\begingroup$ Welcome to Computer Science! Your question is a very basic one. Let me direct you towards our reference questions which cover your problem in detail, especially cs.stackexchange.com/questions/1031/…. $\endgroup$ – D.W. Jan 7 '16 at 22:51
  • 1
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Jan 7 '16 at 22:52

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

| cite | improve this answer | |
  • $\begingroup$ Oh.. i saw a video youtube.com/watch?v=g4e2RElzCSQ which seemed to indicate that you could just assume a pumping lemma constant and if you could find a single contradiction, it's not regular. Having seen your post you linked to, I can see that's not the case but now I am confused about what values of p to try. How do I know which p is correct? Oh so confused.. $\endgroup$ – user44576 Jan 7 '16 at 22:27
  • 1
    $\begingroup$ Just use a generic constant p. You don't need to give it a numerical value. $\endgroup$ – Renato Sanhueza Jan 7 '16 at 22:53
  • 1
    $\begingroup$ For example. Consider the word $\sigma = a^pba^pb$ with $|\sigma|=2p+2 \geq p$. You can say that $xy$ are only letter a's because $|xy|\leq p$. I really can't be more precise without solving the exercise. $\endgroup$ – Renato Sanhueza Jan 7 '16 at 23:00
  • 1
    $\begingroup$ @user44576, you can not assume any specific pumping lemma constant, you are trying to show none works. $\endgroup$ – vonbrand Jan 23 '16 at 1:21

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