# How to prove this language is context free?

There's lots of ways to prove a language is not context free. Going through some exercises, I'm stuck at a question that asks me to prove that a language is indeed context free.

$$L = \{a^{(n+1)} b^{(m+2)}c^{(n+4)}\ |\ m, n ≥ 0 \}$$

I see that the langauge is equivalent to $$L = \{aa^nbbb^mccccc^n\}$$, but I'm not sure if that helps at all.

Maybe breaking the language apart into a concatenation of three languages like $$\{a^{n+1} | n>= 0\}.\{b^{m+2} | m >= 0\}.\{c^{n+4} | n>=0\}$$ might be helpful, because we can do a rule separately for each? The n has to be equal for the left and right side though, which I'm having difficulty with.

Any help would be much appreciated!

I see that the language is equivalent to $$L = \{aa^nbbb^mccccc^n\}$$,

Indeed

but I'm not sure if that helps at all.

Well, maybe not. How about if we write the equivalent language ever-so-slightly differently:

$$L = \{a^nabbb^mccccc^n\}$$

That's the same as

\begin{align}L &= \{a^nMc^n\}\\ M &= \{abbb^mcccc\}\\ \end{align} And then \begin{align}L &= \{a^nMc^n\}\\ M &= \{abbNcccc\}\\ N &= \{b^m\}\\ \end{align} Which seems pretty straight-forward.

Or, to put it another way: Look for symmetries. Or try to create them.

The ways to prove a language context free are to (1) exhibit a context free grammar for it; (2) exhibit a PDA accepting it; (3) construct it using closure properties. Here I'll go for (1).

Words in the language have a number of $$a$$ at the beginning and end that almost match, and an arbitrary (almost) number of $$b$$ in the middle. So a grammar is as follows:

\begin{align*} S &\to a S a \mid a A a a a a \\ A &\to A b \mid bb \end{align*}

The idea is that the first production for $$S$$ adds $$a$$ at both ends, the second one fills up the start and end numbers (1 and 4, respectively) and hands the task over to $$A$$. Now $$A$$ adds $$b$$ in the first production, finishes off with $$b b$$ to complete at least two of them.

The other alternatives I leave as an exercise. For a PDA, think how you would check that the word is of the required form, reading a symbol at a time and having only a stack as memory.