I will talk briefly about how I've accomplished this, but first a little about NFAs and DFAs.

NFAs are finite state machines used to determine if a given input is accepted or rejected. They are defined formally as

M = (Q, sigma, delta, q0, {F})

Where

- Q = states within the NFA (nodes)
- sigma = machine alphabet (possible symbols)
- delta = transitions between states (edges)
- q0 = initial state (starting point)
- {F} = set of possible ending states (end points)

Note: DFA's follow basically the same definition, except ...

Here's an example of a possible NFA: M = ({q0, q1}, {0,1}, delta, q1, {q0}) where delta is defined as:

-----------------------------------

delta*(q0,0) = q0

delta*(q0, lambda) = q1

delta*(q0, 1) = q1

delta*(q1, 0) = q0

-----------------------------------

This NFA would accept strings like 01, 011, 000 and so on.

The goal of the program is to turn this NFA into its corresponding DFA. The program does this by following what is called a "proof by construction," which shows that for every NFA there exists a DFA. The proof is (roughly) as follows:

- Create a graph with the appropriate initial vertex.
- Repeat the following steps until the number of edges leaving each vertex equals the carnality of the alphabet:
- Take any vertex that is missing an edge for a in sigma.
- If delta*(qi, a) ... U ... delta*(qk, a) is an element of the power-set of Q, add an edge from qi to qk labeled a.

That is basically what this program does. The NFA would be fed in as a CSV like so:

q0,q0,0

q0,q1,l

q0,q1,1

q1,q0,0

(with a few proceeding lines for initial state, etc.) and produces the following DFA:

Unfortunately this graph doesn't indicate which are initial/final states, but that will come soon (hopefully).

Here's a really crazy example of a DFA it churned out!

Here's a really crazy example of a DFA it churned out!

The source for this project is available under MIT license here: https://bitbucket.org/saulcosta18/nfa_to_dfa

DISCLAIMER: this code is still very rough!

Feel free to comment with questions/comments.

Cheers!

## No comments:

## Post a Comment