Deciding if language is Context-Free

I need help with deciding if $L$ is context-free.

$$L = \{a^pb^{q+r}c^sd^{q+t}e^{p+r} \mid p, q, r, s \ge 0\ , s > t\}$$

Can be rewritten into:

$$L = \{a^pb^qb^rc^sd^qd^te^pe^r \mid p, q, r, s \ge 0\ , s > t\}$$

When we see the first occurrence of $c$, we push the $c$:s onto the stack. But we can't make difference between $d^q$ and $d^t$, so comparing $s < t$ is impossible when popping the $d$:s.

Hence $L$ is not Context-Free.

Is my reasoning right ?

mrjasmin

Posted 2013-08-28T00:05:59.243

Reputation: 536

Answers

Hint: rewrite $L$ as $L = \{a^p b^r b^q c^s d^t d^q e^r e^p \mid p,q,r,s \ge 0, s>t\}$.

Does $L$ now look like something you can generate with a CFG?

Shitikanth

Posted 2013-08-28T00:05:59.243

Reputation: 636

You reasoning is not correct, and not only because you reach the wrong answer.

You argued for one representation of the language that it can't be faithfully checked by one (idea for) a push-down automaton. However, in order to show that a language is not context-free you have to show that no PDA can accept the language in any representation.

There are techniques to approach this task; see our reference question. Always try these if you think a language is not context-free. If you are not able to apply those techniques, you may figure out how to build a PDA or a grammar along the way -- or you have a really tough language at your hands.

Raphael

Posted 2013-08-28T00:05:59.243

Reputation: 69 237

If we rewrite L as

$$L = \{a^pb^qb^rc^sd^td^qe^pe^r \mid p, q, r, s \ge 0\ , s > t\}$$

If we then look at the case where $$q = 0$$ and $$s, t > 0$$

We take this example string $$z = abcccddee$$ which belongs to L.

This string can be accepted by a PDA and the comparison $$s > t$$ can be done by pushing all the c:s and then popping the d:s.

L is context-free because we showed that a PDA exists for SOME representation of the language.

Is my reasoning right ?

mrjasmin

Posted 2013-08-28T00:05:59.243

Reputation: 536

No, you still need to give a grammar or PDA (and prove its correctness). All you did was pick a specific string and claim it can be accepted by some PDA. While that is true, any single string can be accepted by an NFA, too, but the language is certainly not regular. – Raphael – 2013-08-28T10:52:52.407

I know that I have to give a CFG but my reason was informal. In the original question there were 1 more language and the question was to decide which of them was Context Free and which not. So I used the reasoning above to decide for which language to construct the pumping lemma proof. And of course you are right, I still have to give a CFG to prove it Context Free, but my intention was to informally decide which of the two languages is Context Free and then use the pumping lemma proof to on the other language to prove it. – mrjasmin – 2013-08-28T11:03:11.873

Even informally, your argument is bad. You have to come up with an (informal) strategy to accept every word in the language (and no others). So in particular, assuming $q=0$ is a no-go. Otherwise you will be easily tricked because you only "show" a sublanguage to be context-free. – Raphael – 2013-08-28T11:35:47.147

But there is values of q for which the language is not a context-free language ? – mrjasmin – 2013-08-28T11:40:43.973

No, but that's not the point. The original language is the union of all your $q$-restricted languages and you have to talk about that one. Proving stuff is not about stating truth, but deriving truth from a set of axioms using sound rules. – Raphael – 2013-08-28T12:39:39.323