Deterministic Finite Automata (DFA)

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

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:

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
Ok, modules loaded: DFAsimple
ghci> evalDFA evenDFA "abbbabbbab"