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?
- A.
\(𝐿_1⊆𝐿_2⊆𝐿_3⊆𝐿_4\) - B.
\(𝐿_2⊆𝐿_1⊆𝐿_3⊆𝐿_4\) - C.
\(𝐿_1⊆𝐿_2⊆𝐿_4⊆𝐿_3\) - D.
\(𝐿_2⊆𝐿_1⊆𝐿_4⊆𝐿_3\)
Attempted by 92 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.