Yesterday I saw there was a discussion of the following problem, which I'm interested in too:
Given that L is a regular language, construct a DFA for L-pref, where L-pref is defined as follows:
L-pref = {w | at most one prefix of w is not in L}
I've read the solution suggested here,
How to build a DFA for the given language and prove its correctness?
but I don't understand the solution entirely. I understand the case where epsilon belongs to L, but I don't understand the solution in the case in which epsilon doesn't belong to L (i.e the two machine copies thing).
I'd be glad if you could explain how to transition between the two copies, preferably referring to an example of an accepting run of a word and a non-accepting run of some other word.
Thanks!
I will use the same notation as in that answer.
Any transition in $M$ that goes to a non-acceptor state should be changed to go to the corresponding state in $M'$. That means that when $M$ first finds a prefix that is not in $L$, the automaton shifts over to $M'$. Similarly, any transition in $M'$ that goes to a non-acceptor state is changed to go to the ‘garbage’ state $q^*$; this ensures that a second prefix not in $L$ sends the automaton to $q^*$, where it remains forever in a non-acceptor state.
Remember that $M'$ starts out as an exact copy of $M$, except that we don’t care which state is $M$’s initial state. Thus, an input word in $L_{\text{pref}}$ affects the new automaton almost exactly as it affects $M$: the only difference is that if it has one non-$L$ prefix, the new automaton jumps over to $M'$ when that is found and continues its route in that copy of $M$ instead of in $M$ itself. And the adjustments to $M_1$ ensure that a second non-$L$ prefix will dump the new automaton into the ‘garbage’ state.