turingMachine-0.1.1.1: An implementation of Turing Machine and Automaton

Copyright(c) Jorge Santiago Alvarez Cuadros, 2016
LicenseGPL-3
Maintainersanjorgek@ciencias.unam.mx
Stabilityexperimental
Portabilityportable
Safe HaskellSafe
LanguageHaskell2010
Extensions
  • TypeOperators
  • ExplicitNamespaces

Math.Model.Automaton.Finite

Contents

Description

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

Synopsis

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

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

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

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

Constructor

data FiniteA a Source

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) Source 
Show a => Show (FiniteA a) Source 

data Transductor a Source

Constructors

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

Instances

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

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

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

data FiniteAN a Source

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) Source 
Show a => Show (FiniteAN a) Source 

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

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