Prove the following language is context free

878 Views Asked by At

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?

1

There are 1 best solutions below

2
On BEST ANSWER

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?$