# context free grammar to NFA

I've been given an exercise to solve which goes as follows: generate an NFA from the given CFG,

\begin{align*}S &\to AB \mid c\\ A &\to aAb \mid c\\ B &\to bBa \mid c\ . \end{align*}

Now correct me if I'm wrong, but if this language has an NFA it means it is regular. But looking at this grammar the language described is $L=\{a^n cb^{n+k}ca^k\mid n,k\geq 0\}$. If so, I can use the pumping lemma by taking the promised number $n$, choose the word $a^ncb^{n+k}ca^k$, for $xyz$ we get $x=a^s$, $y=a^t$ ($t\ge1$), then I can pump for $i=2$ and get $a^{n+t}cb^{n+k}ca^k$ which is not in the language. Hence the language is not regular and that means there can't be an NFA for it.

I might have done something wrong but I cant see it. Any suggestions?

• It does seem to be non-regular (but context free). Maybe it's a test to see if you recognise that it can't be done? – Luke Mathieson Dec 17 '14 at 3:11
• It is obviously non regular, as FSA cannot count unboundedly. Your pumping proof seems correct. – babou Dec 17 '14 at 15:50

You can use the pumping lemma to show that $L$ is not regular and by definition you can't generate NFA. Maybe the question is wrong and they want you to generate a pushdown automaton (PDA).