Math.Model.Automaton.Finite

Finite Automaton is a stateful machine where all transition means that machine reads a symbol

Deterministic

Function

Recognizer

type Delta a = (:->:) a Symbol ()

Transition function hava a State and a Symbol by domain to decide next state in machine

liftD :: Ord a => [(a, Symbol, a)] -> Delta a

Lift a list of 3-tuples in a Delta

>>> let delta = liftD [(0,'0',0),(0,'1',1),(1,'0',1),(1,'1',0)]

Transducer

type Lambda1 a = (:*>:) a () Symbol

liftL1 :: Ord a => [(a, Symbol)] -> Lambda1 a

type Lambda2 a = (:*>:) a Symbol Symbol

liftL2 :: Ord a => [(a, Symbol, Symbol)] -> Lambda2 a

Constructor

data FiniteA a

Finite deterministic Automaton

Constructors

F (Delta a) (Final a) (State a)

>>> let autFin = F delta [Q 0] (Q 0)

Instances

Eq a => Eq (FiniteA a)

Show a => Show (FiniteA a)

data Transductor a

Constructors

Moore (Delta a) (Lambda1 a) (Final a) (State a)

Mealy (Delta a) (Lambda2 a) (Final a) (State a)

Instances

Eq a => Eq (Transductor a)

Show a => Show (Transductor a)

Function

checkString :: Ord a => FiniteA a -> Wd -> Bool

Executes a automaton over a word

>>> checkString autFin "1010010101101010"
True
>>> checkString autFin "1010010101101010001010101010"
False

translate :: Ord a => Transductor a -> Wd -> Wd

Not deterministic

Function

type DeltaN a = (:>-:) a Symbol ()

liftDN :: Ord a => [(a, Symbol, [a])] -> DeltaN a

Lift a list of 3-tuples in a non deterministic delta

>>> let deltaN = liftDN [(0,'0',[0]),(0,'1',[1]),(1,'0',[1]),(1,'1',[0])]

Constructor

data FiniteAN a

Finite non deterministic Automaton

Constructors

FN (DeltaN a) (Final a) (State a)

>>> let autFinN = FN deltaN (terminal [Q 0]) (Q 0)

Instances

Eq a => Eq (FiniteAN a)

Show a => Show (FiniteAN a)

checkStringN :: Ord a => FiniteAN a -> Wd -> Bool

Executes a non-deterministic automaton over a word, maybe overload your pc