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$ – lukas.coenig Jan 17 '15 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 '15 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$ – lukas.coenig Jan 17 '15 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 '15 at 18:55

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

| cite | improve this answer | |
  • $\begingroup$ You are right, i got it ! thank you :) $\endgroup$ – FixoMiFa Jan 17 '15 at 19:06
  • $\begingroup$ Nice, I'm happy for you! :-) $\endgroup$ – lukas.coenig Jan 17 '15 at 19:10

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.