Lenguajes

Teoría de Autómatas I Máquinas de Turing y lenguajes estructurados por frases

-1-

MÁQUINAS DE TURING Y LENGUAJES ESTRUCTURADOS POR FRASES
MÁQUINAS DE TURING - Son máquinas teóricas capaces de aceptar lenguajes generados por gramáticas estructuradas por frases. - Una máquina de Turing tiene una cabeza de lectura/escritura que avanza bidireccionalmente por una cinta infinita por la derecha.• Entrada: contenido inicial de la cinta. • Salida: contenido final de la cinta. - Símbolos de cinta: • Símbolos de entrada: Σ • Símbolos de cinta: Γ ⊇ Σ - Transiciones: δ(p,x) = (q,y) donde: • p,q: estados • x ∈ Σ : símbolo de entrada • y ∈ Γ ∪ {L,R} : símbolo de cinta o desplazamiento - En una transición, la máquina de Turing lee un símbolo de la cinta, cambia de estado y escribe un símbolo oefectúa un desplazamiento a izquierda o derecha. - Ejemplo de diagrama de transiciones

- Proceso de reconocimiento de una cadena: • Se parte del estado inicial, y la cinta contiene símbolos de entrada. • Se efectúan las transiciones pertinentes según la función de transición. • Si la cabeza lectora rebasa el extremo izquierdo de la cinta, la cadena es rechazada y el proceso termina (terminaciónanormal). • Si la máquina alcanza el estado de parada, la cadena es aceptada.

Teoría de Autómatas I Máquinas de Turing y lenguajes estructurados por frases

-2-

- MT: M(S,Σ,Γ,δ,i,h) • S: conjunto finito de estados. • Σ: alfabeto de entrada. • Γ: alfabeto de símbolos de cinta. • δ: función de transición (determinista): S x Γ → S x (Γ∪{L,R}). • i: estado inicial. • h: estado de aceptación o deparada. - En general, las máquinas de Turing son deterministas. TESIS DE TURING El poder computacional de una máquina de Turing es tan grande como el de cualquier sistema computacional posible. COMBINACIÓN DE MÁQUINAS DE TURING - Pasos: 1. Eliminar la característica de inicio de los estados iniciales de todas las máquinas, excepto de la primera. 2. Eliminar la característica de parada de todaslas máquinas, e incluir un nuevo estado de parada. 3. Para cada estado de parada p y para cada x ∈ Γ: a) Si la nueva máquina se debe detener al llegar a p con x, añadir un arco x/x de p al nuevo estado de parada. b) Si al llegar al estado p con el símbolo actual x la máquina compuesta debe transferir el control a la máquina M(S,Σ,Γ,δ,i,h), dibujar un arco con etiqueta x/z de p al estado q de M talque δ(i,x) = (q,z). CONSTRUCCIÓN MODULAR DE MÁQUINAS DE TURING - Construcción de máquinas de Turing complejas a partir de bloques elementales. x - Transferencia de control entre máquinas: → M1  → M2  - Transferencia de control con varios símbolos: x, y, z w w → M1  →} → M2 → M3 

Teoría de Autómatas I Máquinas de Turing y lenguajes estructurados por frases

-3-

Bloques deconstrucción básicos

- Bloques más complejos

Teoría de Autómatas I Máquinas de Turing y lenguajes estructurados por frases

-4-

Teoría de Autómatas I Máquinas de Turing y lenguajes estructurados por frases

-5-

EVALUACIÓN DE CADENAS - Aceptación de una cadena • Situación inicial: ∗ Cabeza en el extremo izquierdo de la cinta. ∗ La cadena de entrada empieza en la segunda posición de lacinta. • Situación final: ∗ Máquina de Turing en estado de parada. - Lenguaje aceptado por una máquina de Turing: conjunto de cadenas que acepta. - Una máquina de Turing puede escribir un mensaje de aceptación si acepta una cadena. • Mensaje de aceptación: ∆Y∆∆∆ - Símbolos especiales • #: extremo izquierdo de la cinta • *: extremo derecho de la porción alterada de la cinta - Si la máquina es M, lamáquina final es:

• M0 es igual que M, salvo que: ∗ Si M0 alcanza #, se desplazará una casilla a la izquierda (terminación anormal) ∗ Si M0 alcanza *, debe desplazarlo un lugar a la derecha ejecutando → R * L∆

Teoría de Autómatas I Máquinas de Turing y lenguajes estructurados por frases

-6-

Máquinas de Turing de varias cintas - Cada cinta tiene su propia cabeza de lectura/escritura....