| Copyright | (c) Jorge Santiago Alvarez Cuadros, 2016 |
|---|---|
| License | GPL-3 |
| Maintainer | sanjorgek@ciencias.unam.mx |
| Stability | experimental |
| Portability | portable |
| Safe Haskell | Safe |
| Language | Haskell2010 |
| Extensions |
|
Math.Model.Automaton.Finite
Contents
Description
Finite Automaton is a stateful machine where all transition means that machine reads a symbol
- type Delta a = (:->:) a Symbol ()
- liftD :: Ord a => [(a, Symbol, a)] -> Delta a
- 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
- data FiniteA a = F (Delta a) (Final a) (State a)
- data Transductor a
- checkString :: Ord a => FiniteA a -> Wd -> Bool
- translate :: Ord a => Transductor a -> Wd -> Wd
- type DeltaN a = (:>-:) a Symbol ()
- liftDN :: Ord a => [(a, Symbol, [a])] -> DeltaN a
- data FiniteAN a = FN (DeltaN a) (Final a) (State a)
- checkStringN :: Ord a => FiniteAN a -> Wd -> Bool
Deterministic
Function
Recognizer
type Delta a = (:->:) a Symbol () Source
Transition function hava a State and a Symbol by domain to decide next state in machine
liftD :: Ord a => [(a, Symbol, a)] -> Delta a Source
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
Constructor
Finite deterministic Automaton
data Transductor a Source
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) Source | |
| Show a => Show (Transductor a) Source |
Function
checkString :: Ord a => FiniteA a -> Wd -> Bool Source
Executes a automaton over a word
>>>checkString autFin "1010010101101010"True>>>checkString autFin "1010010101101010001010101010"False
Not deterministic
Function
liftDN :: Ord a => [(a, Symbol, [a])] -> DeltaN a Source
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
Finite non deterministic Automaton