FSM can recognize
a) Any grammar
b)Only CFG
c)Any unambiguous grammar
d)Only regular grammar

Question

FSM can recognize
a) Any grammar
b)Only CFG
c)Any unambiguous grammar
d)Only regular grammar

shadowfiend · Answer

Finite state machines can only recognize regular grammars. In particular, regular grammars are actually defined as being regular if and only if there is a Finite State Machine that can recognize them.

jagatuba · Answer

@shadowfiend: That kinda sounds like the chicken or the egg dilemma. FSM's can only recognize regular grammars, but regular grammars can only exist if there is a FSM that understands them. o.O

shadowfiend · Answer

It's not. FSMs are defined a certain way (mathematically, in terms of states and transitions between the states), regular languages are defined as the languages that an FSM can recognize.