Any string of terminals generated by the CFG S → XY, X → 0X | 1X | 0, Y → Y0 | Y1 | 0 (S is the start symbol)
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: D. has at least two 0's
Explanation
X always ends with 0 and Y always starts with 0, so every string contains at least two 0's. Strings like 00 show A and C fail, and 001 shows B fails.
More Theory of Computation and Compilers questions
- 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…
- 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…