0
.*foo

Academically, that is a regular expression. A string aaaaaaaaaaaaafoo will match that. Also string aaaaaaaaaaaaafooaaaaafoo will match that too.

I would imagine that an NFA that solve that will have 4 states. State 0 will have an arrow going back to itself. Then an arrow f going to state 1, o to state 2, and another o to state 3.

The NFA would keep looping through to state 0 before it magically uses it's psychic power to decide aha, now I am going to start looking for foo. However, I have a hard time understanding psychic computer.

What would be a DFA for that? I would imagine that the number of state would probably be 6. So a the DFA may contain a boolean variable whether you are still looping or still going. I still can't quite figure that out. So can anyone help me construct a DFA for that?

Also .*foo, and it's variant .*?foo and .*+foo are actual regular expression used nowadays in non academic sense.

How would an actual regex engine implement those 3 expressions? How close are those actual implementation to actual DFA? I mean I know real DFA don't look back. I also know that real regex engine do look back and forth.

For simplicity sake let's presume that the DFA can contains variable instead of just states. I think the states of DFA are just variable in memories anyway.

  • I think for the variants you may have intended .*?foo and .+foo as what you have are not valid regular expressions. – Morgen Nov 9 '15 at 14:35
  • what's the possesive form? .*+? – user4951 Nov 9 '15 at 14:40
  • I'm not sure what you mean by “possessive”, but if you mean “greedy”, that's the default behaviour. – Morgen Nov 9 '15 at 14:42
  • You may find this article on the quantifiers useful: rexegg.com/regex-quantifiers.html – Morgen Nov 9 '15 at 14:46
  • The source for Java's Pattern class is quite visible. Digging into the compile() method will tell you how its implemented. grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/… – user40980 Nov 9 '15 at 15:33
6

With a simple conversion you can change a NFA to a DFA by taking each state of the DFA as a subset of the NFA states. The transition function would take each State of the input and get the set of next states and make the union of all of them. This models the computer being in multiple states at the same time.

As a result Your 4 state NFA would result in a 4 state DFA.

  1. A starting state {s0}. It has a transition with f to the next state {s0, s1} and any other loops back to itself.

  2. a state {s0, s1}. It has a transition with o to the next state {s0,s2}, a transition with f to itself and any other will go back to {s0}.

  3. a state {s0,s2} It has a transition with o to the next state {s0, s3} a transition with f to {s0, s1} and any other will go back to {s0}.

  4. and a finishing state {s0,s3} with a transition with f to {s0, s1} and all others back to {s0}

More state combinations (a total of 2^4) are possible but none of the others are reachable from the starting state.

This is the method that a few regex engines use to avoid backtracking in the NFA constructed from the regex string though it won't be able to model capturing groups and backrefs. It is essentially a breath-first search into the NFA.

Other regex engines (most actually) basically do a depth-first search in the constructed NFA. Each time multiple options are available it will pick one and try that, if it fails then it backtrack to that decision and tries the other path. Which path it picks first is decided by the greediness modifier.

  • So that's how actual regex engine works. It creates an NFA but store states everytime it tries to "branch" out. Is this true? – user4951 Nov 9 '15 at 14:41
  • @JimThio how exactly it does its backtracking is an implementation detail. One way would be to push the state on a stack another would be to use recursion and use the application stack as the stack. – ratchet freak Nov 9 '15 at 14:53
  • so real regex engine uses stack. Interesting. Hmmm... Any references he he he he. – user4951 Nov 9 '15 at 15:52
  • @JimThio the Java compiled regular expression state machine and stack can be seen in the Pattern class. – user40980 Nov 9 '15 at 21:27
  • 1
    A practical article I like on this subject describes how the NFA of a regexp can be translated to instructions. The instructions are 'char c', 'match' 'jmp x' and 'split x,y'. The 'jmp x' instruction jumps to the label x. The 'split x,y' instruction jumps to both label x and label y. The article is here The article also describes a handful of interpreters for the instructions, in historic implementations. I myself branched off from it to write a glob matcher that implemented the characters of the glob pattern as the instructions. – cardiff space man Nov 9 '15 at 23:54

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.