Math.Model.Automaton.Finite

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

Recognizer

Functions

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

Transition function that for every pair, a State and a Symbol by domain, decide next state in machine

type NDelta a = (:-<:) a Symbol ()

Transition function that for every pair, a State and a Symbol by domain, decide next list of states in machine

Constructor

data FiniteA a

Finite deterministic Automaton

Constructors

F (Delta a) (Final a) (Label a)

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

FN (NDelta a) (Final a) (Label a)

>>> let autFinN = FN deltaN (Set.fromList [Q 0]) (Q 0)

Instances

Eq a => Eq (FiniteA a)

Methods

(==) :: FiniteA a -> FiniteA a -> Bool

(/=) :: FiniteA a -> FiniteA a -> Bool

Show a => Show (FiniteA a)

Methods

showsPrec :: Int -> FiniteA a -> ShowS

show :: FiniteA a -> String

showList :: [FiniteA a] -> ShowS

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

Executes a automaton over a word

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

Transducer

Functions

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

Transducer function

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

Transducer function with output at transition

Constructor

data Transductor a

Transducer Autmaton, both types:

1. Moore
2. 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)

Methods

(==) :: Transductor a -> Transductor a -> Bool

(/=) :: Transductor a -> Transductor a -> Bool

Show a => Show (Transductor a)

Methods

showsPrec :: Int -> Transductor a -> ShowS

show :: Transductor a -> String

showList :: [Transductor a] -> ShowS

translate :: Ord a => Transductor a -> Wd -> (Wd, Bool)

For every transducer, given a word the automaton change all symbols in lambda

Auxiliar functions

getAlphabet :: FiniteA a -> Alphabet

Gets alphabet for some finite automaton

endState :: Ord a => Delta a -> Wd -> State (Label a) (Label a)

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)

Same as endState but work with no deterministic delta

Create deltas and lambdas

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

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

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])]

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

Lift simple transducer function

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

Lift second transducer function

Mininmize delta

reachableDelta :: Ord a => FiniteA a -> FiniteA a

Minimaize a delta for some finite automaton. Gets a delta with all reachable states from initial state.

distinguishableDelta :: Ord a => FiniteA a -> FiniteA a

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

Minimize a finite automaton,

1. Delete redundant states
2. Delete unreachable states and their transitions

Equivalence

convertFA :: (Enum a, Ord a) => FiniteA a -> FiniteA a

Finite Autmaton Equivalence

transducerToFinite :: Transductor a -> FiniteA a

Transforms a Transducer to a Finite Autmaton

finiteToMoore :: (Enum a, Ord a) => FiniteA a -> Lambda1 a -> Transductor a

Transforms a Finite Autmaton with some lambda to a Moore Transducer

finiteToMealy :: (Enum a, Ord a) => FiniteA a -> Lambda2 a -> Transductor a

Transforms a Finite Autmaton with some lambda to a Mealy Transducer

Language

automatonEssence :: Ord a => FiniteA a -> Essence

Tells if a finite automaton had empty language or not.

automatonCardinality :: Ord a => FiniteA a -> Discrete

Tells if a finite automaton had infinite language or the number or words in his language