automatas

Views:
 
Category: Entertainment
     
 

Presentation Description

...

Comments

Presentation Transcript

Teoría de Autómatas I : 

Teoría de Autómatas I 2º curso Ingeniería Técnica en Informática de Sistemas UNED

Sesión 8 : 

Teoría de Autómatas I 2º Ing. Tec. Informática Sistemas Josep Silva Galiana Sesión 8 Construcción Modular de Máquinas de Turing

Máquinas de Turing : 

Teoría de Autómatas I 2º Ing. Tec. Informática Sistemas Josep Silva Galiana Máquinas de Turing Bloques de construcción básicos Máquinas R, L y x (Página 153) Máquinas Rx, Lx, R¬x, R¬y (Página 154) Máquinas SR, SL (Página 155) Los bloques de construcción básicos se pueden combinar: Figura 3.4 (Página 153) Ejemplos: Figuras 3.8, 3.9, 3.10 (Página 156)

Máquinas de Turing : 

Teoría de Autómatas I 2º Ing. Tec. Informática Sistemas Josep Silva Galiana Máquinas de Turing Las máquinas de Turing se pueden combinar: 2 Ejercicios: Construir una máquina de Turing para: A = Mover la cabeza una celda hacia la izquierda B = Encontrar la primera x a la derecha de la celda actual C = Encontrar la primera y a la derecha de la celda actual Componer las máquinas A, B y C siguiendo el esquema Solución página 151

Máquinas de Turing : 

Teoría de Autómatas I 2º Ing. Tec. Informática Sistemas Josep Silva Galiana Máquinas de Turing Ejercicios: Ejercicio 1 (Página 157) Ejercicio 3 (Página 157) Ejercicio 4 (Página 158)

Máquinas de Turing : 

Teoría de Autómatas I 2º Ing. Tec. Informática Sistemas Josep Silva Galiana Máquinas de Turing Máquinas de Turing como aceptadores de lenguajes: Una máquina acepta un lenguaje si desde su estado inicial encuentra el estado de parada Las cadenas a analizar empiezan con un blanco: ∆ x x y y ∆ ∆ ∆ ∆ ∆ ∆ ∆… (Figura 3.11, página 159) Ejemplo: La máquina de la figura 3.12, página 159 acepta xnynzn

Máquinas de Turing : 

Teoría de Autómatas I 2º Ing. Tec. Informática Sistemas Josep Silva Galiana Máquinas de Turing Cuando una máquina reconoce un lenguaje puede terminar de dos formas: Simplemente parando Devolviendo un resultado, por ejemplo: ∆ Y ∆ ∆ ∆ ∆ ∆ ∆ ∆… Ejemplo: Dibujo página 161 Cualquier máquina que termine parando puede convertirse en una que devuelva “Y” y viceversa

Máquinas de Turing : 

Teoría de Autómatas I 2º Ing. Tec. Informática Sistemas Josep Silva Galiana Máquinas de Turing Máquinas de Turing de varias cintas Tienen un cabezal por cada cinta La transición la determina el estado de las cintas, y la acción solo afecta a una de ellas. Teorema 3.1 (Página 162) Para cada máquina de varias cintas existe una máquina equivalente de una cinta que acepta el mismo lenguaje Las máquinas de varias cintas NO son más potentes

Máquinas de Turing : 

Teoría de Autómatas I 2º Ing. Tec. Informática Sistemas Josep Silva Galiana Máquinas de Turing Ejercicios Ejercicio 1 (Página 171) ∆/R x / R y / R ∆/∆ ∆/R ∆/∆

Máquinas de Turing : 

Teoría de Autómatas I 2º Ing. Tec. Informática Sistemas Josep Silva Galiana Máquinas de Turing Lenguajes Estructurados por Frases Generados por Gramáticas Estructuradas por Frases Gramáticas sin restricciones Al menos deben tener un no-terminal en el lado izquierdo de las reglas Ejemplo: Figura 3.16 (Figura 172) genera xnynzn Equivalentes a los generados por las máquinas de Turing Máquina de Turing  Gramática Estructurada por Frases

Máquinas de Turing : 

Teoría de Autómatas I 2º Ing. Tec. Informática Sistemas Josep Silva Galiana Máquinas de Turing Ejercicio: Ejercicio 5 (Página 197) Solución: Modificación trivial Figura 3.12 (página 159)

authorStream Live Help