Let L be a regular language and M is a dfa of L. build a dfa that acceptable all the prefix of every word in L
i think to make all the states are acceptable but the problem the new DFA willemphasized textaccept a words that not included in M
any tips or ideas ??
$\endgroup$1 Answer
$\begingroup$How careful you need to be depends on the form of your DFA. For example, if it is complete, then it has a sink state, and this one should not be made accepting, otherwise the new automaton accepts ALL words.
In general, every prefix corresponds to a path through the original automaton to some state, from which a final state can be reached. There might be more "useless" states (instead of one sink state) in the original DFA from which no final state can be reached, if this automaton is not normalized in any way. Then a reachability analysis should be done, and all states from which a final state can be reached should be made accepting in the new automaton. The original accepting states should remain accepting.
$\endgroup$
