Let 1 and 2 be languages over represented by the regular expressions (a∗ + b)∗ (a + b)∗ and respectively. Which of the following is true with respect to the two languages?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: C. L₁ = L₂
Explanation
(a* + b)* can produce any single a or b repeatedly, so it equals (a + b)* = all strings over {a, b}.
More Theory of Computation and Compilers questions
- Which of the following statements is true?
- Which of the following is not an intermediate code form?
- Which of the following are applications of symbol table? (A) Storage allocation (B) Checking type compatability (C) Suppressing duplicate e…
- 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)?…
- 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…