1
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ It's not clear why you want to do this. Wouldn't it be simpler to modify the FA so that you can just run the input string through it and keep going until either the FA is in an accept state or you run out of input? Then you'd never encounter any of your 'fail' states, which seems to be the best solution. $\endgroup$
    – Rick Decker
    Dec 3, 2015 at 16:10
  • $\begingroup$ "modify the FA" how, is the question. $\endgroup$
    – Harald
    Dec 3, 2015 at 16:26
  • $\begingroup$ Just to clarify your rephrased question, if $s_x=abc$ then $ac$ could be in $L_p$ in two ways: from $s=ac$ or $s=acabc$, right? $\endgroup$
    – Rick Decker
    Dec 6, 2015 at 19:31
  • $\begingroup$ Yes. Whereby the first, $s=ac$, is less important for a the practical application I have in mind, so if it is in the way for a theoretical solution, it can be left out. $\endgroup$
    – Harald
    Dec 7, 2015 at 11:50
  • $\begingroup$ Your question reminds me of string searching algorithms such as Boyer-Moore and Knuth-Morris-Pratt. Isn't KMP-style skipping what you're trying to do? $\endgroup$
    – Gilles 'SO- stop being evil'
    Feb 22, 2016 at 1:10

2 Answers 2

Reset to default
3
$\begingroup$

Here is what I came up with finally. I need the following operations on finite automata, for automata a and b.

  1. allPrefixes(a) creates an automaton that matches all non-empty prefixes of the language L(a). The implementation is quite simple on a DFA. Make sure there are no useless states (those with no path to a stop state). Then make all states except the start state into stop states.
  2. invert(a) creates an automaton that matches the complement of L(a).
  3. asSubstring(a) creates an automaton that matches every string in $\Sigma^*$L(a)$\Sigma^*$.
  4. not(a) is a shortcut for invert(asSubstring(a)).
  5. or(a,b) is the automaton that recognizes L(a)$\cup$L(b).

Given an automaton a, the automaton which comes very close to what I was after is then easy to describe as c=or(a, not(allPrefixes(a)).

Remember that I want filtering, i.e. find a match, remove the matching input, find a match again and so on until end of input. The automaton c either matches my original a or all kinds of stuff that does not end in any prefix recognized by a. Except for a suffix of the input matching only a prefix of a, there will always be a prefix of the input being matched by c.

Improve this answer
$\endgroup$
0
2
$\begingroup$

Let's use your $abc$ example. Of course, the standard regexp-NFA construction yields a 3-state DFA for the language $\{abc\}$. What you want is a DFA which accepts every string represented by the regexp $\Sigma^*abc\Sigma^*$. The regexp-NFA construction yields a 4-state NFA with transition table $$\begin{array}{r|ccc} \delta & a & b & c & other\\ \hline q_0 & \{q_0,q_1\} & \{q_0\} & \{q_0\} & \{q_0\} \\ q_1 & \varnothing & \{q_2\} & \varnothing & \varnothing \\ q_2 & \varnothing & \varnothing & \{q_3\} & \varnothing \\ q_3 & \{q_3\} & \{q_3\} & \{q_3\} & \{q_3\} \\ \end{array}$$ where $other$ represents any symbol other than $a, b$, or $c$, $q_0$ is the start state, and $q_3$ is the final state. Using the standard NFA-to-DFA construction (and merging the 3 final states that result into one) we obtain a 4-state DFA with table $$\begin{array}{r|ccc} \delta & a & b & c & other\\ \hline p_0 & p_1 & p_0 & p_0 & p_0 \\ p_1 & p_1 & p_2 & p_0 & p_0 \\ p_2 & p_1 & p_0 & p_3 & p_0 \\ p_3 & p_3 & p_3 & p_3 & p_3 \\ \end{array}$$ where $p_0$ is the start state and $p_3$ is the final state. This DFA will take any input string and halt in a final state if the input string contains $abc$ as a substring. If we run out of input and are not in the final state, we know $abc$ does not appear in the input.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Not quite. I need a dfa that matches "everything up to 'abc'" or 'abc' to be able to jump to the 'abc' in a long text as fast as possible. My first attempt was invert(.*abc.*)|abc, where invert() inverts stop states into normal states and vice versa. We see your $\Sigma^*abc\Sigma^*$ appearing, but the problem is that invert(.*abc.*) matches .*ab, so using this to jump over non-matching stretches does not work, it would cut into the match. $\endgroup$
    – Harald
    Dec 6, 2015 at 13:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.