Back to the 2024 paper

Module 1: Introduction & Regular Languages

20242m

Which of the following is a type of grammar in the Chomsky hierarchy?

(i) Regular
(ii) Context-Free
(iii) Context-Sensitive
(iv) All of the above

Worked SolutionAI Assisted

Answer

Correct Option: (iv) All of the above

Explanation

Chomsky Hierarchy classifies grammars into 4 types:

Type Name Production Form Language Class
Type-0 Unrestricted α→β\alpha \rightarrow \beta, no restriction Recursively Enumerable (TM)
Type-1 Context-Sensitive ∣α∣≤∣β∣|\alpha| \le |\beta|, α→β\alpha \rightarrow \beta with context CSL (LBA)
Type-2 Context-Free A→γA \rightarrow \gamma, A∈VA\in V CFL (PDA)
Type-3 Regular A→aB∣aA \rightarrow aB \mid a, A→aA\rightarrow a Regular (FA)
  • (i) Regular → Type-3 ✓
  • (ii) Context-Free → Type-2 ✓
  • (iii) Context-Sensitive → Type-1 ✓

All three are in Chomsky hierarchy (Type-0 is the super-set).

Final Answer

All are types → Option (iv) All of the above.

Similar questions

AI LearningWeb Platform

Coursify — Personal AI Course Generator

Struggling with a difficult subject or concept? Turn any engineering topic into a structured course with interactive lessons, quizzes, and research-backed explanations.