Skip to content

Instantly share code, notes, and snippets.

@banacorn

banacorn/fa.hs

Created Sep 24, 2012
Embed
What would you like to do?
Deterministic & Non-deterministic Finite Automaton
import Data.Set
type State = String
type Alphabet = Char
type Language = String
type States = Set State
type Alphabets = Set Alphabet
type Transition = State -> Alphabet -> State
type NDTransition = State -> Alphabet -> States
data FA = DFA States Alphabets Transition State States
| NFA States Alphabets NDTransition State States
machine :: FA -> Language -> Bool
machine (DFA states alphabets transition state accepts) [] = member state accepts
machine (DFA states alphabets transition state accepts) (x:xs)
| notMember x alphabets = False
| otherwise = machine (DFA states alphabets transition nextState accepts) xs
where nextState = transition state x
machine (NFA states alphabets transition state accepts) [] = member state accepts
machine (NFA states alphabets transition state accepts) (x:xs)
| notMember x alphabets = False
| otherwise = or $ Prelude.map (\next -> machine (NFA states alphabets transition next accepts) xs ) nextState
where nextState = toList $ union alphabet eta
alphabet = transition state x
eta = transition state ' '
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment