Converting from NDFSA to DFSA
Both NDFSA and DFSA have identical computational capabilities and conversion between them is possible.
Hints:
- To convert from NDFSA to DFSA, one needs to know the pattern that is recognized by this NDFSA, hence building a new DFSA that recognizes this pattern is the way to go.
- To convert from NDFSA to DFSA, it's possible to insert midway transition paths by introducing new midway states, by doing that, you can ensure a transition path (successor path with the same input between 2 successive states) will not repeat.
- Starting vertices could be merged in a single vertex, as well as the Terminating vertexes.
For example, considering this NDFSA Pattern:
- The tabulation form of this NDFSA can be described as follows:
| Vertex | 0-Successor path emanating and ending at | 1-Successor path emanating and ending at |
|---|---|---|
| A | C | - |
| B | - | AC |
| C | AB | A |
- Conversion to a DFSA:
- Find the starting vertices and the accepting (terminating) vertices.
In this case:
- Vertex A and Vertex B are both starting vertices, the final merge is vertex {A, B}.
- Find the valid successor arcs emanating from the starting vertices and terminating at the accepting vertices.