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 covered in the first chapter of the textbook 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. Soon, we will show 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

For your convenience, we have already installed the haskell platform in the class directory on ieng6. 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.) So, log into your account, and type ghci. This will present you with a prompt >. You can type any expression at the prompt, the expression is evaluated, and the result it printed. E.g., if you enter 1+1, well, you know what the result should be. But to make more interesting use of the language, you will need to type your programs in a separate editor (e.g. emacs), and compile them with ghc or load them into ghci. So, exit ghci (e.g., typing Control-D), and keep reading.

We will only use the most basic features of the language. 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 on your computer with the commands cabal update, cabal install xml. (You will find all required packages already installed in ieng6. Installing packages is only needed if you use your own computer.)

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 try to focus on the course material, and don't get carried away with programming.

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 notation f : Z → Z (i.e., f is a function from the integers to the integers.)
• Haskell uses indentation to delimit blocks of code, similarly to python. So, be careful on how you format your functions, and don't use TABs, or make sure to use an editor that expands TABs into spaces.
• Haskell has strict conventions about the use of upper and lower case identifiers. By and large, functions and values start with a lowercase letters, while types start with uppercase.

Now, go over Chapter 2 of "Learn you a Haskell for Great Good!" and follow the examples. This should be enough for you to start writing and running some simple programs.

Next

• DFAs: Modeling and running DFAs. Constructive proofs of closure properties of regular languages.

• NFAs: Modeling nondeterministic automata. More closure properties of regular languages using NFAs, and converting Regular Expressions into automata.