Wednesday, February 5, 2014

NFA to DFA Converter (Ruby)

Nondeterministic finite automata (NFAs) all have a deterministic counterpart, called a deterministic finite automata (DFA). Finding the DFA for an NFA is trivial for simple problems, however the problem quickly becomes difficult once more states and possible symbols are added. This program automates this process, not only for the purpose of checking homework problems, but also so that different methods of constructing DFAs can be tested (a future post will detail these findings).

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

The resulting NFA would look like:


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:
  1. Create a graph with the appropriate initial vertex.
  2. 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!




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