Finite state machine can recognize language generated by __________.

Answer: Only regular grammar.

Explanation:

• Finite state machines (deterministic or nondeterministic) recognize exactly the class of regular languages generated by regular grammars.

• Regular grammars, regular expressions, and finite automata are equivalent formalisms for the same class of languages.

• Context-free languages are more expressive (for example, {a^n b^n | n ≥ 0}) and require a pushdown automaton rather than a finite state machine.

• Context-sensitive languages are yet more powerful and typically need a linear bounded automaton to be recognized.

• An unambiguous grammar is a property of a grammar (unique parse trees) and does not guarantee the generated language is regular.