automata-pila.hs

data State = Q1 | Q2 deriving Show
data Sigma = Zer | One | Cee | Nan deriving Show
data Gamma = R | B | G deriving Show

delta _ _ [] = error "Finished!"

delta Q1 Zer (R:p) = (Q1, B:R:p)
delta Q1 Zer (B:p) = (Q1, B:B:p)
delta Q1 Zer (G:p) = (Q1, B:G:p)

delta Q1 Cee (R:p) = (Q2, R:p)
delta Q1 Cee (B:p) = (Q2, B:p)
delta Q1 Cee (G:p) = (Q2, G:p)

delta Q1 One (R:p) = (Q1, G:R:p)
delta Q1 One (B:p) = (Q1, G:B:p)
delta Q1 One (G:p) = (Q1, G:G:p)

delta Q2 Nan (R:p) = (Q2, p)
delta Q2 Zer (B:p) = (Q2, p)
delta Q2 One (G:p) = (Q2, p)

delta q s p = error $ ("Undefined state: " ++ show (q, s, p))

trans '0' = Zer
trans '1' = One
trans 'c' = Cee

transAll s = map trans s ++ [Nan]

delta' s = uncurry $ flip delta s

runDelta s = (foldl (.) (delta' Nan) $ reverse $ map delta' $ transAll s) (Q1, [R])