Let L1 = {0ⁿ1ⁿ0ᵐ | n ≥ 1, m ≥ 1}, L2 = {0ⁿ1ᵐ0ᵐ | n ≥ 1, m ≥ 1}, L3 = {0ⁿ1ⁿ0ⁿ | n ≥ 1}. Which are correct? A. L3 = L1 ∩ L2. B. L1 and L2 are context free but L3 is not. C. L1 and L2 are not context free but L3 is. D. L1 is a subset of L3.
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: A. A and B only
Explanation
Requiring both 0ⁿ1ⁿ and 1ᵐ0ᵐ forces all three counts equal, so L1 ∩ L2 = L3. L1 and L2 are CFLs; L3 is the classic non-CFL. So A and B.
More Theory of Computation and Compilers questions
- Given below are two statements Statement I: The family of context free languages is closed under homomorphism Statement II: The family of c…
- What is the minimum number of states required to the finite automaton equivalent to the transition diagram given below?
- Find the regular expression for the language accepted by the automata given below.
- What language is accepted by the PDA M = ({q0, q1, q2}, {a, b}, {a, b, z}, δ, q0, z, {q2}) where in q0 every input symbol is pushed, δ(q0,…
- Match List I (production rules) with List II (grammar). List I: A. S → XY, X → 0, Y → 1. B. S → aS | bSS | c. C. S → AB, A → 0A | 1A | 0, B…
- Which of the following concepts can be used to identify loops? A. Depth first ordering B. Dominators C. Reducible graphs