module Haskell12 where
{- The DFA module provides the definition of DFA, as given in Homework 1,
and utility functions to run DFAs on input strings, and import/export to JFLAP. -}
import DFA
{- Replace all the ... with the appropriate expressions corresponding to your
solution. You can work on one problem at a time, and try to compile, by encosling
the rest of the assignment in "{- ... -}" to comment it out.
-}
complementDFA :: DFA a -> DFA a
complementDFA (DFA (states,alphabet,delta,startState,isFinal)) =
DFA (states1, alphabet1, delta1, startState1, isFinal1) where
states1 = ...
alphabet1 = ...
delta1 q x = ...
startState1 = ...
isFinal1 q = ...
unionDFA :: DFA a -> DFA b -> DFA (a,b)
unionDFA
(DFA (states1,alpha1,delta1,start1,isFinal1))
(DFA (states2,alpha2,delta2,start2,isFinal2))
| alpha1 == alpha2 -- assume input alphabets are the same
= DFA (states,alpha1,delta,start,isFinal) where
states = ...
start = ...
isFinal (q1,q2) = ...
delta (q1,q2) x = ...
intersectDFA :: DFA a -> DFA b -> DFA (a,b)
intersectDFA
(DFA (states1,alpha1,delta1,start1,isFinal1))
(DFA (states2,alpha2,delta2,start2,isFinal2))
| alpha1 == alpha2 -- assume input alphabets are the same
= DFA (states,alpha1,delta,start,isFinal) where
states = ...
start = ...
isFinal (q1,q2) = ...
delta (q1,q2) x = ...
-- This is the transformation used in HW2 problem 4, defined in terms of complement and intersection
problem4transformation dfa1 dfa2 =
intersectDFA dfa1 (complementDFA dfa2)