Skip to content

Instantly share code, notes, and snippets.

@skalahonza
Last active January 3, 2019 14:59
Show Gist options
  • Save skalahonza/4556f5bd97d8b5761b28a9ffeadeabcd to your computer and use it in GitHub Desktop.
Save skalahonza/4556f5bd97d8b5761b28a9ffeadeabcd to your computer and use it in GitHub Desktop.
State machine solving a language problem
-- http://math.feld.cvut.cz/demlova/teaching/jag/cjag812.pdf cviceni 12.1
automat :: String -> Bool
automat input = automat_h input 0 False
automat2 :: String -> Bool
automat2 input = automat_h2 input ['z'] 1
automat_h :: String -> Int -> Bool -> Bool
automat_h ('a':xs) count False = automat_h xs (count + 1) False
automat_h ('b':xs) count False = automat_h xs (count + 1) False
automat_h ('c':xs) count False = automat_h xs count True
automat_h ('a':xs) count True = automat_h xs (count - 1) True
automat_h ('b':xs) count True = automat_h xs (count - 1) True
automat_h "" count _ = (count /= 0)
automat_h2 :: String -> [Char] -> Int -> Bool
automat_h2 ('c':xs) stack 1 = automat_h2 xs stack 2
automat_h2 (x:xs) stack 1 = automat_h2 xs ('a':stack) 1
automat_h2 ('a':xs) ('a':ss) 2 = automat_h2 xs ss 2
automat_h2 ('a':xs) ('z':_) 2 = True
automat_h2 "" ('a':_) 2 = True
automat_h2 _ _ _ = False
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment