Suppose I have a finite automaton to match a simple string "abc" and I built some software around it to not only match the start of a string or a full incoming string, but rather to search through a string and find the first match. As an example consider the string to be "12abcxxx".
The naive approach is to start with reading the '1' and trying a transition in the automaton. It fails. So we advance the input and try again, with `2'. Fail again. Now read 'a', 'b', 'c' nicely transition though the automaton, reach the stop state, store it, read 'x', fail and declare a match for the latest stop state we ran through.
If we assume that every 'fail' in this algorithm is inefficient, while transitions through the automaton are fast, an improvement would be to extend the automaton such that it matches either 'abc' or '[^a]+' and mark the different stop states as 'found abc' and 'not found abc'. Then '123' would be a match, supposedly much faster then three fails to skip over.
But adding '[^a]+' is not the only optimization. We could even add something like '([^a]|a[^b]|ab[^c])+' (which is not completely correct) to the automaton to skip over the non-matching sequences quickly.
Question: Working with a finite automaton that allows to mark stop states with different markers, and given an automaton for a regular expression re
, is it possible to "complete" the automaton such that it implements the quick skip over non-matching substrings as described informally above.
If it is possible, what would be the operation to perform either on the regular expression or an NFA or DFA representation? I would expect the result to talk about something like the complement set of the prefix set recognized by the original automaton.
Question rephrased: Reading the first answer I realized that the question is equivalent to the following: Given a regular language $L$, is there a regular language $L_p$ that satisfies the following: For all strings $s\in\Sigma^*$, $L_p$ shall contain the prefix of $s$ that ends just before an $s_x\in L$ or the complete $s$ if no such substring exists.