Considering a language L, let L′ be the set of all first halves of strings in L so that
L′ ={x| for some y,|x|=|y|and xy ∈ L}
Please prove that if L is regular, then L′ is also regular by constructing a finite
automaton for L′.
I am having some difficulty tackling this problem. I've seen a few solutions but would like to have someone explain, in layman's terms, how this problem should be solved. I've reviewed the solution on problem 11 from the following link: http://tuvalu.santafe.edu/~moore/theory/hw1solns.pdf.
From my understanding, both a DFA for L and NFA for L' must be constructed, and within L' we track the final state of L as well as the backwards path from the final state. I appreciate the clarification.
For this proof, you don't have to construct a DFA for L. Your premise is that L is regular, so you know that there exists a DFA for L. Choose any, and now you can construct a NFA for L', by running your L DFA parallel to a copy of it that operates backwards.