Implementing a Deterministic Finite Automaton

So I recently started a new project I trivially named “adnumata” because well, it’s the name of my school and I am not a very creative person when it comes to naming. My plan is to create an Automata Theory library that incorporates everything from Finite Automata to Turing Machines(I know… They’re from Computability Theory but to hell with it). It’s also to test my Haskell skills since this is the largest project that I had done with Haskell so far. I’ve also gained new skills from this first iteration such as Travis-CI and Unit Testing using HUnit(Another xUnit… I know).

Design Decisions

I used Stack to manage my project. So basically, I contemplated whether I use newtype for DFA and another newtype for the Non-deterministic Finite Automaton. But I figured, I’ll be extremely verbose and would feel like I’m coding in Java if I do that so I just crunched both DFA and NFA as Algebraic Data Types(ADT) and let Haskell determine which one I want to use. For other automaton such as Context-Free Grammar and maybe even Cellular Automata, if I understand it enough by then, I’ll create new abstractions for them. As of now, the ADT for Finite Automata is as follows:

data FiniteAutomata = DFA { states :: [String]
                          , alphabet :: [String]
                          , transition :: Transition (Map (String, String) String)
                          , initialState :: String
                          , acceptStates :: [String]
                          }
                    | NFA { states :: [String]
                          , alphabet :: [String]
                          , transition :: Transition (Map (String, String) [String])
                          , initialState :: String
                          , acceptStates :: [String]
                          }

They basically just differ on the transition function where it maps to a set of strings(or a list of strings in this case).

Future Plans

For now, I intend to allow user inputs since my program is still pure. But that means I have to deal with impure code(yuck) and that’s something I’ve never done(fully separating impure code from pure code). Since I have an imperative programming background where I’ve done impure programming all my coding life, I think this will be a nice skill to learn.

After that, I can probably proceed on implementing Non-deterministic finite automata. And then create functions to convert DFAs to NFAs automatically. Also, I hope to integrate basic Automata Theory theorems as functions that can be called using user inputs.

That’s all for now.