3
$\begingroup$

E.g.

Matching Problem The DFA of regex good is like a chain.

match:     "good"
not match: "people do not give good comments are not good people"

Searching Problem The DFA used in searching regex good could be:

enter image description here

1 matching:  "good"
2 matchings: "people do not give good comments are not good people"

Here are the questions:

  1. In the above two problems, it seems the searching problem's DFA is the matching problem's DFA plus some backedges and an additional state (here state 0). Is this the difference in general?
  2. What is the regex of searching problem in this case?
$\endgroup$

migrated from stackoverflow.com Mar 20 '13 at 2:34

This question came from our site for professional and enthusiast programmers.

  • $\begingroup$ This answer contains some related thoughts. $\endgroup$ – Raphael Mar 20 '13 at 11:09
3
$\begingroup$

This is true in general, in a way. Consider a regex $r$. You can construct a DFA (or NFA) for the matching problem. Denote this NFA by $A$.

To solve the searching problem, you can proceed in several ways. First, you can just solve the matching problem for the regex $\Sigma^*\cdot r\cdot \Sigma^*$.

Alternatively, you can construct an equivalent NFA for the latter regex. The form of such an NFA would be an initial state that guesses when $r$ starts (at which point there is a transition to the initial states of $A$), and every accepting state of $A$ moves to an accepting sink.

This NFA can be thought of as a generalization of the situation you describe. Indeed, when you determinize it, the equivalent DFA essentially tracks $r$, and whenever it fails the DFA "resets". This is not exact, since it strongly depends on $r$.

When $A$ is a chain, then indeed determinizing the NFA yields a DFA that follows the chain, and whenever there is a "mistake" (that is, $r$ is not met), it resets to the initial state. However, it could be that resetting might not go as far as the initial state. For example, when searching for $aba$, if you see $aa$, then the second $a$ should not reset all the way back, but rather to the second state, since the second $a$ may be the start of the regex's occurrence.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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