Maquina Turing II

Máquina de Turing



Cíclicas o iterativos




Elementos:
                Q=(0,1,A,B)
                =(a,b,B)   entrada à cinta
                M=|x,R)    graba à  memoria
                SP=|R)
∆
(a,B)
(b,B)
(a,a)
(a,b)
(B,a)
(b,b)
(B,B)
(b,b)
0
(A,R)
(B,R)
ᶿ
ᶿ
ᶿ
ᶿ
(1, ᴫ)
ᶿ
A
ᶿ
ᶿ
(A,R)
ᶿ
(1,ᴫ)
ᶿ
ᶿ
ᶿ
B
ᶿ
ᶿ
ᶿ
(A,R)
ᶿ
(B, ᴫ)
ᶿ
(1, ᴫ)
1
ᶿ
ᶿ
ᶿ
ᶿ
ᶿ
ᶿ
ᶿ
ᶿ

Expresiones:
aB
bB                                                          (a,b)B  L()=((abB) B/n ≥0)
B
aBaBB

Comentarios

Publicar un comentario

Entradas más populares de este blog

Traductores: Ensambladores, compiladores e intérpretes

  Ensambladores:  son los encargados de transformar o traducir los programas escritos en ensamblador a su equivalente en código maquina o binario para que pueda ser ejecutado por la CPU. Este fue el primer lenguaje de programación que tradujo el lenguaje maquina a un lenguaje más natural para el ser humano. Con todo esto podemos decir que el lenguaje ensamblador es un lenguaje de programación de bajo nivel que se utiliza para escribir programas para computadoras, es la representación más directa del código máquina comprensible por los programadores. El lenguaje ensamblador se usó para la creación de programas en el pasado, actualmente se usa muy poco. Únicamente cuando se requiere un control directo del hardware o se quiere conseguir rendimientos poco comunes de los equipos. Un programa escrito con el lenguaje ensamblador seguirá los siguientes pasos: este programa tiene una serie de instrucciones que contienen las órdenes a seguir para llevar a cabo una acción. Todas...
Leer más

Clasificación de los Compiladores

El programa compilador traduce las instrucciones en un lenguaje de alto nivel a instrucciones que la computadora puede interpretar y ejecutar. Para cada lenguaje de programación se requiere un compilador separado. El compilador traduce todo el programa antes de ejecutarlo. Los compiladores son, pues, programas de traducción insertados en la memoria por el sistema operativo para convertir programas de cómputo en pulsaciones electrónicas ejecutables (lenguaje de máquina). Tipos compiladores: Una sola pasada:  examina el código fuente una vez, generando el código o programa objeto Pasadas múltiples:  requieren pasos intermedios para producir un código en otro lenguaje, y una pasada final para producir y optimizar el código producido durante los pasos anteriores. Optimación:  lee un código fuente, lo analiza y descubre errores potenciales sin ejecutar el programa. Compiladores incrementales:  generan un código objeto instrucción por instrucción (en vez de hacerlo ...
Leer más

Automatas de pila Unidad 2

Introducción De igual manera que los lenguajes regulares se pueden representar mediante autómatas finitos deterministas, los lenguajes independientes del contexto tienen su correspondencia en otro tipo de dispositivo: el Autómata a Pila (AP). Un autómata a pila es un dispositivo que tiene acceso a: Una secuencia de símbolos de entrada, que en general se representa por una cinta que se desplaza frente a un mecanismo de captación de dichos símbolos. El símbolo superior de una memoria en pila (LIFO) Un autómata a pila se encuentra en cada momento en un estado determinado y el estado siguiente depende de los tres elementos siguientes:  estado actual símbolo de entrada  símbolo superior de la pila Generalmente, el autómata a pila es no determinista en el sentido de que se permite que haya varias acciones posibles en cada momento. Un AP puede realizar dos tipos de operaciones elementales: Dependientes de la entrada.  Se lee la cinta y se av...
Leer más