module Rip where ---------------------------------------------------------- -- Algebraic types for Regular Expressions, DFAs and GNFAs ---------------------------------------------------------- data RE a = Null | Epsi | Lit a | Or (RE a) (RE a) | Cat (RE a) (RE a) | Star (RE a) data DFA s a = DFA [s] [a] (s -> a -> s) s [s] data GNFA s a = GNFA [s] [a] (Maybe s -> Maybe s -> RE a) -- a function to rip a GNFA into an RE, based on 1-step helper function -- (note that rip1 is not quite a fold, but it is a "paramorphism") rip (GNFA ss _ d) = rip1 d (map Just ss) rip1 d [] = d Nothing Nothing rip1 d (s:ss) = rip1 d' ss where d' u v = elim (d u v) (d u s) (d s s) (d s v) elim r s t v = r `Or` (s `Cat` (Star t `Cat` v)) -- a function to "inject" a DFA into an initial GNFA -- (Nothings represents new begin and end states) d2g (DFA ss as d q0 f) = GNFA ss as d' where d' Nothing Nothing = Null d' Nothing (Just s) = if s == q0 then Epsi else Null d' (Just s) Nothing = if s `elem` f then Epsi else Null d' (Just s) (Just t) = foldl Or Null (map Lit [a | a <- as, d s a == t]) -- just for fun, how big are those REs computed as conversions? size Null = 1 size Epsi = 1 size (Lit _) = 1 size (Or r s) = 1 + size r + size s size (Cat r s) = 1 + size r + size s size (Star r) = 1 + size r -- a Show instance for REs, using Unicode (probably won't work in lecture ...) instance Show a => Show (RE a) where show Null = "ø" -- ("\195\184") show Epsi = "ε" -- ("\206\181") show (Lit a) = chr a show (Or r s) = inf "|" (show r) (show s) show (Cat r s) = inf "·" (show r) (show s) show (Star r) = par (show r ++ "*") chr c = [head (tail (show c))] par str = "(" ++ str ++ ")" inf x a b = par (a ++ x ++ b) --------------------------------------- -- Some sample DFAs (from the homework) --------------------------------------- sample1 = DFA [1..4] "ab" d 1 [1,4] where d 1 'a' = 2 ; d 1 'b' = 3 d 2 'a' = 2 ; d 2 'b' = 4 d 3 'a' = 3 ; d 3 'b' = 3 d 4 'a' = 2 ; d 4 'b' = 4 sample2 = DFA [1..8] "ab" d 1 [2,4,5,7] where d 1 'a' = 5 ; d 1 'b' = 2 d 2 'a' = 4 ; d 2 'b' = 3 d 3 'a' = 4 ; d 3 'b' = 3 d 4 'a' = 8 ; d 4 'b' = 8 d 5 'a' = 6 ; d 5 'b' = 7 d 6 'a' = 6 ; d 6 'b' = 7 d 7 'a' = 8 ; d 7 'b' = 8 d 8 'a' = 8 ; d 8 'b' = 8 sample3 = DFA [1..3] "ab" d 1 [1,3] where d 1 'a' = 2 ; d 1 'b' = 3 d 2 'a' = 2 ; d 2 'b' = 3 d 3 'a' = 3 ; d 3 'b' = 2 -- ripping result REs from the samples r1 = rip (d2g sample1) -- ε | aa*b (b|aa*b)* r2 = rip (d2g sample2) -- b | ba | bbb*a | a | ab | aaa*b -- bb*a | a | aa*b | b -- b*a | a*b r3 = rip (d2g sample3) -- ε | (b|aa*b) (a|ba*b)* -- ε | a*b (a|ba*b)* ------------------------------------------ -- A (really messy) function to reduce REs ------------------------------------------ red r = case red1 r of Nothing -> r; Just s -> red s red1 (Null `Cat` r) = Just Null red1 (r `Cat` Null) = Just Null red1 (Null `Or` r) = Just (red r) red1 (r `Or` Null) = Just (red r) red1 (Epsi `Cat` r) = Just (red r) red1 (r `Cat` Epsi) = Just (red r) red1 ((r `Or` s) `Or` t) = Just (red r `Or` (red s `Or` red t)) red1 ((r `Cat` s) `Cat` t) = Just (red r `Cat` (red s `Cat` red t)) red1 (Star Null) = Just Epsi red1 (Star Epsi) = Just Epsi red1 Null = Nothing red1 Epsi = Nothing red1 (Lit a) = Nothing red1 (Or r s) = case red1 r of Nothing -> case red1 s of Nothing -> Nothing Just s' -> Just (Or r s') Just r' -> Just (Or r' s) red1 (Cat r s) = case red1 r of Nothing -> case red1 s of Nothing -> Nothing Just s' -> Just (Cat r s') Just r' -> Just (Cat r' s) red1 (Star r) = case red1 r of Nothing -> Nothing Just r' -> Just (Star r') -- red1 (r `Or` s) = if s < r then Just (s `Or` r) else Nothing -- red1 (Epsi `Or` (r `Cat` Star s)) = if s == r then Just (Star r) else Nothing -- red1 ((r `Cat` Star s) `Or` Epsi) = if s == r then Just (Star r) else Nothing