Working with Finite Automata using Haskell

Most of the mathematical definitions and theorems studied in this course, have a direct translation into (useful) computer programs. For example, the mathematical definitions of DFAs and NFAs easily translate into corresponding data structures. The recursive definition of the function computed by a DFA is easily translated into a computer program that given a DFA and an input string, outputs True or False.

Translating mathematical definitions and theorems into computer programs is especially easy when using a high level programming language. Here we describe how to translate the definition associated to a DFA into a program written in the programming language haskell. These notes are a quick start guide to using haskell to work on finite state automata.

Get ready to run haskell

We have installed the haskell platform on the class directory. So, you can immediately compile and run haskell programs just by logging in your class account, and invoking the ghc compiler on the command line. (You can also invoke the interpreter by running ghci.) We will only use the most basic features of the language, explained in these notes. So, if you are not familiar with haskell, don't worry. You should be able to pick up all you need in just a few minutes, and you can always post questions on piazza. (Use the 'haskell' tag for questions about the language, and the tag 'hw2' etc. for questions specific to the homework.) You may also want to install haskell on your computer. It is freely available on a variety of operating systems, and it should be easy to install following the instructions here. In order to compile some programs, you may also need some additional packages (not included in the haskell platform), like the xml package which you can install with the commands cabal update, cabal install xml. See post @101 on piazza.

If you want to dig deeper into haskell, you can find plenty of documentation and other resources at haskell.org. For a good tutorial introduction to the language we recommend "Learn you a Haskell for Great Good!", but you may be able to get by just with what is written in these notes.

Some basics notation

If you are not familiar with any language in the haskell family, here are a few notes that may save you a few headaches. As a notational convention, we use this font when referring to haskell syntax, and use mathematical notation f(x²) to illustrate its meaning.

• Haskell is a functional programming language. Programs are written as functions f: X → Y that on input a value x ∈ X produce some other value f(x) ∈ Y.
• Function invocation is written without parentheses, i.e., as "f x" rather than "f(x)"
• Functions of several arguments (f: X × Y → Z) are usually curried, which means that f is written as a function that on input x ∈ X outputs, as a result, a function from Y to Z. So, formally f: X → (Y → Z). If you want to apply f to x and y, you first apply it to x, and then you apply the result f(x) to y. Since parentheses are not required, this is written simply as f x y
  
• Haskell is a typed language: every value has a corresponding type. To a large extent, you can think of types as sets of possible values that a given variable may take. The assertion that a given value has a certain type is written as value::type. You can think of v::T as the mathematical statement v ∈ T, i.e., the value v belongs to the set represented by the type T.
• Before any function definition, we usually give a function declaration that specifies the type of the function. Function declarations are written as f::Int->Int, which corresponds to the mathematical statement f: Z → Z.
• Haskell uses indentation to delimit blocks of code, similarly to python. So, be careful on how you format your functions.

Deterministic Finite Automata

These notes illustrate the use of the haskell programming language to implement the mathematical definition of Deterministic Finite Automata. We closely follow the notation in the lecture notes from last week. So, this may be a good time to read them again to refresh your memory. The complete code is in the file DFA.hs. Download the file, and try to compile it running the command ghc DFA.hs. (If working on the class computer accounts, you can find DFA.hs and other files in the $PUBLIC/share directory.)

Let's look at the content of DFA.hs. Its starts with the definition of DFA. Recall that we defined a DFA as a 5-tuple M = (Q, Σ , δ, s, F) where Q, Σ  are finite sets, δ: Q × Σ  → Q, s ∈ Q and F ⊆ Q. Later on, it will be convenient to use automata with different types of states, e.g., we may have automata where states are integers, and other automata where states are pairs of integers. So, we define a parametric type DFA st where st is the underlying type of states. Our definition of DFA is

type DFA st = ([st], [Char], (st->Char->st), st, (st->Bool))

What this declaration says is that DFA st is a type (parametrized by st), and that this type is just a 5-tuple consisting of 5 objects of the following types:

• [st] (a list of states, corresponding to the set of states Q of the DFA). Here, for any type t, the expression [t] is the type of lists with elements of type t. For example, x::[Int] means "x is a list of integers. A list with first element a and tail w is written a:w. The empty list is [].
  
• [Char] (a list of characters, corresponding to the set Σ  of input symbols). Here Char is just the standard type of characters. Characters are written as 'a', 'b', etc.
• st->Char->st (the transition function δ: Q → Σ  → Q). Recall that functions are curried, so, the type of the transition functions is more accurately described as δ: Q → Σ  → Q.
• st (the start state s ∈ Q),
• a function st\to Bool (representing the final states F, described by a predicate that on input a state q outputs True if q ∈ F and False otherwise).

Except for minor differences (e.g., currying the transition function δ: Q → Σ  → Q and representing the final states as a predicate f(x) = (x ∈ F)), this is almost identical to the definition of a DFA as a mathematical object.

Now let's define the function defined by an automaton M = (Q, Σ , δ, s, F). This should be a function f_M: Σ ^* → {0, 1}. In our program, we define it as a function which takes as input the DFA M (of type DFA st) and an input string (a String is just a list of Char). The output of the function is a boolean, either True or False. Remember that the definition in the notes makes use of an auxiliary function δ^*: Q × Σ ^* → Q. Our haskell program is

evalDFA :: DFA st -> String -> Bool
evalDFA (qs, sigma, delta, s, inF) w = 
  inF (deltaStar s w) 
  where deltaStar q [] = q
        deltaStar q (a:w) = deltaStar (delta q a) w

It says that evalDFA is a function mapping a DFA and an input string to a boolean value. On input a DFA (qs, sigma, delta, s, inF) and a string w, it simply computes δ^*(s, w) and checks that the result satisfies the predicate inF, i.e., it is an accepting state. Compare the definition of evalDFA above, with the definition of f_M in the class notes. The two lines defining the function detlaStar in the program correspond to the definition of the function δ^* in the notes.

That's it. We turned the mathematical definition of DFA, and the function it computes, into a computer program that you can run. The file DFA.hs also contains the implenetation of the mathematical objects corresponding to the definition of configurations, and associated state transition system, corresponding to section 1.2 of the class notes. We don't need it here, but you are encouraged to look at it, and compare it to the mathematical definitions.

Let's run some programs

We wrote a simple program, compiled it. Let's try to run it. We have provided a few additional files that contain code useful to run the programs on interesting examples. In order to run our evalDFA function, do the following:

• Draw a DFA in JFLAP. For this to work, you should design a complete DFA, with all transitions, including default transitions going to reject state. You can pick one of the automata you designed as part of homework 1, or use the example file hw2dfa1.jff. Copy the jff file to your working directory.
• copy the JFF.hs, NFA.hs and FST.hs files to your working directory too, and compile them with the command ghc JFF.hs. NFA.hs and FST.hs are used later on, but you need them now to compile JFF.hs, which is a simple library we wrote to import/export automata between our haskell programs and jflap. You do not need to look at this program for now. Just use it.
• call the haskell interpreter ghci DFA.hs JFF.hs and run the following commands at its prompt

f <- readFile "hw2dfa1.jff"
let (Just m) = JFF.readDFA f
evalDFA m "10001001"

These commands perform the following actions: 1. read the file "hw2dfa1.jff", and put its content in f. You can replace it with any other filename, as long as it contains a valid DFA. 2. parse f as the jflap file of a DFA, and put the result in m. 3. Run the DFA m on the given input string. It should output either True or False. Replace "10001001" with any string of your choice over the input alphabet of your DFA. Our example DFA uses alphabet {0, 1}.

You can keep running the automaton on other string over the input alphabet of your automaton. Look at the .jff file from step 1 in JFLAP. What's the language of the automaton? Is our program providing the correct answers to the given input strings? When you had enough, type :q to quit the interpreter.

Closure properties

The textbook (Theorem 1.25) gives a proof that regular languages are closed under the union operation. The proof is constructive, in the sense that it gives an algorithmic procedure to transform any two DFA M₁ and M₂ into a new DFA M₁₂ such that L(M₁₂) = L(M₁) ∪ L(M₂). The proof is easily translated into a computer program that performs the transformation.

1. Read the proof of Theorem 1.25 from the textbook, showing that the union of two regular languages is regular. Notice, this is a different proof than the one presented in class (where we followed Theorem 1.45).
2. Look at the file DFAunion.hs

The first few lines are just the module preamble and some comments. The interesting part of the file is

unionDFA :: DFA st1 -> DFA st2 -> DFA (st1,st2)
unionDFA (qs1, sigma, delta1, q1, inF1) (qs2, sigma2, delta2, q2, inF2) | sigma2 == sigma = 
  let  qs = [(r1,r2) | r1 <- qs1, r2 <- qs2]
       delta (r1,r2) a = (delta1 r1 a, delta2 r2 a)
       q0 = (q1, q2)
       inF (r1,r2) = (inF1 r1) || (inF2 r2)
  in (qs, sigma, delta, q0, inF)

The first line says that unionDFA is a function that on input two DFA, outputs a new DFA. Moreover, if the two input DFA have states of types st1 and st2, then the output DFA has states of type (st1,st2), i.e., pairs consisting of a state from the first DFA, and a state from the second DFA. The (st1,st2) notation to combine two types, corresponds to the Cartesian product operation A₁ × A₂ to combine two sets.

The next line starts the definition of the function unionDFA which takes as input two DFA (qs1, sigma, delta1, s1, inF1) and (qs2, sigma, delta2, s2, inF2). As done in class, and in the textbook, we assume the two input DFA have the same input alphabet Σ . Since Haskell does not allow to use the same variable name in both positions of the input automata, the constraint that the two inputs have the same alphabet is encoded by the |sigma2==sigma condition before the = sign.

The body of the function definition says that the output of unionDFA is the DFA (qs,sigma,delta,s,inF), where the various component of the DFA are defined as follows:

1. qs is the list of all pairs (q1,q2), where q1 is a state of the first automaton, and q2 is a state of the second automaton. Compare the program definition qs = [(r1,r2) | r1 <- qs1, r2 <- qs2] to the mathematical definition Q = {(r₁, r₂) ∣ r₁ ∈ Q₁, r₂ ∈ Q₂}
2. The result of applying delta on state (r1,r2) and input symbol a, is obtained by applying delta1 on r1 and delta2 on r2. Compare the program line delta (r1,r2) a = (delta1 r1 a, delta2 r2 a) to the mathematical definition δ((r₁, r₂), a) = (δ₁(r₁, a), δ₂(r₂, a)).
3. The line q0 = (q1,q2) hardly requires any explaination, and it is virtually identical to the mathematical definition q₀ = (q₁, q₂).
4. Finally, inF (r1,r2) = (inF1 r1) || (inF2 r2) says that (r1,r2) is an accepting state is either r1 is accepting or r2 is accepting (or both). Compare to the mathematical definition F = {(r₁, r₂) ∣ r₁ ∈ F₁ ∨ r₂ ∈ F₂}. It looks slightly different from the program, because in our DFA.hs implementation we chose to model the accept states using a predicate inF :: st -> Bool, rather than a set/list.

In order to run our unionDFA function, we write a main program TestUnion.hs. You can look at the program, and figure out what it does:

1. it reads to file names from the command line arguments
2. it reads the corresponding files
3. it parses them as DFA, and stores the result in dfa1 and dfa2
4. it calls unionDFA dfa1 dfa2 to combine the two automata together
5. it converst the result into JFLAP format, and prints it out

To run the program, do the following:

1. Compile the program with the command ghc TestUnion.hs
2. Design two DFA using JFLAP, or use our example DFA hw2dfa1.jff and hw2dfa2.jff. If you use our examples, look at what they do by loading them in JFLAP. If you use your own automata, make sure they are fully specified DFA, as expected by our unionDFA function. (If not, you will get an error.)
3. Run the compiled program ./TestUnion hw2dfa1.jff hw2dfa2.jff, possibly replacing the file names with your own DFA.
4. The command produces the output (union) DFA on standard output. That's not very readable. So, run the command again to output the result in a file: ./TestUnion hw2dfa1.jff hw2dfa2.jff >union.jff
5. Open union.jff in JFLAP, and look at the result.

Compare the two input DFA and output DFA by examining them in JFLAP. The layout of the states may not be great (our "unionDFA" program only takes care of the mathematical definition, leaving it to JFLAP to figure out where to place the states), but it works. You can run the DFA corresponding to the union in JFLAP, or even within haskell using our evalDFA function.

Homework 2, Problem 4

The solution to the homework problem 4 is very similar to the one described in the previous section. In fact, the solution to part (b) is almost identical. You can use the following files:

• TestComplement.hs This is the main program to test your solution to part (a). You should use this file unmodified.
• hw4a.hs You should complete the definition of the function complementDFA in this file, similar to what with did for unionDFA.
• TestIntersect.hs This is the main program to test your solution to part (b). You should use this file unmodified.
• hw4b.hs You should complete the definition of the function intersectDFA in this file, similar to what with did for unionDFA.

You can test your programs by running

ghc TestComplement.hs hw4a.hs
ghc TestIntersect.hs hw4b.hs

and execute the resulting programs on DFA of your choice similar to what we did for the union operation. You can examing the output of your programs in JFLAP, test them on various input strings, etc. As part of your homework, you only need to submit your hw4a.hs and hw4b.hs files.

Closure properties using NFA

In order to implement your solution to Problem 5, you will need Nondeterministic Finite Automata. In NFA.hs we define a data type to represent NFA, and use it to implement the constructions that prove the closure properties of regular languages under union, concatenation and star along the lines of Theorems 1.45, 1.47, 1.49 in the testbook. We also give NFA constructions to translate any regular expression into an NFA, as done in Lemma 1.55. Beside giving a method to transform any regular expression into an NFA, the constructions illustrate the use of various types that you may find useful in the solution of problem 5.

Let's begin from the definition of NFA. Remember, the mathematical definition N = (Q, Σ , δ, s, F) is almost the same as for DFA, except that type of the transition function now is δ: Q × Σ _ε → ℘(Q). Accordingly, we implement NFA as 5-tuples

type NFA st = ([st], [Char], st->(Maybe Char)->[st], st, st->Bool)

All component are the same as in the DFA definition, except for the type st -> Maybe Char -> [st] of the transition function. There are two differences with DFA:

• The second argument to the transition function is Maybe Char. This represents an "optional" element of type Char. Elements of type Maybe Char can be either Nothing (which we use to represent the empty string ε) or Just a (to represent any character a::Char)
• The output of the transition function is a list of states [st] rather than a single state. We use lists rather than the poweset because they are more convenient to use in computer programs. So, the automaton is nondeterministic. The transition function may output the empty list [] (corresponding to the empty set ∅), or a singleton list [q] (if there is just one possible transition), or a longer list [q1,q2,q3].

Let's define some NFA. We begin with an NFA accepting only the empty string. As in the proof of Lemma 1.55, we define it as an NFA with only one state, which is accepting, and no transitions.

epsilonNFA :: NFA () -- () is a special type, called unit, with only one element, also written as ()
epsilonNFA =
  let delta () a = [] -- There are no transitions
      inF () = True   -- Accepts empty string
  in ([()],[],delta,(),inF)

The first line says that epsilonNFA is an automaton with states of type (). This is a special type, called unit, with only one element which is also written as (). Alternatively, you could have defined epsilonNFA as having type NFA Int and restrist the set of states to just [q] where q is an arbitrary integer used to represent the start state.

Can you define an NFA that accepts the empty language? Try on your own, and then look at the definition of emptyNFA in NFA.hs.

Let's move of a more complex example: an NFA that only accepts the one element string "a". (Again, our definition directly encodes the construction in the proof of Lemma 1.55 in the textbook. So, you may want to start by reading the mathematical definition.) Since "a" can be any character, we define a function symbolNFA that takes a single character as input, and outputs a corresponding NFA. The output NFA needs to state. This can be accomplished using the type Either () (). This is a datatype with just to elements Left () and Right ().

symbolNFA :: Char -> NFA (Either () ())
symbolNFA a =
  let qs = [Left (),Right()] 
      sigma = [a]
      q0 = Left ()
      inF (Left  ()) = False
      inF (Right ()) = True
      delta (Left ()) (Just a) = [Right ()]
      delta _ _ = []
  in  (qs,sigma,delta,q0,inF)

More generally, you can use Either to form the disjoint union of two sets (techically, this is called a "sum type"): For any two types type1 and type2, the type Either type1 type2 contains all elements of the form Left v1 (where v1::type1) or Right v (where v::type2). The Left and Right constructors are used not to confuse elements coming from the first set and elements from the second set. So, as in the previous example, Either () () contains two distinct copies of the value (), which are used for the left state and right state of the automaton. The left state is the start state. The right state is the only accepting state. Finally, there is only one transition, from the left state to the right state, and labeled with Just a.

We can use the unit type () and the sum type Either a b to give automata corresponding to the union, concatenation and star operations:

• Read the proof of Theorem 1.49 that regular languages are closed under star. We implement it as a function that on input an NFA N₁, outputs an NFA that recognizes L(N₁)^*. The construction needs to introduce a new state. We accomplish this by defining a transformation that maps automata with states of type st to automata with states of type Either () st. The resulting set of states includes a state Right q for each state q of the original automaton, as well as a new state Left ().
• Read the proof of Theorem 1.47 that regular languages are closed under concatenation. This time, given two NFA with states Q₁, Q₂, we need to produce an NFA with states Q₁ ∪ Q₂. Notice, what we really want is the disjoint union of Q₁ and Q₂. So, we implement the transformation as a function mapping automata of types NFA type1 and NFA type2 to a new automaton of type NFA (Either type1 type2)
• Read the proof of Theorem 1.45 that regular languages are closed under union. This type with need to take the disjoint union Q₁ ∪ Q₂, and then add an extra state. We implement this as a transformation mapping NFA type1 and NFA type2 to a new NFA of type NFA (Either () (Either type1 type2)).

Look at the implementation of the functions in NFA.hs and compare the to the corresponding proofs in the textbook.

We have included a new function in JFF.hs to turn NFA into strings that can be read by JFLAP. Putting it all together, you can build an NFA corresponding to the regular expression (ab) *  ∪ (ba) * , and look at the result in JFLAP by calling the interpreter ghci NFA JFF and issuing the following command:

let n1 = starNFA (concatNFA (symbolNFA 'a') (symbolNFA 'b'))
let n2 = starNFA (concatNFA (symbolNFA 'b') (symbolNFA 'a'))
let n3 = unionNFA n1 n2
writeFile "nfa.jff" (JFF.writeNFA n3)
:q

Load "nfa.jff" into JFLAP and look at the result.

Homework 2, Problem 5

Work out the mathematical definition first. For part (a), you don't really need NFA. In fact, the problem is very very simple, but it is a good warm up to part (b).

• For part (a), implement a function transform that on input a symbol a and a DFA M, produces a DFA for the language L − a. You can do so by completing the definition in hw5a.hs. Notice: you need to choose the type of states for the output DFA. (Hint: it is very very simple.) You can also test your program using TestHW2p5a.hs similarly to problem 4. Notice that the homework assignment says your transformation should output an NFA. This is not needed. Give a program that outputs a DFA instead as in the template.
• For part (b), you can use the template hw5b.hs, and complete the definition of the function transform. Notice, this time you need to give a function that takes two DFA as input, and outputs an NFA. You can use TestHW2p5b.hs to test your program similarly to problem 4.