Skip to main content
Software Engineering

Return to Question

edited body
Source Link
user4951
user4951
  • 719
  • 6
  • 14
.*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 .*?*foofoo and .+*foo*+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.

.*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.

.*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.

Source Link
user4951
user4951
  • 719
  • 6
  • 14

What would be an actual DFA/actual regex engine solve this simple regex pattern?

.*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.