module HW1
where
import Text.PrettyPrint.HughesPJ(Doc,text,char,int,(<>),(<+>),($+$),($$),render)
import PP
import Auxfuns
import List

import qualified DFA as D
import qualified NFA as N
import qualified NFAe as Ne

import PrintDFA
import PrintNFA
import PrintNFAe
import Graphviz

import Lecture2

-- Problem 1:  Sipser 1.3
data UD = U | D deriving (Eq, Ord, Show)

instance PP UD where pp = text . show

m13 = D.DFA { D.states = [1..5], D.symbols = [U,D], D.delta = d, D.start = 3, D.final =[3] }
      where d 1 U = 1
            d 1 D = 2
            d 2 U = 1
            d 2 D = 3
            d 3 U = 2
            d 3 D = 4
            d 4 U = 3
            d 4 D = 5
            d 5 U = 4
            d 5 D = 5

m13Diag = pdfG "HW1/p1" m13

--  Problem 2:  1.4g  even length, odd number of a's
intersectionDFA :: (Ord q1, Ord q2) => D.DFA q1 s -> D.DFA q2 s -> D.DFA (q1, q2) s
intersectionDFA 
         (D.DFA { D.states = bigQ1, D.symbols = sigma, D.delta = d1, D.start = q10, D.final = f1})
         (D.DFA { D.states = bigQ2, D.delta = d2, D.start = q20, D.final = f2})  
    = D.DFA { D.states = [(q1,q2) | q1 <- bigQ1, q2 <- bigQ2],
              D.symbols = sigma,
              D.delta = \ (q1,q2) a -> (d1 q1 a, d2 q2 a),
              D.start = (q10,q20),
              D.final = nub $ [(q1,q2) | q1 <- f1, q2 <- f2]}

meven = D.DFA { D.states = [0,1], D.symbols = ['a','b'], D.delta = d, D.start = 0, D.final = [0] }
    where d 0 _ = 1
          d 1 _ = 0

moddas = D.DFA { D.states = [0,1], D.symbols = ['a','b'], D.delta = d, D.start = 0, D.final = [1] }
    where d i 'a' = (i+1) `mod` 2
          d i 'b' = i

m14g = intersectionDFA meven moddas

m14gDiag = do { pdfG "HW1/p2.1" meven
              ; pdfG "HW1/p2.2" moddas
              ; pdfG "HW1/p2.3" m14g
              }

-- Problem 3:  1.5d

-- DFAs are closed under complement
--
compDFA :: (Ord q) => D.DFA q s -> D.DFA q s
compDFA (m@(D.DFA { D.states = bigQ, D.final = f}) )
    = m { D.final = filter (\p -> not $ p `elem` f) bigQ }

masbs = D.DFA{D.states = [0,1,2], D.symbols = ['a','b'], D.delta = d, D.start = 0, D.final = [0,1] }
   where d 0 'a' = 0
         d 0 'b' = 1
         d 1 'a' = 2
         d 1 'b' = 1
         d 2 _ = 2

masbsDiag = do { pdfG "HW1/p3.1" masbs
               ; pdfG "HW1/p3.2" (compDFA masbs)
               }

-- Problem 4:  1.31

-- Reverse of a DFA is a regular language
--

reverseDFA :: (Ord q) => D.DFA q s -> Ne.NFAe (Either q ()) s
reverseDFA (D.DFA { D.states = bigQ, 
                    D.symbols = sigma, 
                    D.delta = d, 
                    D.start = q0, 
                    D.final = f}) 
    = Ne.NFAe {Ne.states = (Right ()) : map Left bigQ,
               Ne.symbols = sigma,
               Ne.delta = delta',
               Ne.start = Right (),
               Ne.final = [Left q0]}
      where delta' (Right ()) Nothing  = map Left f
            delta' (Right ()) (Just _) = []
            delta' (Left p) (Just a)   = canonical $ [Left p' | p' <- bigQ, d p' a == p]
            delta' (Left p) Nothing    = []


-- Problem 5:  1.32

-- Binary 

bits = [0,1]

d (Just i) (a,b,c) 
    | (i + a + b) `mod` 2 == c = Just $ (i + a + b) `div` 2
    | otherwise = Nothing
d Nothing _ = Nothing

sums = D.DFA { D.states = [Just 0, Just 1, Nothing],
               D.symbols = [(a,b,c) | a <- bits, b <- bits, c <- bits],
               D.delta = d,
               D.start = Just 0,
               D.final = [Just 0]}

rsums = reverseDFA sums

rsum2 = nfaeToDfa rsums

m132Diag = do { pdfG "HW1/p5.1" sums
              ; pdfG "HW1/p5.2" rsums
              ; pdfG "HW1/p5.3" rsum2
              }