Deterministic Finite Automata in Haskell

Consider the deterministic finite automaton [1] illustrated below

[ state diagram courtesy of Michael Sipser [1] ]

Henceforth, we will call this automaton . Note that has three states, labeled , , and . The start state is (note the arrow coming from nowhere) and the accept state is (note the double circle). There are two possible inputs, labeled and , and, depending on the input, the automaton will jump from one state to another. In the diagram above these state transitions are depicted using arrows connecting two states.

Suppose that the automaton receives an input string such as (which the automaton reads from left to right). Since the start state is and the first input symbol is , the automaton will jump to state . The second input symbol is , so the automaton will remain at . The automaton reads the third input symbol, which is , and then jumps from state to state . The last input symbol is and thus the automaton jumps from state to state . Hence, the state sequence corresponding to the input string is the following

After reading the last symbol in the input string, produces an output. Since the final state is the accept state, we have that the automaton produces the output “accept”. Were the final state not , the automaton would produce the output “reject”. We conclude that this automaton accepts the input string . What other input strings does accept? Michael Sipser answers this question in [1]:

Experimenting with this machine on a variety of input strings reveals that it accepts the strings , , , and . In fact, accepts any string that ends with a , as it goes to its accept state whenever it reads the symbol . In addition, it accepts strings , , , and , and any string that ends with an even number of s following the last . It rejects other strings, such as , , .

A set of strings is called a language [1]. The set of all input strings accepted by the deterministic finite automaton is a language which we denote by .

__________

Formal definition

A deterministic finite automaton (DFA) consists of a finite set of states , a finite input alphabet that tells us what the allowed input symbols are, a transition function  that tells us how to jump from one state to another, a start state , and a set of accept states . A deterministic finite automaton (DFA) is thus a -tuple of the form

The deterministic finite automaton which we discussed earlier in this post is defined formally as follows

where the transition function is defined enumeratively as

,        ,       

,        ,       

Alternatively, we could view each state transition as an ordered triple , which might be easier to implement in some programming languages.

__________

Computing state sequences

Given an input string over a given alphabet , how do we obtain the corresponding state sequence? I solved that problem last January. I will not repeat myself here, but the crux of the matter is that the final state can be obtained using a left-fold

whereas the entire state sequence can be computed using a left-scan

Lacking a better name, I called this procedure the “scanl trick“, as I used the Haskell function scanl to implement it. Please let me know if you find a more sophisticated name for this “trick”.

__________

Haskell implementation of the DFA

Without further ado, here is a Haskell script:

data State = Q1 | Q2 | Q3 deriving (Read, Show, Eq)

type Input = Integer

-- define state-transition function
delta :: State -> Input -> State
delta Q1 0 = Q1
delta Q1 1 = Q2
delta Q2 0 = Q3
delta Q2 1 = Q2
delta Q3 0 = Q2
delta Q3 1 = Q2
delta  _ _ = error "Invalid input!"

-- define initial state
initialstate :: State
initialstate = Q1

-- create list of accept states
acceptstates :: [State]
acceptstates = [Q2]

-- create infinite list of input sequences
inputss :: [[Input]]
inputss = concat $ iterate g [[]]
          where g = concat . map (\xs -> [ xs ++ [s] | s <- [0,1]])

-- create accept predicate
isAccepted :: [Input] -> Bool
isAccepted inputs = finalstate `elem` acceptstates
                    where finalstate = foldl delta initialstate inputs

-- compute language recognized by the DFA
language :: [[Input]]
language = filter isAccepted inputss

Some remarks about this script are in order. Please note that:

• Sets are represented by lists. Strings are represented by lists, too. The latter is more natural than the former. Sets of strings become lists of lists.

• A new data type is created to represent the states, which we denote by Q1, Q2, and Q3. The input symbols are integers.

• Note that Input is a type synonym, inputs is a list of inputs symbols (i.e., an input string), and inputss is a list of lists of inputs (i.e., a list of input strings). Yes, it is a bit confusing.

• Note also that inputss is generated using the procedure I blogged about yesterday where the alphabet is .

• The final state is computed using the higher-order function foldl (left-fold). We check if the final state is an accept state using  the list membership predicate elem.

If you have any objections to this script, please do let me know. Let us now test it! We load it into GHCi and voilà:

*Main> -- check list of input strings
*Main> take 31 $ inputss
[[],[0],[1],
 [0,0],[0,1],[1,0],[1,1],
 [0,0,0],[0,0,1],[0,1,0],[0,1,1],
 [1,0,0],[1,0,1],[1,1,0],[1,1,1],
 [0,0,0,0],[0,0,0,1],[0,0,1,0],[0,0,1,1],
 [0,1,0,0],[0,1,0,1],[0,1,1,0],[0,1,1,1],
 [1,0,0,0],[1,0,0,1],[1,0,1,0],[1,0,1,1],
 [1,1,0,0],[1,1,0,1],[1,1,1,0],[1,1,1,1]]
*Main> -- compute the language of the automaton
*Main> -- (let us extract some 40 input strings only)
*Main> take 40 language
[[1],[0,1],[1,1],
 [0,0,1],[0,1,1],[1,0,0],[1,0,1],[1,1,1],
 [0,0,0,1],[0,0,1,1],[0,1,0,0],[0,1,0,1],
 [0,1,1,1],[1,0,0,1],[1,0,1,1],[1,1,0,0],
 [1,1,0,1],[1,1,1,1],[0,0,0,0,1],[0,0,0,1,1],
 [0,0,1,0,0],[0,0,1,0,1],[0,0,1,1,1],[0,1,0,0,1],
 [0,1,0,1,1],[0,1,1,0,0],[0,1,1,0,1],[0,1,1,1,1],
 [1,0,0,0,0],[1,0,0,0,1],[1,0,0,1,1],[1,0,1,0,0],
 [1,0,1,0,1],[1,0,1,1,1],[1,1,0,0,1],[1,1,0,1,1],
 [1,1,1,0,0],[1,1,1,0,1],[1,1,1,1,1],[0,0,0,0,0,1]]

The list of input strings is exactly the same I posted yesterday. The input strings in the language , or, to put it more precisely, the input strings in that are displayed above either end with a , or end “with an even number of s following the last “, as mentioned by Sipser in [1]. Why is that? The last in the input string puts in state , and an even number of s after that lead to transitions from to and back to , e.g.,

or

or

It would also be interesting to take a look at the state sequences corresponding to the input strings in . We compute these state sequences using the infamous “scanl trick“:

*Main> -- create list of sequences of states
*Main> let statess = map (\xs -> scanl delta initialstate xs) language
*Main> -- take the "first" 20 state sequences
*Main> take 20 statess
[[Q1,Q2],[Q1,Q1,Q2],[Q1,Q2,Q2],
 [Q1,Q1,Q1,Q2],[Q1,Q1,Q2,Q2],[Q1,Q2,Q3,Q2],
 [Q1,Q2,Q3,Q2],[Q1,Q2,Q2,Q2],[Q1,Q1,Q1,Q1,Q2],
 [Q1,Q1,Q1,Q2,Q2],[Q1,Q1,Q2,Q3,Q2],[Q1,Q1,Q2,Q3,Q2],
 [Q1,Q1,Q2,Q2,Q2],[Q1,Q2,Q3,Q2,Q2],[Q1,Q2,Q3,Q2,Q2],
 [Q1,Q2,Q2,Q3,Q2],[Q1,Q2,Q2,Q3,Q2],[Q1,Q2,Q2,Q2,Q2],
 [Q1,Q1,Q1,Q1,Q1,Q2],[Q1,Q1,Q1,Q1,Q2,Q2]]

Note that all state trajectories end in state Q2, as we expected.

__________

References

[1] Michael Sipser, Introduction to the Theory of Computation (2nd edition), Thomson Course Technology, 2006.