If L₁ and L₂ are context-free languages, which one of the following is true about L₁ ∩ L₂?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: C. L₁ ∩ L₂ is recursively enumerable
Explanation
CFLs are not closed under intersection (aⁿbⁿcᵐ ∩ aᵐbⁿcⁿ = aⁿbⁿcⁿ), so A and B are not guaranteed. The intersection is always decidable, hence recursively enumerable, which is the keyed answer. (Strictly it is also context-sensitive, since CSLs are closed under intersection; the key takes the safest class, RE.)More Theory of Computation and Compilers questions
- Which of the following tasks could be attained using syntax trees in compiler design? (A) Type Checking (B) Code Generation (C) Code Optimi…
- Arrange the following stages of a Turing Machine (TM) operation in the correct order as they occur during computation. (A) Writing a symbol…
- Which of the following languages can be recognized by a Non-Deterministic Finite Automaton (NFA) but cannot be recognized by a Deterministi…
- Arrange the following phases in the correct order as they typically occur in the compilation process. (A) Lexical Analysis (B) Semantic Ana…
- Arrange the following language classes in ascending order of their expressive power, as defined by the Chomsky hierarchy: (A) Context-free…
- Which of the following are context-free languages? (A) {wⁱ xʲ yᵏ zˡ | i + k = j + l, where i, j, k, l ≥ 0} (B) {wⁱ xʲ yᵏ zˡ | i = j, k = l,…