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.
For example, considering this NDFSA Pattern:
| An NDFSA Pattern | its equivalent DFSA 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 {AB}.
- Find the valid successor arcs emanating from the starting vertices and terminating at the accepting vertices.
- Starting from vertex A, valid arcs are {AC} with input value [0].
- Starting from vertex B, valid arcs are {BC} and {BA, AC} with input values [1] and [1, 0] respectively.
- Merge the starting vertices, in this case, into {AB}.
- The remaining valid successor paths are {AC}, {BC} and {BA}.
- Construct 2 parallel finite-state paths starting from vertexes {AC} and {C} respectively following the starting vertex {AB}.
- Such that, AB --> AC and AB --> C.
- Each new starting vertex (whether {AC} or {C}) has their own valid paths.
- Valid successor paths for vertex {C} are the 0-successor paths {CB, CA} and the 1-successor path {CA} as determined by the NDFSA equivalent graph.
- Merge {CB, CA} into {ABC} with 2 successor paths, a 0-successor path and a 1-successor path pointing back to the vertex {AC} (one of the remaining vertexes).
- Vertex {C} finds its 0-successor path {AB} and its 1-successor path {C} to be compatible with the DFSA transition table.
- Vertex {AC} finds its 0-successor path {ABC} and its 1-successor path {A} to be compatible with the DFSA transition table.
- Vertex {A} finds its 0-successor path {C}, and since vertex {A} doesn't have an actual 1-successor path in the original transition graph, then it's replaced by a 1-successor path to a {φ} vertex aka. null or empty set.