# Deterministic Finite Automata (DFA)

A Deterministic Finite Automaton (DFA) is defined as a 5-tuple (Q, Σ, δ, s, F) consisting of

• A finite set Q (the set of states)
• A finite set of symbols Σ (the input alphabet)
• A transition function δ: Q × Σ → Q mapping the current state q ∈ Q and input symbol a ∈ Σ to a new state δ(q, a)∈Q
• An initial state s ∈ Q (the start state)
• A set of accepting states F (the final states)

A DFA is a mathematical model of a simple computational device that reads a string of symbols (over the input alphabet Σ,) and either accepts or rejects the input string. We would like to turn this mathematical definion into a working program, so that we can run DFAs on our computer.

We define a data type corresponding to DFAs:

``````type State = Int
type DFA = ([State], [Char], State->Char->State, State, [State])``````

That’s it! Let us see how this data type corresponds to the mathematical definition. The first line defines `State` as a type synonym for `Int`, the haskell standard type for integer numbers. So, whenever we say that a variable `q` takes a value of type `State`, haskell will understand that `q` is an integer value. Giving a user defined name to the type of states is useful to make our programs more readable. The second line introduces another type synonym, `DFA`, the type we will use to represent DFAs. The type definition simply says that a DFA is a 5-tuple, and specifies the type of each component of the tuple:

• The first component has type `[State]`, i.e., it is a list of states. We do not really care about the order in which the states are given in this list. But ordered lists are generally easier to work with than unordered sets. So, we will generally use lists to represent sets of elements.
• The second component has type `[Char]`, i.e., it is a list of characters, the elements of the input alphabet.
• The third component is the transition function, and has type `State->Char->State`, i.e., it is a function that on input a `State` and a `Char`, outputs a `State`.
• The fourth component is just a `State`, the start state of the automaton
• The last component is a list of states, the final states of the automaton.

In order to do something with this definition, let us define an example automaton, e.g., an automaton with 2 states that accepts strings over the alphabet {a, b} of even length. The automaton is easily defined as a value of type `DFA`.

``````evenDFA :: DFA
evenDFA = (states, alphabet, delta, s, fs)
where states = [1,2]
alphabet = ['a','b']
s = 1
fs = [1]
delta 1 'a' = 2
delta 1 'b' = 2
delta 2 'a' = 1
delta 2 'b' = 1``````

We called our example automaton `evenDFA`. The first line is a type declaration, and it says that `evenDFA` has a value of type `DFA`. Type declarations are typically not necessary in haskell, as the compiler can automatically infer the type of all variables and functions, but including them in our programs is a good way to document them and make them more readable. The remaining lines say that `evenDFA` is a 5-tuple with components `states`, `alphabet`, `delta`, `s` and `fs`, and defines each of the components. These correspond to Q, Σ, δ, s and F from the mathematical definition. But because of haskell syntax conventions, all components must start with a lowercase letter, and we are not allowed to use any Greek. Notice how the transition function is defined as a set of equations `delta q1 a = q2`. You can think of it as defining the transitions by giving a table. Of course, there are often better ways to specify functions.

The definition of DFA given above specifies only the syntax of a finite automaton: it says what is, and what is not a DFA, but it does not really say anything about how a DFA carries out a computation. Of course, we have a pretty good intuitive idea of how computation should proceed, but still this needs to be formalized, both as a mathematical definition and as a computer program.

Recall that a DFA takes as input a string of characters, and either accepts or reject the input. So, we may represent the behavior of a DFA as a function of type `String -> Bool`. Here `String` is just a type synonym for `[Char]`, i.e., a list of characters, and `Bool` is the haskell type for the boolean values (`True` and `False`). Below we define a function `evalDFA` that on input a DFA outputs the function `String -> Bool` computed by the DFA. Alternatively, you can think of `evalDFA` as a function that, given a DFA and an input string, returns the accept/reject output of the DFA.

We first defined a function `extendDelta` that extends the the transition function δ : Q × Σ → Q of a DFA to take arbitrary strings as input, rather than a single alphabet symbol. The result of applying `extendDelta` to a transition function δ is the extended transition function denoted δ* : Q × Σ* → Q in the textbook.

``````extendDelta :: (State -> Char -> State) -> (State -> String -> State)
extendDelta delta = deltaStar
where deltaStar q [] = q
deltaStar q (a:w) = deltaStar (delta q a) w

evalDFA :: DFA -> String -> Bool
evalDFA (qs,alpha,delta,s,fs) w =
let deltaStar = extendDelta delta
q = deltaStar s w
in elem q fs``````

Using the extended transition function, `evalDFA` is easily defined: compute the state q = δ*(s, w) (where s is the start state, and w is the input string), and check if q is an element of the set F of final states.

As a side remark, the `extendDelta` function is such a common and useful programming pattern, that the Haskell standard library (the “Haskell Prelude”) already has a predefined function doing just that. You can find it using Hoogle. Just ask hoogle for a function of type `(Int -> Char -> Int) -> (Int -> [Char] -> Int)`, and you will find that the name of the function is `foldl`. So, we could have simply defined `extendDelta = foldl`, or used `foldl` directly in place of `extendDelta` in the definition of `evalDFA`.

You can find all the above definitions in the file DFAsimple.hs. (The file is also available on the school computers under \$PUBLIC/share/DFAsimple.hs. Let us try out our program from ghci:

``````ieng6\$ cp \$PUBLIC/share/DFAsimple.hs .
ieng6\$ ghci
...
ghci> :l DFAsimple.hs