-- 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 0.1.1.2


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

-- | Initial symbol for stack
z0 :: Symbol

-- | List symbol alias, Word are defined in Prelude
type Wd = [Symbol]
instance GHC.Base.Monoid Data.Sigma.Symbol


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

-- | Macine states are only a label, maybe a letter
data State a

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

-- | Error state
QE :: State a

-- | Final state represent a set of states which elements put end to
--   computation
type Final a = [State a]

-- | Tells if a state is final
terminal :: (Eq a) => Final a -> State a -> Bool

-- | Verifica si el estado es de error, comparandolo con la definicion de
--   estado de error
--   
--   Tells if a state is a error state
isError :: (Eq a) => State a -> Bool
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.State.State a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.State.State a)
instance GHC.Show.Show a => GHC.Show.Show (Data.State.State a)
instance GHC.Base.Functor Data.State.State
instance GHC.Base.Applicative Data.State.State
instance GHC.Base.Monad Data.State.State
instance GHC.Enum.Enum a => GHC.Enum.Enum (Data.State.State a)
instance GHC.Enum.Bounded a => GHC.Enum.Bounded (Data.State.State a)
instance GHC.Base.Monoid a => GHC.Base.Monoid (Data.State.State a)
instance Data.Foldable.Foldable Data.State.State


-- | Map implementation, represent a partial function
module Data.Delta
type (:->:) a p1 p2 = Map (State a, p1) (State a, p2)
nextD :: (Ord p1, Ord a) => (:->:) a p1 p2 -> (State a, p1) -> State a
type (:>-:) a p1 p2 = Map (State a, p1) ([State a], p2)
type (:*>:) a p o = Map (State a, p) o


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

-- | Transition function hava a State and a Symbol by domain to decide next
--   state in machine
type Delta a = (:->:) a Symbol ()

-- | Lift a list of 3-tuples in a Delta
--   
--   <pre>
--   &gt;&gt;&gt; let delta = liftD [(0,'0',0),(0,'1',1),(1,'0',1),(1,'1',0)]
--   </pre>
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

-- | Finite deterministic Automaton
data FiniteA a

-- | <pre>
--   &gt;&gt;&gt; let autFin = F delta [Q 0] (Q 0)
--   </pre>
F :: (Delta a) -> (Final a) -> (State a) -> FiniteA a
data Transductor a
Moore :: (Delta a) -> (Lambda1 a) -> (Final a) -> (State a) -> Transductor a
Mealy :: (Delta a) -> (Lambda2 a) -> (Final a) -> (State a) -> Transductor 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
translate :: (Ord a) => Transductor a -> Wd -> Wd
type DeltaN a = (:>-:) a Symbol ()

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

-- | Finite non deterministic Automaton
data FiniteAN a

-- | <pre>
--   &gt;&gt;&gt; let autFinN = FN deltaN (terminal [Q 0]) (Q 0)
--   </pre>
FN :: (DeltaN a) -> (Final a) -> (State a) -> FiniteAN a

-- | Executes a non-deterministic automaton over a word, maybe overload
--   your pc
checkStringN :: (Ord a) => FiniteAN a -> Wd -> Bool
instance GHC.Classes.Eq a => GHC.Classes.Eq (Math.Model.Automaton.Finite.FiniteAN a)
instance GHC.Show.Show a => GHC.Show.Show (Math.Model.Automaton.Finite.FiniteAN a)
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 and a
--   symbol in stack head and returns next state and update stack
type Delta a = (:->:) a (Symbol, Symbol) [Symbol]

-- | Takes a list of tuples and lift a Delta
--   
--   <pre>
--   &gt;&gt;&gt; let delta = liftD [(0,'1','A',1,[AA]),(0,'0',blank,0,[A])]
--   </pre>
liftD :: (Ord a) => [(a, Symbol, Symbol, a, [Symbol])] -> Delta a

-- | Stack machine only needs a delta and a init state
data StackA a
S :: (Delta a) -> (State a) -> StackA a

-- | Executes a stack machine over a word
--   
--   <pre>
--   &gt;&gt;&gt; checkString autStack 'aaabbbcccccc'
--   True
--   </pre>
checkString :: (Ord a) => StackA a -> Wd -> Bool


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

-- | Movimiento a la izquierda
L :: LRS

-- | No movimiento
S :: LRS

-- | Movimiento a la derecha
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
class (Applicative t) => Tapeable t a
getHead :: Tapeable t a => t a -> a
liftTape :: (Tapeable t a, Monoid (t a)) => [a] -> t a
data 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 :: Delta a b c -> State a -> Final a -> Model a b c
data MultiModel a b c
MTS :: MDelta a b c -> State a -> [Final a] -> MultiModel a b c
instance GHC.Classes.Eq (t a) => GHC.Classes.Eq (Math.Model.Turing.MultiTape t a)
instance GHC.Show.Show (t a) => GHC.Show.Show (Math.Model.Turing.MultiTape t a)
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.LRS
instance Math.Model.Turing.Ways Math.Model.Turing.FW