Closure Properties of Regular Languages

We first generalized our definition of DFA to make it parametric with respect to the type of states. This will be useful to prove closure properties of regular languages. The evaluation function evalDFA is also easily generalized to DFA with parametric state type st. We require the type of states to be an instance of the Eq type class in order to use the elem::(Eq a) => a -> [a] -> Bool library function.

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

evalDFA :: (Eq st) => (DFA st) -> String -> Bool
evalDFA (qs,alpha,delta,s,fs) w =
    let deltaStar = foldl delta
        q = deltaStar s w
    in elem q fs

Read Types and Typeclasses to learn more.

We show that regular languages are closed under complement and union by giving two functions that transform DFAs accordingly. The transformation for the complement operation only modifies the set of accepting states.

complementDFA :: (Eq st) => (DFA st) -> (DFA st)
complementDFA (qs,alpha,delta,s,fs) = (qs,alpha,delta,s,fs1)
        where fs1 = [q | q <- qs, not (elem q fs)]

Notice the use of list comprehension notation [q | q <- qs, not (elem q fs)], similar to the set builder notation {q|q ∈ Q, q ∉ F}. See intro to lists for details.

For the union operation, we use a standard cartesian product operation on the set of states. In haskell, given automata with states of type st1 and st2, we build an automaton with states of type (st1,st2), the type of pairs consisting of an element of type st1 and an element of type st2.

unionDFA :: (Eq st1, Eq st2) => DFA st1 -> DFA st2 -> DFA (st1,st2)
unionDFA (qs1,alpha1,delta1,s1,fs1)
         (qs2,alpha2,delta2,s2,fs2) | alpha1==alpha2 =
             (qs,alpha1,delta,s,fs) where
                 qs = [(q1,q2) | q1 <- qs1, q2<-qs2]
                 delta (q1,q2) a = (delta1 q1 a,delta2 q2 a)
                 s = (s1,s2)
                 fs = filter f qs
                 f (q1,q2) = (elem q1 fs1) || (elem q2 fs2)

As an execise, give a similar transformation to prove that regular languages are closed under:

set intersection
set difference

Editing automata with JFLAP

We would like to try out our closure property constructions on some example automata. Describing DFAs by directly specifying the transition function as a haskell program can be tedious. It would be nice if we could edit and inspect our automata using a graphical interface, like the one provided by the JFLAP program. We will do just that. In order to try this out, you will need the following:

The Java program JFLAP, and a JVM to run it. All this is already installed on ieng6, where you should be able to run JFLAP simply calling the command jflap from the command line. (Of course, logging in ieng6 from a text terminal won’t do. You need graphics.)
The file DFA.hs with the haskell programs written today
The JFF.hs module to parse JFLAP files and turn them into haskell DFAs. This is a simple library written by yours truly for this class. You can look at the code if you are curious, or just use it, but you are not required to. It is a quick hack, but it gets the job done. The JFF.hs module contains parsing functions for various other automata we did not discuss yet. In order to compile and use JFF, download all the files from the Automata Library directory.
If you installed haskell on your own computer, you will also need to install the haskell xml parsing library, used by JFF.hs. You can do so using the commands cabal update; cabal install xml. This is not necessary on ieng6, as we already installed the library for you. You can also find the Automata Library files in $PUBLIC/share. Copy them to your working directory, and you are ready to go.

Then you can proceed as follows. Use JFLAP to draw two DFAs of your choice, or look at the DFAs dfa1.jff, dfa2.jff used in class. Next, make sure you have all required files in your working directory, start ghci, and execute the following sequence of commands:

ghci> :l JFF.hs
[1 of 2] Compiling DFA              ( DFA.hs, interpreted )
[2 of 2] Compiling JFF              ( JFF.hs, interpreted )
Ok, modules loaded: JFF, DFA.
ghci> f1 <- readFile "dfa1.jff"
ghci> f2 <- readFile "dfa2.jff"
ghci> let (Just m1) = readDFA f1
ghci> let (Just m2) = readDFA f2
ghci> let m3 = unionDFA m1 m2
ghci> writeFile "dfa3.jff" (writeDFA m3)

Loading JFF.hs automatically loads also the module DFA.hs with the haskell code written today. Next, we read two jflap files (using the function readFile), and we parse them as DFAs with the function readDFA. This is a function from JFF.hs of type String -> Maybe (DFA Int) that on input a string (the file content), attempts to parse it as the JFLAP representation of a DFA. The result is Nothing if the parsing fails, or Just m for some DFA m. You can read more about working with files in Input and Output. If you are confused about the difference between f <- ... and let m = ..., don’t worry. It is a method to capture Input/Output actions in a purely functional programming language. If you want to learn more about this, you may want to read A fistful of monads, but it is probably better if you leave this for later. Just learn how to read and write to files in haskell using the commands above, and it will be enough for now.

At this point you can use our evalDFA function to run the union automaton m3 on any input of your choice, or write the result to a file, after converting it to JFLAP format with the function writeDFA from JFF.hs, and inspect the result with JFLAP.