Consider the following language families: 𝐿1≑ The context-free languages 𝐿2≑…

2019

Consider the following language families:

𝐿1≑ The context-free languages

𝐿2≑ The context-sensitive languages

𝐿3≑ The recursively enumerable languages

𝐿4≑ The recursive languages

Which one of the following options is correct?

  1. A.

    \(𝐿_1βŠ†πΏ_2βŠ†πΏ_3βŠ†πΏ_4\)

  2. B.

    \(𝐿_2βŠ†πΏ_1βŠ†πΏ_3βŠ†πΏ_4\)

  3. C.

    \(𝐿_1βŠ†πΏ_2βŠ†πΏ_4βŠ†πΏ_3\)

  4. D.

    \(𝐿_2βŠ†πΏ_1βŠ†πΏ_4βŠ†πΏ_3\)

Attempted by 78 students.

Show answer & explanation

Correct answer: C

Answer: L1 βŠ† L2 βŠ† L4 βŠ† L3

  • Context-free βŠ† Context-sensitive: Every context-free language can be generated by a context-sensitive grammar or recognized by a linear-bounded automaton simulated appropriately, so all context-free languages are context-sensitive.

  • Context-sensitive βŠ† Recursive (decidable): Languages accepted by linear-bounded automata are decidable (the machine always halts), so every context-sensitive language is recursive.

  • Recursive βŠ† Recursively enumerable: Any decidable language can be accepted by a Turing machine that halts on all inputs, therefore every recursive language is recursively enumerable.

Thus the correct inclusion chain is: context-free (L1) βŠ† context-sensitive (L2) βŠ† recursive (L4) βŠ† recursively enumerable (L3).

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

Explore the full course: Mppsc Assistant Professor