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โ€ฆ

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

Loading lessonโ€ฆ