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} and any other will go back to {s0}.

4. and a finishing state {s0,s3}. with all transitions 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.

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.

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} and any other will go back to {s0}.

4. and a finishing state {s0,s3}. with all transitions 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.

Other regex engines (most actually) basically to 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.

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} and any other will go back to {s0}.

4. and a finishing state {s0,s3}. with all transitions 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.