I've been trying to make a CFG, and npda/pda for this language (to construct an npda for accepting the language):

L(M)={ww:w∈{a,b}∗,|w| is even}.

i had already solved the reverse of the language (like this):


Please check this snapshot to know what i am asking to do ! (L') : http://i921.photobucket.com/albums/ad53/Johann_1990/IMG_20150117_132616.jpg

but is there is a way to solve this L(M)={ww:w∈{a,b}∗,|w| is even}?

For example, abaaba∈L with w=aba.

Note that I'm not asking to prove by conduction or anything else.

  • $\begingroup$ First of all, why should $|w|$ be even - it's not in your example. Then, $L'$ is a completely different language, and if I'm not totally wrong, $L$ is NOT context-free. So there is no pda/cfg. $\endgroup$ Jan 17, 2015 at 12:55
  • $\begingroup$ I'm just giving an example to show what i am asking exactly, |w| is another example I'm trying to understand it too. I'm looking at the book page 178 "An introduction to formal languages and Automata 5th" its solving L as in my example ! $\endgroup$
    – FixoMiFa
    Jan 17, 2015 at 13:05
  • $\begingroup$ Can you post the exact text of the exercise (or whatever it is) and its context? Like this, it does not make sense. $\endgroup$ Jan 17, 2015 at 17:25
  • $\begingroup$ @lukas.coenig the example context says : "to construct npda's that accept this language" : L(M)={ww:w∈{a,b}∗,|w| is even}. $\endgroup$
    – FixoMiFa
    Jan 17, 2015 at 18:55

1 Answer 1


Short answer: $L$ is not context-free, so there is no CFG/PDA.

  • $\begingroup$ You are right, i got it ! thank you :) $\endgroup$
    – FixoMiFa
    Jan 17, 2015 at 19:06
  • $\begingroup$ Nice, I'm happy for you! :-) $\endgroup$ Jan 17, 2015 at 19:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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