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 language, B. Recursive language, C. Context-free language. List II: I. complement(L_REC) ∪ L_RE, II. complement(L_CF) ∪ L_REC, III. L_R* ∩ L_CF.
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: C. A-I, B-II, C-III
Explanation
The complement of a recursive language is recursive, and its union with an RE language is RE. A CFL's complement is recursive, so its union with a recursive language is recursive. A regular language (closed under star) intersected with a CFL is context-free.
More Theory of Computation and Compilers questions
- 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…
- Which grammar generates L = {aⁿbⁿ⁻³ | n > 2} over Σ = {a, b}?
- Consider the following grammar : S → 0A ∣ 0BB A → 00A ∣ λ B → 1B ∣ 11C C → B Which language does this grammar generate?
- Let Σ = {w, x} and T = {x, y, z}, with homomorphism h(x) = xzy and h(w) = zxyy. If L is denoted by r = (w + x*)(ww)*, then h(L) is denoted…