Let L be any language. Define even (W) as the strings obtained by extracting…
2014
Let L be any language. Define even (W) as the strings obtained by extracting from W the letters in the even-numbered positions and even(L) = {even (W) | W ∈ L}. We define another language Chop (L) by removing the two leftmost symbols of every string in L given by Chop(L) = {W | ν W ∈ L, with | ν | = 2}.
If L is regular language then
- A.
even(L) is regular and Chop(L) is not regular.
- B.
Both even(L) and Chop(L) are regular.
- C.
even(L) is not regular and Chop(L) is regular.
- D.
Both even(L) and Chop(L) are not regular.
Attempted by 26 students.
Show answer & explanation
Correct answer: B
Answer: Both even(L) and Chop(L) are regular.
Reason for Chop(L):
By definition, Chop(L) = { w | there exists a string u of length 2 with u w ∈ L }.
Thus Chop(L) = ⋃_{u of length 2} u^{-1}L. For any fixed string u, the left quotient u^{-1}L is regular when L is regular. The set of length-2 strings over a finite alphabet is finite, so this is a finite union of regular languages, hence regular.
Reason for even(L):
The mapping even(·) that takes a string and keeps only the letters in even positions can be implemented by a finite-state (sequential) transducer: the device has two states (odd and even). On reading a symbol in the odd state it does not output and moves to the even state; on reading a symbol in the even state it outputs that symbol and moves back to the odd state.
Applying this finite-state transduction to a regular language produces a regular language (images of regular languages under such finite-state transducers are regular). Equivalently, one can construct an NFA/DFA that simulates the original automaton while consuming input in pairs and outputting only the second symbol of each pair, yielding regularity.
Therefore, if L is regular then both even(L) and Chop(L) are regular.