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?

Improve this question
$\endgroup$
2
  • 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
    Commented Dec 17, 2014 at 3:11
  • $\begingroup$ It is obviously non regular, as FSA cannot count unboundedly. Your pumping proof seems correct. $\endgroup$
    – babou
    Commented Dec 17, 2014 at 15:50

1 Answer 1

Reset to default
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).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.