Instructor: Daniele Micciancio
Lectures: Monday 9:00-9:50am in CENTER 222
Welcome to "CSE191: Automata Practicum", a companion course to be taken concurrently with CSE105: Introduction to the Theory of Computation, where you will turn mathematical definitions and constructions into working computer programs.
Most of the mathematical definitions and theorems studied in Automata and Computability Theory classes 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, like haskell. If you have never used Haskell before, don't worry. While some prior knowledge of haskell, or other functional programming languages, may be useful, it is not required. We will use only a very small subset of the features of the Haskell programming language, and you can pick it up as we use it in class.
Haskell code written in class, and supporting files, will be posted below after each lecture:
Lecture 0: Get ready to run haskell on ieng6 (or your own computer), and learn a little bit about haskell. For a good tutorial introduction to haskell, see "Learn you a Haskell for Great Good!".
Lecture 1: Defining DFAs and the functions they compute in haskell.
Lecture 2: DFAs with parametric state type, closure properties of Regular languages, and reading/writing JFLAP files in haskell.
Lecture 3: Finite State Transducers (FST), evaluation and composition.
Homework 1, due Tuesday April 28. Starter files HW11.hs, HW12.hs, HW13.hs.
Lecture 4: Nondeterministic Finite Automata (NFA) and equivalence with DFAs.
Homework 2, due Tuesday May 19.
Download the new versions of DFA.hs, NFA.hs, FST.hs, JFF.hs.
You may also need the solutions HW13sol.hs.
Starter Files: FSTtest.hs, FSTdiff.hs
Testing programs: TestRLLencoder.hs, TestRLLdecoder.hs, id.jff
Lecture 5: Regular expressions, and conversion to finite automata.
You can use the following programs to test if a JFLAP file contains a valid DFA or FST, and run it on a given input. Remember to get the latest version of DFA.hs, NFA.hs, FST.hs, JFF.hs, otherwise they won't compile.
Testing programs: TestDFA.hs, TestFST.hs
Example usage (after compiling with 'ghc TestXXX.hs'): ./TestFST id.jff 1001
If id.jff is a valid jflap FST for the identity function, it will output '1001'. If the program gives an error message, then your automaton is not wellformed. (It may have missing transitions, nondeterministic transitions, or alphabet symbols that do not match. Open it up in jflap, and check for correctness.