# 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``````

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 )
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.