0
$\begingroup$

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!

$\endgroup$
0
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.