Let G1 and G2 be arbitrary context-free grammars and R an arbitrary regular language. Which problems are undecidable? (A) Is L(G1) = L(G2)? (B) Is L(G2) ⊆ L(G1)? (C) Is L(G1) = R?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: D. (A), (B) and (C)
Explanation
Equivalence and containment of CFLs are undecidable, and so is equality with a regular language (taking R = Σ* gives the undecidable universality problem).
More Theory of Computation and Compilers questions
- Consider L1 = {a^(z²) | z is an integer}, L2 = {a^(2z) | z ≥ 0}, L3 = {ωω | ω ∈ {a, b}*}. Which of the languages is (are) regular?
- Which of the following grammars is (are) ambiguous? (A) S → SS | aSb | bSa | λ (B) S → aSbS | bSaS | λ (C) S → aAB, A → bBb, B → A | λ, whe…
- Match List I with List II (L_R regular, L_CF context-free, L_REC recursive, L_RE recursively enumerable). List I: A. Recursively enumerable…
- Consider the regular expressions r = a(b + a)*, s = a(a + b)⁺, t = aa*b. Which relation holds between the languages they generate?
- Given below are two statements: L ∧ L = ϕ Statement I : The problem "Is 1 2 ? " is L undecidable for context sensitive languages 1 L and 2.…
- Consider the following grammars : G : S → aSb|bSa|aa 1 G : S → aSb|bSa|SS ∣ λ 2 G : S → aSb|bSa|SS ∣ a 3 G : S → aSb|bSa|SS|SSS|λ 4 Which o…