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

## Tuesday, April 3, 2012

### Summer Research Grant

So back in a couple of months ago I wrote a grant to Norwich University for a summer research project. It was for an Intrusion Prevention System (IPS) that will be implemented on Brain-Computer Interfaces (BCI). Basically it is so that as humans interface more directly with computers using their brains, this IPS will prevent malicious programs (or people) from compromising their intellectual integrity (eg. monitoring their thoughts, controlling their actions, even killing them).

I was really concerned that I wouldn't get the grant, because it's very technical and kind of futuristic, and the people on the board are not at all technical and usually only approve projects that have applications at this point in time. I worked very hard (and got a lot of great help from Dad) to write it in a way that was easy to understand and showed that it was something that could be used in the near future.

And I guess it worked, because I just found out today that I got the grant! So now I'll be staying here at NU this summer for ten weeks after this semester finishes. The pay for the ten weeks is only \$4,000, and as this isn't as much as I could make elsewhere I am working on a second grant to DARPA that will provide me some additional funding, as well as funding to purchase some equipment that the project will require. The professor advising me on this project and myself are fairly certain I'll get the DARPA grant, as they are technical people and this is something they would be very interested in. As part of this research project I'll be writing an in-depth research paper that I hope to have accepted to a conference in this field, which would be a great opportunity.

So yeah! I'm very happy. I worked really hard on the grant, and I'm glad it paid off. I really wanted to spend my summer doing something relating to my field, and I'm glad God has blessed me with this opportunity.

Hope all is well,
Saul