Question

Which of the following CFG’s can’t be simulated by an FSM?

(a) S->Sa/b

(b) S->aSb/ab

(c) S->abX, X->cY, Y->d/aX

(d) None of the mentioned

The question was asked in an online quiz.

This interesting question is from The NFA with epsilon in division Finite Automata and Regular Expression of Compiler

Answer 1

Correct choice is (b) S->aSb/ab

For explanation I would say: generates the set {an bn, n=1,2,3 ….}which is not regular.