Theory of computation

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 these

Comments

B) ..

---

plz tell me  solution /reason

---

S->aSb/ab

If you try to check what strings the grammar generates then you will find that they are in the form of {aⁿbⁿ/n>0}.

S->aSb>aaSbb->aaaSbbb->aaaabbbb (like this)

This can't be a regular language because we have to remember the count of a and match it with b. In FSM we don't have any mechanism to "remember" anything..

Answer 1

Answer is B). S->aSb/ab

Because its language contains L = {ab,aabb,aaabbb......} = a^nb^n;for which Finite state machine is not possible