Create CFG and pushdown automaton for {ww} [duplicate]

Question

I've been trying to make a CFG, a pushdown automaton and a regular expression for the language

$\qquad L(M) = \{ww : w \in \{a, b\}^*, |w| \text{ is even}\}$.

I understand how the reverse of the string work, that is

$\qquad L' = \{ ww^R : w \in \{a, b\}^*\}$,

but is there is a way to solve this one too?
$\qquad L(M) = \{ww : w \in \{a, b\}^*, |w| \text{ is even}\}$.

For example, $abaaba \in L$ with $w = aba$.

Note that $ww = abaaba$ is a bad example (as in, you don't learn anything from it) here as $w = w^R$. — Raphael, Commented Jan 16, 2015 at 14:58
@Raphael , i need to train my self for any example.. when i am learning ! i know how to make the reverse of string pushdown or cfg, i was just trying something new! Thank you ! — FixoMiFa, Commented Jan 16, 2015 at 20:52
@D.W.,its not the same question am talking about another thing completely.. — FixoMiFa, Commented Jan 16, 2015 at 20:53

Community · Accepted Answer · 2017-04-13 12:48:34Z

1

You can not do so as $L$ is not context-free.

See our reference questions for how to prove that, i.e.

CommunityBot

1

answered Jan 16, 2015 at 12:30

Raphael

72.8k30 gold badges180 silver badges392 bronze badges

$\begingroup$ so are you saying that it cannot be proved ? only the reverse of the string can be proved ? $\endgroup$
– FixoMiFa
Commented Jan 16, 2015 at 13:00
$\begingroup$ @AaoIi That's what I'm saying, yes. At least, your first statement. I don't understand the second. $\endgroup$
– Raphael
Commented Jan 16, 2015 at 14:54
$\begingroup$ I'm saying that this L′={wwR:w∈{a,b}∗}, I've seen that its accomplished in cfg and pushdown automata , so why L={ww:w∈{a,b}∗,|w| is even}.cannot be accomplished ? prove is not what I'm asking for, I'm asking for making the cf grammar for it as S -->aB and drawing the pushdown ? $\endgroup$
– FixoMiFa
Commented Jan 16, 2015 at 15:34
1

$\begingroup$ I recommend you read some literature covering the basics and then go read the questions I link. (Your terminology is shaky; what is "accomplish"?) The answers are all there, hence I only link. (Hint: "L is not context-free" implies "there is no context-free grammar, pushdown-automaton or regular expression for L".) $\endgroup$
– Raphael
Commented Jan 16, 2015 at 15:38
$\begingroup$ i got it, I'm just trying to understand Formal Language and Automata, Thank you for you help :) $\endgroup$
– FixoMiFa
Commented Jan 16, 2015 at 15:42

Add a comment |

1 Answer 1