data Automaton state symbol
  = Automaton state (state -> symbol -> state) (state -> Bool)

-- { a^n | n >= 0 } <= {a,..}*
onlyAs :: Automaton Bool Char
onlyAs = Automaton True (\b c -> b && c=='a') id

{- Alternativen:
    - Uebergangsfunktion als Liste von Paaren,
    - Endzustandstest mit Liste von Endzustaenden
-}

accept :: Automaton state symbol -> [symbol] -> Bool
accept (Automaton init suc final) = final . foldl suc init

-- Die modellierten Automaten sind nicht notwendig endlich:

-- Klammerausdruecke
parens :: Automaton (Maybe Int) Char
parens
  = Automaton (Just 0) (\m b -> maybe Nothing (suc b) m) (maybe False (0==))
 where
  suc '(' n     = Just (n+1)
  suc ')' 0     = Nothing
  suc ')' (n+1) = Just n

-- { a^nb^n | n >= 0 } <= {a,b}*
anbn :: Automaton (Either Int Int) Char
anbn = Automaton (Left 0) (either go back) (either (0==) (1==))
 where
  go n   'a' = Left (n+1)
  go n   'b' = Right n
  back _ 'a' = Right 0
  back n 'b' = Right (n-1)