Create cfg and npda/pda for Language {ww}

Question

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):

L′={wwR:w∈{a,b}∗},

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.

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. — lukas.coenig, Jan 17, 2015 at 12:55
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 ! — FixoMiFa, Jan 17, 2015 at 13:05
Can you post the exact text of the exercise (or whatever it is) and its context? Like this, it does not make sense. — lukas.coenig, Jan 17, 2015 at 17:25
@lukas.coenig the example context says : "to construct npda's that accept this language" : L(M)={ww:w∈{a,b}∗,|w| is even}. — FixoMiFa, Jan 17, 2015 at 18:55

lukas.coenig · Accepted Answer · 2015-01-17 12:57:53Z

4

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

answered Jan 17, 2015 at 12:57

lukas.coenig

7434 silver badges11 bronze badges

$\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$
– lukas.coenig
Jan 17, 2015 at 19:10

Add a comment |

1 Answer 1