We proved that if L can be recognized by a DFA then the language lefthalf(L) = {x ∈ Σ*|∃y xy ∈ L and |x| = |y|} is also regular; here |x| means the length of x. Suppose that L is regular then show that middle - thirds(L) = {x|∃y, z such that |x| = |y| = |z| and yxz ∈ L}
is also regular. You should assume that you are given a DFA to recognize L and you should describe - in terms of the given machine - how you would construct a new machine to recognize middle - thirds(L). Your new machine does not have to be a DFA of course, it could be an NFA. However, you may ?nd it amusing to make de?ne a DFA directly. You need not prove that your machine is correct. Marks will be deducted for a solution that is clumsy and hard to understand even if it is correct.