Context free grammar to NFA

Question

I've been given an exercise to solve which goes as follows: generate an NFA from the given CFG,
S -> AB | c
A -> aAb | c
B -> bBa | c

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={w| w=aⁿcb^n+kca^k} Assuming I'm not wrong I can use the pumping lemma -> by taking the promised number n, choose the word aⁿcb^n+kca^k, for xyz we get x=a^s y=a^t while t>=1, then I can pump for i=2 and get a^n+tcb^n+kca^k which is not in the language hence the language is not regular and that means there cant be an NFA for it.

I might have done something wrong but I cant see it, any suggestions ?

Answer 1

I agree with your set-theoretic characterization of the grammar you've been given. I also agree with the statement that $L$ is not regular. The Myhill-Nerode theorem can be used to reason about it as follows: $L$ has infinitely many equivalence classes under the Myhill-Nerode theorem, so it's not regular. Specifically, each $a^n$ is distinct from every $a^m$ where $n \ne m$. This can be shown by observing for the distinguisher $cb^{n+k}ca^{k}$, $a^{n}cb^{n+k}ca^{k}$ is in $L$, but $a^{m}cb^{n+k}ca^{k}$ is not.