Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- -- Implementación de Máquina de Turing
- -- Se define formalmente como TM = (Q, Σ, Γ, δ, qo, ␣, F) donde:
- -- Q Conjunto de estados
- -- Σ Alfabeto de entrada
- -- Γ Alfabeto de la cinta
- -- δ Función de transición
- -- q0 Estado Inicial
- -- ␣ Símbolo en blanco
- -- F Conjunto de estados finales
- -- Definamos los tipos:
- type State = String
- -- Una configuración se representa mediante el siguiente sinónimo
- -- El entero representa la posición de la cabeza de lectoescritura en la cadena
- type Config = (State, String, Int)
- type Q = [State]
- type Sigma = [Char]
- type Gamma = [Char]
- type Delta = State -> Char -> (State, Char, Movement)
- type F = [String]
- -- Movimiento de la cabeza lectora
- data Movement = L | R
- -- Tipo de dato algebraico de la Máquina de Turing
- data MaqT = MaqT { states :: Q
- , sigma :: Sigma
- , gamma :: Gamma
- , delta :: Delta
- , q_0 :: State
- , blank_symbol :: Char
- , end_states :: F
- }
- -- Recibe una MaqT y una cadena
- -- Imprime el procesamiento formal de la cadena con configuraciones
- compute :: MaqT -> String -> [Config]
- compute tm@(MaqT _ _ _ _ q_0 _ _) str = computeAux tm q_0 str 0
- computeAux :: MaqT -> State -> String -> Int -> [Config]
- computeAux tm@(MaqT states sigma gamma delta _ blank_symbol end_states) q str index =
- case str of [] -> []
- (x:_) ->
- let (q_next, c_next, mov) = delta q x
- new_str = replaceNth index c_next str
- config = (q, str, index)
- i_head = case mov of
- L -> index
- R -> index + 1
- in config:(computeAux tm q_next new_str i_head)
- replaceNth :: Int -> a -> [a] -> [a]
- replaceNth _ _ [] = []
- replaceNth n newVal (x:xs)
- | n == 0 = newVal:xs
- | otherwise = x:replaceNth (n-1) newVal xs
- -- Recibe una MaqT y una cadena
- -- Regresa un bool diciendo si la cadena es aceptada [true] o no [false]
- -- por la máquina de Turing
- accept :: MaqT -> String -> Bool
- accept _ _ = True
- -- Recibe una MaqT
- -- Codifica la MaqT para pasarla como entrada de la Máquina Universal
- encode :: MaqT -> String
- encode _ = "d"
- -- EXTRA
- -- Recibe una String representando una máquina codificada
- -- Regresa la MaqT que representa
- decode :: String -> MaqT
- decode _ = error "sdf"
- tm_delta :: State -> Char -> (State, Char, Movement)
- tm_delta "q0" 'a' = ("q1", 'A', R)
- tm_delta "q0" 'B' = ("q4", 'B', R)
- tm_delta "q1" 'a' = ("q1", 'a', R)
- tm_delta "q1" 'b' = ("q2", 'B', R)
- tm_delta "q1" 'B' = ("q1", 'B', R)
- tm_delta "q2" 'C' = ("q2", 'C', R)
- tm_delta "q2" 'b' = ("q2", 'b', R)
- tm_delta "q2" 'c' = ("q3", 'C', L)
- tm_delta "q3" 'A' = ("q0", 'A', R)
- tm_delta "q3" 'C' = ("q3", 'C', L)
- tm_delta "q3" 'b' = ("q3", 'b', L)
- tm_delta "q3" 'B' = ("q3", 'B', L)
- tm_delta "q3" 'a' = ("q3", 'a', L)
- tm_delta "q4" 'B' = ("q4", 'B', R)
- tm_delta "q4" 'C' = ("q4", 'C', R)
- tm_delta "q4" '_' = ("qf", '_', R)
- -- tm_delta _ _ = ("qf", '_', R)
- tm_ex = MaqT { states=["q0", "q1", "q2", "q3", "q4", "qf"]
- , sigma=['a', 'b', 'c']
- , gamma=['a', 'b', 'c', 'A', 'B', 'C', '_']
- , delta=tm_delta
- , q_0="q0"
- , blank_symbol='_'
- , end_states=["qf"]
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement