Back to the 2025 paper

Module 1: Introduction & Regular Languages

20252m

Regular languages belong to which type in the Chomsky hierarchy?

(i) Type-0
(ii) Type-2
(iii) Type-1
(iv) Type-3

Worked SolutionAI Assisted

Answer

Correct Option: (iv) Type-3

Explanation

Chomsky Hierarchy (Noam Chomsky, 1956)

Type Language Class Grammar Automaton
Type-0 Recursively Enumerable Unrestricted Turing Machine
Type-1 Context-Sensitive Context-Sensitive Linear Bounded Automaton
Type-2 Context-Free Context-Free Pushdown Automata
Type-3 Regular Regular (Left/Right-linear) Finite Automaton (DFA/NFA)

Regular languages are the most restricted class, generated by:

  • Right-linear grammars: A→aB∣a∣ϵA \rightarrow aB \mid a \mid \epsilon
  • Left-linear grammars
  • Regular expressions

and recognized by DFA/NFA/ε-NFA.

They are strictly contained:
Type-3⊂Type-2⊂Type-1⊂Type-0 \text{Type-3} \subset \text{Type-2} \subset \text{Type-1} \subset \text{Type-0}

Final Answer

Regular languages are Type-3 languages. Correct option (iv).

Similar questions

Official AppAndroid App

PYQDeck for Android

Solve BEU previous-year exam papers anywhere, anytime. Fast search, offline paper viewing, and step-by-step solutions designed specifically for your phone.