Arrange the following Language Classes in ascending order according to their…
2024
Arrange the following Language Classes in ascending order according to their expressive power, as defined by Chomsky hierarchy:
(A) Context-free languages
(B) Context-sensitive languages
(C) Regular languages
(D) Unrestricted Grammars
Choose the correct answer from the options given below:
- A.
(C), (A), (B), (D)
- B.
(C), (A), (D), (B)
- C.
(A), (C), (B), (D)
- D.
(A), (D), (B), (C)
Attempted by 141 students.
Show answer & explanation
Correct answer: A
Answer: Regular languages < Context-free languages < Context-sensitive languages < Unrestricted grammars (recursively enumerable languages).
Why this order is correct:
Regular languages: recognized by finite automata; all regular languages are context-free.
Context-free languages: generated by context-free grammars / recognized by pushdown automata; there are context-free languages that are not regular, so context-free strictly contains regular.
Context-sensitive languages: recognized by linear bounded automata; they strictly include context-free languages (for example, {a^n b^n c^n} is context-sensitive but not context-free).
Unrestricted grammars (recursively enumerable languages): the most general class generated by unrestricted grammars / recognized by Turing machines; they include all context-sensitive languages.
Thus the ascending order from least to most expressive is: Regular, Context-free, Context-sensitive, Unrestricted grammars.
A video solution is available for this question — log in and enroll to watch it.