Which of the following CFG’s can't be simulated by an FSM?
[A] S → Sa | a
[B] S → abX X → cY Y → d | aX
[C] S → aSb | ab
[D] None of the above
Answer & Explanation
Answer: Option [C]
The set generated by the Option (C) is ( anbn, n=1, 2, 3, ………) which is not regular. Options (A) and (B) being left linear and right linear respectively and option [c] cannot be simulated by an FSM.