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:

Answer: A. (C), (A), (B), (D) — Answer: Regular languages < Context-free languages < Context-sensitive languages < Unrestricted grammars (recursively enumerable languages). Why this order is…

  1. A.

    (C), (A), (B), (D)

  2. B.

    (C), (A), (D), (B)

  3. C.

    (A), (C), (B), (D)

  4. D.

    (A), (D), (B), (C)

Attempted by 176 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.

Explore the full course: Mppsc Assistant Professor Computer Science Paper 2

Loading lesson…