Dfa.hs

import Numeric
import Data.Char
import Data.Monoid

data State = Accept | S1 | S2 deriving (Show)

data Alphabet = Zero | One deriving (Show)

newtype Transition = Transition { runTransition :: State -> State }

transition :: Alphabet -> Transition
transition Zero = Transition $ \q -> case q of
                                       Accept -> Accept
                                       S1 -> S2
                                       S2 -> S1

transition One = Transition $ \q -> case q of
                                      Accept -> S1
                                      S1 -> Accept
                                      S2 -> S2

transitionHat :: State -> [Alphabet] -> State
transitionHat q [] = q
transitionHat q (a:w) = runTransition (transition a) $ transitionHat q w

transitionHat' :: State -> [Alphabet] -> State
transitionHat' q w = runTransition (mconcat (map transition w)) q

isMultipleOfThree :: [Alphabet] -> Bool
isMultipleOfThree w = case transitionHat Accept w of
                        Accept -> True
                        S1 -> False
                        S2 -> False

toBin :: Show a => Integral a => a -> String
toBin n = showIntAtBase 2 intToDigit n ""

fromBin :: String -> Int
fromBin = fst . head . readInt 2 (`elem` "01") digitToInt

toAlphabet :: Char -> Alphabet
toAlphabet '0' = Zero
toAlphabet '1' = One

toInput :: Show a => Integral a => a -> [Alphabet]
toInput = map toAlphabet . toBin

instance Monoid Transition where
    mempty = Transition id -- can we do this???
    (Transition t1) `mappend` (Transition t2) = Transition $ t1 . t2

main :: IO ()
main = return ()