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?
.*foo, and it's variant
.*+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.