Given the recursively enumerable language (LRE), the context sensitive…

2014

Given the recursively enumerable language (LRE), the context sensitive language (LCS), the recursive language (LREC), the context free language (LCF) and deterministic context free language (LDCF). The relationship between these families is given by

  1. A.

    LCF ⊆ LDCF ⊆ LCS ⊆ LRE ⊆ LREC

  2. B.

    LCF ⊆ LDCF ⊆ LCS ⊆ LREC ⊆ LRE

  3. C.

    LDCF ⊆ LCF ⊆ LCS ⊆ LRE ⊆ LREC

  4. D.

    LDCF ⊆ LCF ⊆ LCS ⊆ LREC ⊆ LRE

Attempted by 126 students.

Show answer & explanation

Correct answer: D

Correct relationship: Deterministic context-free ⊆ Context-free ⊆ Context-sensitive ⊆ Recursive ⊆ Recursively enumerable

  • Deterministic context-free ⊆ Context-free: every deterministic pushdown automaton is a pushdown automaton, so every deterministic context-free language is context-free. There exist context-free languages that are not deterministic context-free (for example, certain palindrome languages).

  • Context-free ⊆ Context-sensitive: any context-free language can be generated by a context-sensitive grammar, and there are context-sensitive languages that are not context-free (for example, {a^n b^n c^n}).

  • Context-sensitive ⊆ Recursive: context-sensitive languages are exactly those decided by linear-bounded automata, which always halt, so every context-sensitive language is recursive (decidable).

  • Recursive ⊆ Recursively enumerable: every decider is also a recognizer, so every recursive language is recursively enumerable. There are recursively enumerable languages that are not recursive (for example, the halting problem).

Therefore the correct ordering from smallest to largest is: Deterministic context-free ⊆ Context-free ⊆ Context-sensitive ⊆ Recursive ⊆ Recursively enumerable

A video solution is available for this question — log in and enroll to watch it.

Explore the full course: Mppsc Assistant Professor