How to build a DFA for the given language and prove its correctness? Let's say $L$ is a regular language.
(reminder: the word $x$ is a $\text{Prefix}$ of the word $w$ if: $w=xy$, for some $y$ $\in$ $\Sigma^*$)
$L_{pref} = \{w | \text{ at most  $1$ prefix of $w$ is not in } L\}$
I need to build a DFA for $L_{pref}$ and prove its correctness.
I tried everything :(
Any ideas?
 A: HINT: Let $M$ be a DFA for $L$, and add a new state $q^*$ that is not in $M$. If $\epsilon\notin L$, every word over $\Sigma$ already has a prefix not in $L$, so one more ‘bad’ prefix takes it out of $L_{\text{pref}}$. Modify $M$ as follows: if $q\overset{a}\longrightarrow q'$ is a transition of $M$ such that $q'$ is not an acceptor state, replace it with $q\overset{a}\longrightarrow q^*$, and let $q^*$ be a non-acceptor state with transitions $q\overset{a}\longrightarrow q^*$ for every $a\in\Sigma$. The resulting DFA will accept $w\in\Sigma^*$ if and only if $\epsilon$ is the only prefix of $w$ that is not in $L$.
If $\epsilon$ is in $L$, a word $w\in\Sigma$ has to drive $M$ to non-acceptor states twice in order to be rejected. See if you can design a suitable DFA by adding to $M$ not just the ‘garbage’ state $q^*$ but also a whole second copy $M'$ of $M$. The idea is that the machine should stay in the original $M$ as long as the input keeps it in acceptor states but switch to $M'$ when the input sends it to a non-acceptor state.
