Skip to content

Latest commit

 

History

History
55 lines (40 loc) · 1.84 KB

README.md

File metadata and controls

55 lines (40 loc) · 1.84 KB
Raw

automata

The goal of this package is to enable simple and fast simulation and visualization of finite automata.

Currently I have a (maybe) working implementation of DFA and NFA simulation. Please excues the messy code, this project is still under heavy development and changing rapidly.

DFA & NFA Simulation

My goals for this package are:

  • Make creating simple DFAs and NFAs easy enough (not there yet)

  • Check user input DFAs and NFAs for validity (haven't started this one)

  • Make it easy to combine and modify DFAs and NFAs, examples being:

    • Intersection (done)
    • Reversal (done)
    • Union (easy to do)
    • Concatenation (just as easy to do)
    • Other transformations (I have to think of them first)

  • Make the interface general enough to be useful.

I think I am a good way towards my goal, although I may have over-engineered the types a bit.

One of the best design decisions I made‒in my opinion—is to represent the transition function as arbitrary arrows.

dfaTransition :: ArrowChoice ar => ar (state, alphabet) -> state
nfaTransition :: ArrowChoice ar => ar (state, Maybe alphabet) -> Set state

The NFA transition takes a Maybe alphabet to handle epsilon-transitions. This representation allows me to embed debugging/error-handling code into the transition function. For instance, I can use a Kleisli arrow to embed an Either or Maybe monad and have my transition function that returns an error message for unreachable states:

data S = Q0 | Q1 | QReserved

delta Q0 _ = Right Q1
delta Q1 _ = Right Q0
delta q  c = Left (q,c)

transitionFunction = Kleisli (uncurry delta)

I could also use it to log information in the same way by embedding the IO monad. An example of this is in examples/fizzbuzz.hs, where I use the intersection of two DFAs to pass the FizzBuzz challenge.