-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | An implementation of Turing Machine and Automaton
--   
--   An implementation of Turing Machine and Automaton for language theory
@package turingMachine
@version 1.0.0.0


-- | Auxiliar Functions
module Data.Helper

-- | Union of set monad
unionsFold :: (Ord a, Foldable t) => t (Set a) -> Set a

-- | Size of a set, with large integers
setGenericSize :: (Ord a) => Set a -> Integer


-- | Simple Label-State function, have an isomorphism with Maybe but order
--   are diferent
module Data.Label

-- | Machine states are only a label, maybe a letter
data Label a

-- | State constructor
Q :: a -> Label a

-- | Error state
QE :: Label a

-- | Final label state represent a set of states which elements put end to
--   computation
type Final a = Set (Label a)

-- | Tells if a label state is a error state
isError :: (Eq a) => Label a -> Bool

-- | Tells if a label state is final
terminal :: (Ord a) => Final a -> Label a -> Bool

-- | Alias for a set of lalbel states
type SetLabel a = Set (Label a)

-- | Alias for a label state of a set of label states
type LabelSS a = Label (SetLabel a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Label.Label a)
instance GHC.Show.Show a => GHC.Show.Show (Data.Label.Label a)
instance GHC.Base.Functor Data.Label.Label
instance GHC.Base.Applicative Data.Label.Label
instance GHC.Base.Monad Data.Label.Label
instance GHC.Enum.Enum a => GHC.Enum.Enum (Data.Label.Label a)
instance GHC.Enum.Bounded a => GHC.Enum.Bounded (Data.Label.Label a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Label.Label a)
instance GHC.Base.Monoid a => GHC.Base.Monoid (Data.Label.Label a)
instance Data.Foldable.Foldable Data.Label.Label


-- | Cardinal definitions
module Data.Numerable

-- | All sets can be one and only one:
--   
--   <ul>
--   <li>a empty set</li>
--   <li>a set with, at least, one element</li>
--   </ul>
data Essence
Empty :: Essence
Occupied :: Essence

-- | Simple cardinality definition, we work here with numerable sets.
--   
--   All numerable set have one and only one:
--   
--   <ol>
--   <li>A finite size</li>
--   <li>A infinite size</li>
--   </ol>
data Discrete
Fin :: Integer -> Discrete
Numerable :: Discrete

-- | Order for numerable cardinality

-- | Bound limits for numerable cardinality
instance GHC.Classes.Eq Data.Numerable.Discrete
instance GHC.Show.Show Data.Numerable.Discrete
instance GHC.Enum.Bounded Data.Numerable.Essence
instance GHC.Classes.Ord Data.Numerable.Essence
instance GHC.Classes.Eq Data.Numerable.Essence
instance GHC.Show.Show Data.Numerable.Essence
instance GHC.Classes.Ord Data.Numerable.Discrete
instance GHC.Enum.Bounded Data.Numerable.Discrete


-- | Alphabet and symbols of languaje
module Data.Sigma

-- | Symbols are character, and with Unicode CharSet we have a big amount
--   of them.
type Symbol = Char

-- | Blank symbol
blank :: Symbol

-- | List symbol alias, Word are defined in Prelude
type Wd = [Symbol]

-- | An alphabet is a set of symbols
type Alphabet = Set Symbol

-- | For every alphabet there is a function <b>h</b> that maps one symbol
--   to one natural. For every <b>h</b> function there is a function that
--   enumerete every words in that alphabet
enumWord :: Alphabet -> Wd -> Integer

-- | Gives the Kleene Closure for all alphabets. closureAlph is a infinite
--   list of words.
closureAlph :: Alphabet -> [Wd]

-- | For some alphabet <b>S</b> and a natural number <b>n</b> take all
--   words of length <b>n</b> or less
lessKWords :: Alphabet -> Integer -> [Wd]

-- | For some alphabet <b>S</b> and a natural number <b>n</b> take all
--   words of length <b>n</b>
kWords :: Alphabet -> Integer -> [Wd]
instance GHC.Base.Monoid Data.Sigma.Symbol


-- | Map implementation, represent a partial function
module Data.Delta

-- | Map a tuple, a state and a param, to some output
type (:*>:) a p o = Map (Label a, p) o

-- | Deterministic Delta
--   
--   Maps a tuple, a state and a param, to another tuple, a state and a
--   param.
type (:->:) a p1 p2 = (:*>:) a p1 (Label a, p2)

-- | Lifts a deterministic delta from a 4-tuple list
liftD :: (Ord a, Ord p1) => [(a, p1, a, p2)] -> (:->:) a p1 p2

-- | Next state function for deterministic delta
nextD :: (Ord p1, Ord a) => (:->:) a p1 p2 -> (Label a, p1) -> Label a

-- | Non-Deterministic Delta
--   
--   Maps a tuple, a state and a param, to a tuple, a state list and a
--   param.
type (:-<:) a p1 p2 = (:*>:) a p1 (Set (Label a, p2))

-- | Lifts a non-deterministic delta from a 4-tuple list
liftND :: (Ord a, Ord p1, Ord p2) => [(a, p1, [(a, p2)])] -> (:-<:) a p1 p2

-- | Next state function for non-deterministic delta
nextND :: (Ord p1, Ord a) => (:-<:) a p1 p2 -> p2 -> (Label a, p1) -> Set (Label a)

-- | Lift a generic delta/map from a 3-tuple list
liftL :: (Ord a, Ord p) => [(a, p, o)] -> (:*>:) a p o

-- | Take a state and a param and maybe resolve some output
nextTMaybe :: (Ord p1, Ord a) => (:*>:) a p1 o -> (Label a, p1) -> Maybe o

-- | For simple map with Chars range
nextSymbol :: (Ord p1, Ord a) => (:*>:) a p1 Symbol -> (Label a, p1) -> Symbol

-- | Gets all params at domain, for (:-&gt;:) and (:-&lt;:)
getFirstParam :: (Eq b) => Map (a, b) a1 -> [b]

-- | Gets all params at domain, for (:-&lt;:) and (:-&lt;:)
getFirstParamSet :: (Ord b) => Map (a, b) a1 -> Set b

-- | Gets all params at range, for (:-&gt;:)
getSecondParamD :: (Eq p2) => (:->:) a p1 p2 -> [p2]

-- | Gets all params at range, for (:-&lt;:)
getSecondParamND :: (Ord p2) => (:-<:) a p1 p2 -> [p2]

-- | Gets all params at range, for (:-&gt;:)
getSecondParamSetD :: (Ord b) => Map k (a, b) -> Set b

-- | Gets all params at range, for (:-&lt;:)
getSecondParamSetND :: (Ord p2) => (:-<:) a p1 p2 -> Set p2

-- | Gets all states at domain, for (:-&gt;:) and (:-&lt;:)
getStateDomain :: (Eq a) => Map (a, b) a1 -> [a]

-- | Gets all states at domain, for (:-&gt;:) and (:-&lt;:)
getStateDomainSet :: (Ord a) => Map (a, b) a1 -> Set a

-- | Gets first param at range, for (:-&gt;:)
getStateRangeD :: (Eq a) => (:->:) a p1 p2 -> [Label a]

-- | Gets state at range in a list, for (:-&lt;:)
getStateRangeND :: (Ord a) => (:-<:) a p1 p2 -> [Label a]

-- | Gets first param at range, for (:-&gt;:)
getStateRangeSetD :: (Ord a) => (:->:) a p1 p2 -> Set (Label a)

-- | Gets state at range in a set, for (:-&lt;:)
getStateRangeSetND :: (Ord a) => (:-<:) a p1 p2 -> Set (Label a)


-- | Finite Automaton is a stateful machine where all transition means that
--   machine reads a symbol
module Math.Model.Automaton.Finite

-- | Transition function that for every pair, a State and a Symbol by
--   domain, decide next state in machine
type Delta a = (:->:) a Symbol ()

-- | Transition function that for every pair, a State and a Symbol by
--   domain, decide next list of states in machine
type NDelta a = (:-<:) a Symbol ()

-- | Finite deterministic Automaton
data FiniteA a

-- | <pre>
--   &gt;&gt;&gt; let autFin = F delta (Set.fromList [Q 0]) (Q 0)
--   </pre>
F :: (Delta a) -> (Final a) -> (Label a) -> FiniteA a

-- | <pre>
--   &gt;&gt;&gt; let autFinN = FN deltaN (Set.fromList [Q 0]) (Q 0)
--   </pre>
FN :: (NDelta a) -> (Final a) -> (Label a) -> FiniteA a

-- | Executes a automaton over a word
--   
--   <pre>
--   &gt;&gt;&gt; checkString autFin "1010010101101010"
--   True
--   
--   &gt;&gt;&gt; checkString autFin "1010010101101010001010101010"
--   False
--   </pre>
checkString :: (Ord a) => FiniteA a -> Wd -> Bool

-- | Transducer function
type Lambda1 a = (:*>:) a () Symbol

-- | Transducer function with output at transition
type Lambda2 a = (:*>:) a Symbol Symbol

-- | Transducer Autmaton, both types:
--   
--   <ol>
--   <li>Moore</li>
--   <li>Mealy</li>
--   </ol>
data Transductor a
Moore :: (Delta a) -> (Lambda1 a) -> (Final a) -> (Label a) -> Transductor a
Mealy :: (Delta a) -> (Lambda2 a) -> (Final a) -> (Label a) -> Transductor a

-- | For every transducer, given a word the automaton change all symbols in
--   lambda
translate :: (Ord a) => Transductor a -> Wd -> (Wd, Bool)

-- | Gets alphabet for some finite automaton
getAlphabet :: FiniteA a -> Alphabet

-- | For some delta, an initial state anf a word returns final state for
--   that word
endState :: (Ord a) => Delta a -> Wd -> State (Label a) (Label a)

-- | Same as endState but work with no deterministic delta
endStates :: (Ord a) => NDelta a -> Wd -> State (SetLabel a) (SetLabel a)

-- | Lift a list of 3-tuples to a Delta
--   
--   <pre>
--   &gt;&gt;&gt; let delta = liftDelta [(0,'0',0),(0,'1',1),(1,'0',1),(1,'1',0)]
--   </pre>
liftDelta :: (Ord a) => [(a, Symbol, a)] -> Delta a

-- | Lift a list of 3-tuples to a non deterministic delta
--   
--   <pre>
--   &gt;&gt;&gt; let deltaN = liftNDelta [(0,'0',[0]),(0,'1',[1]),(1,'0',[1]),(1,'1',[0])]
--   </pre>
liftNDelta :: (Ord a) => [(a, Symbol, [a])] -> NDelta a

-- | Lift simple transducer function
liftL1 :: (Ord a) => [(a, Symbol)] -> Lambda1 a

-- | Lift second transducer function
liftL2 :: (Ord a) => [(a, Symbol, Symbol)] -> Lambda2 a

-- | Minimaize a delta for some finite automaton. Gets a delta with all
--   reachable states from initial state.
reachableDelta :: (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.
distinguishableDelta :: (Ord a) => FiniteA a -> FiniteA a

-- | Minimize a finite automaton,
--   
--   <ol>
--   <li>Delete redundant states</li>
--   <li>Delete unreachable states and their transitions</li>
--   </ol>
minimizeFinite :: (Ord a) => FiniteA a -> FiniteA a

-- | Finite Autmaton Equivalence
convertFA :: (Enum a, Ord a) => FiniteA a -> FiniteA a

-- | Transforms a Transducer to a Finite Autmaton
transducerToFinite :: Transductor a -> FiniteA a

-- | Transforms a Finite Autmaton with some lambda to a Moore Transducer
finiteToMoore :: (Enum a, Ord a) => FiniteA a -> Lambda1 a -> Transductor a

-- | Transforms a Finite Autmaton with some lambda to a Mealy Transducer
finiteToMealy :: (Enum a, Ord a) => FiniteA a -> Lambda2 a -> Transductor a

-- | Tells if a finite automaton had empty language or not.
automatonEssence :: (Ord a) => FiniteA a -> Essence

-- | Tells if a finite automaton had infinite language or the number or
--   words in his language
automatonCardinality :: (Ord a) => FiniteA a -> Discrete
instance GHC.Classes.Eq a => GHC.Classes.Eq (Math.Model.Automaton.Finite.Transductor a)
instance GHC.Show.Show a => GHC.Show.Show (Math.Model.Automaton.Finite.Transductor a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Math.Model.Automaton.Finite.FiniteA a)
instance GHC.Show.Show a => GHC.Show.Show (Math.Model.Automaton.Finite.FiniteA a)


-- | Stack Automaton
module Math.Model.Automaton.Stack

-- | Delta for stack machine, takes a state, a symbol in string input or
--   not and a symbol in stack head and returns next state and update stack
type Delta a = (:->:) a (Maybe Symbol, Symbol) Wd

-- | A key for a delta.
type Key a = (Label a, (Maybe Symbol, Symbol))

-- | Takes a list of tuples and lift a Delta
--   
--   <pre>
--   &gt;&gt;&gt; let delta = liftD [(0,"(",'Z',0,"IZ"),(0,"",'Z',0,""),(0,"(",'I',0,"II"),(0,")",'I',0,"")]
--   </pre>
liftDelta :: Ord a => [(a, Wd, Symbol, a, Wd)] -> Delta a
nextDTuple :: Ord a => Delta a -> Key a -> (Label a, Wd)

-- | Stack machine only needs a delta, an init state and an initial symbol.
--   
--   This works for empty stack and final state acceptor
data StackA a
Stack :: Delta a -> Label a -> Final a -> Symbol -> StackA a
[getDelta] :: StackA a -> Delta a
[getInitState] :: StackA a -> Label a
[getFinal] :: StackA a -> Final a
[getInitSymbol] :: StackA a -> Symbol
nextState :: (Ord a) => Delta a -> Wd -> State (Wd, Label a) (Label a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Math.Model.Automaton.Stack.StackA a)
instance GHC.Show.Show a => GHC.Show.Show (Math.Model.Automaton.Stack.StackA a)


-- | Turing machine abstaction
module Math.Model.Turing
class Ways a
oposite :: Ways a => a -> a
data LRS

-- | Left move
L :: LRS

-- | No move
S :: LRS

-- | Right move
R :: LRS
data FW
Dw :: FW
Lf :: FW
Rt :: FW
Up :: FW
type Delta a b c = (:->:) a b (b, c)
type MDelta a b c = (:->:) a [b] ([b], [c])
liftD :: (Ord a, Ord b) => [(a, b, a, b, c)] -> Delta a b c
liftMD :: (Ord a, Ord b) => [(a, [b], a, [b], [c])] -> MDelta a b c
liftDAux :: (Ord a, Ord b) => [(a, b, a, b, c)] -> (:->:) a b (b, c)
class (Applicative t) => Tapeable t a
getHead :: Tapeable t a => t a -> a
liftTape :: (Tapeable t a, (Monoid (t a))) => [a] -> t a
newtype MultiTape t a
MT :: [t a] -> MultiTape t a
getMHead :: (Tapeable t a) => MultiTape t a -> [a]
liftMTape :: (Tapeable t a, Monoid (t a)) => [a] -> MultiTape t a
class (Tapeable t b, Ways w) => TuringM t b w
moveHead :: (TuringM t b w, (Monoid b)) => w -> t b -> t b
data Model a b c
[TS] :: (Ways c) => Delta a b c -> Label a -> Final a -> Model a b c
data MultiModel a b c
[MTS] :: (Ways c) => MDelta a b c -> Label a -> [Final a] -> MultiModel a b c
instance GHC.Enum.Bounded Math.Model.Turing.FW
instance GHC.Classes.Eq Math.Model.Turing.FW
instance GHC.Show.Show Math.Model.Turing.FW
instance GHC.Enum.Bounded Math.Model.Turing.LRS
instance GHC.Classes.Ord Math.Model.Turing.LRS
instance GHC.Classes.Eq Math.Model.Turing.LRS
instance GHC.Show.Show Math.Model.Turing.LRS
instance Math.Model.Turing.Ways Math.Model.Turing.FW
instance Math.Model.Turing.Ways Math.Model.Turing.LRS


-- | Two ways turing machine
module Math.Model.Turing.TwoWays
data Tape a
T :: [a] -> a -> [a] -> Tape a

-- | <pre>
--   &gt;&gt;&gt; let tapeLifted = (liftTape "word")::Tape Symbol
--   
--   &gt;&gt;&gt; tapeLifted
--   T "" 'w' "ord"
--   </pre>
instance GHC.Classes.Eq a => GHC.Classes.Eq (Math.Model.Turing.TwoWays.Tape a)
instance GHC.Show.Show a => GHC.Show.Show (Math.Model.Turing.TwoWays.Tape a)
instance GHC.Base.Functor Math.Model.Turing.TwoWays.Tape
instance GHC.Base.Applicative Math.Model.Turing.TwoWays.Tape
instance (GHC.Classes.Eq s, GHC.Base.Monoid s) => GHC.Base.Monoid (Math.Model.Turing.TwoWays.Tape s)
instance Math.Model.Turing.Tapeable Math.Model.Turing.TwoWays.Tape Data.Sigma.Symbol
instance Math.Model.Turing.Tapeable Math.Model.Turing.TwoWays.Tape [Data.Sigma.Symbol]
instance Math.Model.Turing.TuringM Math.Model.Turing.TwoWays.Tape Data.Sigma.Symbol Math.Model.Turing.LRS
instance Math.Model.Turing.TuringM Math.Model.Turing.TwoWays.Tape [Data.Sigma.Symbol] Math.Model.Turing.LRS


-- | Four ways turing machine
module Math.Model.Turing.FourWays
data Tracks a
Track :: [Tape a] -> (Tape a) -> [Tape a] -> Tracks a
instance GHC.Classes.Eq a => GHC.Classes.Eq (Math.Model.Turing.FourWays.Tracks a)
instance GHC.Show.Show a => GHC.Show.Show (Math.Model.Turing.FourWays.Tracks a)
instance GHC.Base.Functor Math.Model.Turing.FourWays.Tracks
instance GHC.Base.Applicative Math.Model.Turing.FourWays.Tracks
instance (GHC.Classes.Eq s, GHC.Base.Monoid s) => GHC.Base.Monoid (Math.Model.Turing.FourWays.Tracks s)
instance Math.Model.Turing.Tapeable Math.Model.Turing.FourWays.Tracks Data.Sigma.Symbol
instance Math.Model.Turing.TuringM Math.Model.Turing.FourWays.Tracks Data.Sigma.Symbol Math.Model.Turing.FW
instance Math.Model.Turing.TuringM Math.Model.Turing.TwoWays.Tape Data.Sigma.Symbol Math.Model.Turing.FW