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?
Answer: C. \(๐ฟ_1โ๐ฟ_2โ๐ฟ_4โ๐ฟ_3\) โ 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โฆ
- A.
\(๐ฟ_1โ๐ฟ_2โ๐ฟ_3โ๐ฟ_4\) - B.
\(๐ฟ_2โ๐ฟ_1โ๐ฟ_3โ๐ฟ_4\) - C.
\(๐ฟ_1โ๐ฟ_2โ๐ฟ_4โ๐ฟ_3\) - D.
\(๐ฟ_2โ๐ฟ_1โ๐ฟ_4โ๐ฟ_3\)
Attempted by 108 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 Computer Science Paper 2