1
$\begingroup$

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 ?

$\endgroup$
4
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Raphael Aug 28 '13 at 10:52
  • $\begingroup$ 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. $\endgroup$ – mrjasmin Aug 28 '13 at 11:03
  • $\begingroup$ 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. $\endgroup$ – Raphael Aug 28 '13 at 11:35
  • $\begingroup$ But there is values of q for which the language is not a context-free language ? $\endgroup$ – mrjasmin Aug 28 '13 at 11:40
  • $\begingroup$ 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. $\endgroup$ – Raphael Aug 28 '13 at 12:39

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.