How to prove this language is context free?

Question

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!

Answer 1

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.

Answer 2

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.