Let r = a(a + b)*, s = aa*b and t = a*b be three regular expressions. Consider:
(i) L(s) ⊆ L(r) and L(s) ⊆ L(t)
(ii) L(r) ⊆ L(s) and L(s) ⊆ L(t)
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: A. Only (i) is correct.
Explanation
s = a⁺b starts with a (so it is in r) and is a run of a's followed by b (so it is in t). But r contains 'a', which is not in s, so (ii) fails.
More Theory of Computation and Compilers questions
- Consider the language L = {a^(nk) | k > 0}, where n is a fixed non-negative integer. The minimum number of states of a finite automaton acc…
- The number of substrings that can be formed from a string given by a d e f b g h n m p is
- Consider the languages L₁ = {x | for some y with |y| = 2|x|, xy ∈ L} and L₂ = {x | for some y with |x| = |y|, xy ∈ L}, where L is a regular…
- Consider L₁ = {a^(n+m) bⁿ aᵐ | n, m ≥ 0} and L₂ = {a^(n+m) b^(n+m) a^(n+m) | n, m ≥ 0}. Which one is correct?
- Consider to be any regular language and L , L 1 2 be any two context-free languages. Which one of the following is correct?
- Consider the following problems : (i) Whether a finite state automaton halts on all inputs ? (ii) Whether a given context free language is…