6
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Luke Mathieson Dec 17 '14 at 3:11
  • $\begingroup$ It is obviously non regular, as FSA cannot count unboundedly. Your pumping proof seems correct. $\endgroup$ – babou Dec 17 '14 at 15:50
1
$\begingroup$

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).

$\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.