| 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 ()
- type NDelta a = (:-<:) a Symbol ()
- data FiniteA a
- checkString :: Ord a => FiniteA a -> Wd -> Bool
- type Lambda1 a = (:*>:) a () Symbol
- type Lambda2 a = (:*>:) a Symbol Symbol
- data Transductor a
- translate :: Ord a => Transductor a -> Wd -> (Wd, Bool)
- getAlphabet :: FiniteA a -> Alphabet
- endState :: Ord a => Delta a -> Wd -> State (Label a) (Label a)
- endStates :: Ord a => NDelta a -> Wd -> State (SetLabel a) (SetLabel a)
- liftDelta :: Ord a => [(a, Symbol, a)] -> Delta a
- liftNDelta :: Ord a => [(a, Symbol, [a])] -> NDelta a
- liftL1 :: Ord a => [(a, Symbol)] -> Lambda1 a
- liftL2 :: Ord a => [(a, Symbol, Symbol)] -> Lambda2 a
- reachableDelta :: Ord a => FiniteA a -> FiniteA a
- distinguishableDelta :: Ord a => FiniteA a -> FiniteA a
- minimizeFinite :: Ord a => FiniteA a -> FiniteA a
- convertFA :: (Enum a, Ord a) => FiniteA a -> FiniteA a
- transducerToFinite :: Transductor a -> FiniteA a
- finiteToMoore :: (Enum a, Ord a) => FiniteA a -> Lambda1 a -> Transductor a
- finiteToMealy :: (Enum a, Ord a) => FiniteA a -> Lambda2 a -> Transductor a
- automatonEssence :: Ord a => FiniteA a -> Essence
- automatonCardinality :: Ord a => FiniteA a -> Discrete
Recognizer
Functions
type Delta a = (:->:) a Symbol () Source #
Transition function that for every pair, a State and a Symbol by domain, decide next state in machine
type NDelta a = (:-<:) a Symbol () Source #
Transition function that for every pair, a State and a Symbol by domain, decide next list of states in machine
Constructor
Finite deterministic Automaton
checkString :: Ord a => FiniteA a -> Wd -> Bool Source #
Executes a automaton over a word
>>>checkString autFin "1010010101101010"True>>>checkString autFin "1010010101101010001010101010"False
Transducer
Functions
Constructor
data Transductor a Source #
Transducer Autmaton, both types:
- Moore
- Mealy
Constructors
| Moore (Delta a) (Lambda1 a) (Final a) (Label a) | |
| Mealy (Delta a) (Lambda2 a) (Final a) (Label a) |
Instances
| Eq a => Eq (Transductor a) Source # | |
| Show a => Show (Transductor a) Source # | |
translate :: Ord a => Transductor a -> Wd -> (Wd, Bool) Source #
For every transducer, given a word the automaton change all symbols in lambda
Auxiliar functions
getAlphabet :: FiniteA a -> Alphabet Source #
Gets alphabet for some finite automaton
endState :: Ord a => Delta a -> Wd -> State (Label a) (Label a) Source #
For some delta, an initial state anf a word returns final state for that word
endStates :: Ord a => NDelta a -> Wd -> State (SetLabel a) (SetLabel a) Source #
Same as endState but work with no deterministic delta
Create deltas and lambdas
liftDelta :: Ord a => [(a, Symbol, a)] -> Delta a Source #
Lift a list of 3-tuples to a Delta
>>>let delta = liftDelta [(0,'0',0),(0,'1',1),(1,'0',1),(1,'1',0)]
liftNDelta :: Ord a => [(a, Symbol, [a])] -> NDelta a Source #
Lift a list of 3-tuples to a non deterministic delta
>>>let deltaN = liftNDelta [(0,'0',[0]),(0,'1',[1]),(1,'0',[1]),(1,'1',[0])]
Mininmize delta
reachableDelta :: Ord a => FiniteA a -> FiniteA a Source #
Minimaize a delta for some finite automaton. Gets a delta with all reachable states from initial state.
distinguishableDelta :: Ord a => FiniteA a -> FiniteA a Source #
Delete redundant states and their transitions, if a state is equivalent to another then is redundant, two state are equivalent if they are undistinguisahbles.
minimizeFinite :: Ord a => FiniteA a -> FiniteA a Source #
Minimize a finite automaton,
- Delete redundant states
- Delete unreachable states and their transitions
Equivalence
transducerToFinite :: Transductor a -> FiniteA a Source #
Transforms a Transducer to a Finite Autmaton
finiteToMoore :: (Enum a, Ord a) => FiniteA a -> Lambda1 a -> Transductor a Source #
Transforms a Finite Autmaton with some lambda to a Moore Transducer
finiteToMealy :: (Enum a, Ord a) => FiniteA a -> Lambda2 a -> Transductor a Source #
Transforms a Finite Autmaton with some lambda to a Mealy Transducer