0
$\begingroup$

I can find many proofs for how a language is not context free using the pumping lemma. But I am not sure how to definitely prove a language is context free. Consider this language:

$$\mathcal{A} = \{ a^m b^n c^n ~:~ m,n \ge 0\}$$

Could someone demonstrate a proof. More importantly, when given a non-regular language, sometimes you can find strings in the language that can be pumped. So how do I argue $\mathcal{A}$ is context free using the pumping lemma, and be satisfied that someone else won't come up with some string in $\mathcal{A}$ above that cannot be pumped?

$\endgroup$
1
$\begingroup$

You cannot use the pumping lemma to show that a language is context-free. You can show that it's context-free by giving a context-free grammar for it or a pushdown automaton that accepts it. Here it's not hard to come up with a suitable grammar. The idea is to generate a string of $a$'s first, and then to generate the $b$'s and $c$'s 'from the inside out', so to speak.

If $S$ is the initial non-terminal, $S\to aS\mid X\mid\epsilon$ will get you started. Can you figure out how to make $X$ generate strings of the form $b^nc^n?$

$\endgroup$
  • $\begingroup$ With a slight change of terminology, if $B \rightarrow bc ~|~ bBc$, then $A \rightarrow \epsilon ~|~ aA ~|~ B$? $\endgroup$ – chibro2 Feb 11 '15 at 0:14
  • 1
    $\begingroup$ @chibro2: Yes, that works just fine. $\endgroup$ – Brian M. Scott Feb 11 '15 at 0:15

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.