Setting up the frame

See previous post.  |  See next post.

First off, some definitions:

A DFA is formally defined as a 5-tuple (Q, S, d, q₀, F) where:

• Q is the set of all the states of the DFA
• S is the alphabet over which the DFA works
• d is the transition function. This is a very important part of the DFA as most of the information is encoded here. The result of the function d(s,q) is the state into which you move if you are in the state q and consume s.
• q₀ is the initial state
• F is the set of final states.

Similarly, a NFA is defined as (Q, S, d, q₀, F). All of the definitions are maintained as they were in the DFA. Two amendments are made, both of them to the transition function d:

• d can now accept e. This just represents an epsilon transition, which moves you to a state but does not consume a letter from the word you are reading.
• d will return a (possibly empty) set of states into which you move given a state and a symbol. The behaviour is different than that of a DFA as now you can have more than one active state at a given moment.

Since we'll be working in Haskell, let's think about the types of each element of the 5-tuple. Let the alphabet be of type ab and the states be represented by elements of type st. Then:

• Q is simply a set of states. We'll implement this as [st]
• S is the state of accepted symbols, that is type [ab]
• d needs a bit of care. It is a function which receives a symbol and a state and returns a state. That is: d :: ab → st → st.
• q₀ is a state, so just st
• F is a set of final states, so we'll implement it as [st]

Then the definition of a DFA over an alphabet [ab] that represents states as st is:

-- vocabulary, set of states, transition function, initial state, final states

data DFA st ab = DFA [ab] [st] (ab -> st -> st) st [st]

Note that DFA is both the name of the data type and the name of the constructor. This is clearer:

data DFA st ab = DFAconstructor [ab] [st] (ab -> st -> st) st [st]

However, I will be using the first definition.

Now to model the NFA: Things will pretty much stay the same, apart from the function which will require a bit of care. First of all, the function will return a set of states instead of a single state so:

d :: ab → st → [st]

gets us closer to our definition. The other amendment is that d also accepts e as a symbol. The best way to model this is to use the Maybe data type:

data Maybe a = Nothing | Just a

Then Just a will represent the symbol a and Nothing will represent the e symbol. Then:

-- vocabulary, set of states, transition function, initial state, final states

data NFA st ab = NFA [ab] [st] (Maybe ab -> st -> [st]) st [st]