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 language. Which one is correct?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: C. Both L₁ and L₂ are regular
Explanation
Regular languages are closed under 'first half' and 'first third' operations: run the DFA forward on x while guessing in parallel the states reachable by some suffix of length |x| (or 2|x|). Both are regular.
More Theory of Computation and Compilers questions
- 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…
- Which of the following problems is decidable for recursive languages L?
- Consider the grammar G: S → A | B, A → a | c, B → b | c, with non-terminals {S, A, B} and terminals {a, b, c}. S₁: LR(1) can parse all stri…
- The grammar S → (S) | SS | ε is not suitable for predictive parsing because the grammar is