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 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.