Theory of Computation (Automata)
Select the accurate description of Chomsky hierarchy.
- A. A visual representation showing how an automaton moves between states based on input symbols.
- B. A classification of formal grammars into four types based on their generative power. ✓
- C. A sequence of characters that defines a search pattern, corresponding to regular languages.
- D. A property of a problem indicating whether an algorithm can be constructed that always provides a correct yes/no answer.
Correct answer
B. A classification of formal grammars into four types based on their generative power.
Explanation
Chomsky hierarchy refers to a classification of formal grammars into four types based on their generative power.