Consider the regular expressions r = a(b + a)*, s = a(a + b)⁺, t = aa*b. Which relation holds between the languages they generate?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: B. L(r) ⊇ L(s) ⊇ L(t)
Explanation
r is every string starting with a; s is those of length at least 2; t (a⁺b) is a subset of those. So L(r) ⊇ L(s) ⊇ L(t).
More Theory of Computation and Compilers questions
- 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…
- Consider the following statements with respect L = {anbn ∣ n ≥ 0} to the language S : L2 1 is context free language S : Lk 2 is conext-free…