Renta 4 Renta 4 Renta 4 Renta 4 Renta 4 Renta 4 Renta 4 Renta 4 Renta 4 Renta 4 Renta 4 Renta 4
4-6_a_traductor
15
El Problema Operaciones en el Autómata con Pila Definiciones Formales Traductores Push–Down Extensión de Autómatas Universidad de Cantabria Traductores
-
Upload
nilas-arcanister -
Category
Documents
-
view
213 -
download
0
description
Universidad de Cantabria - CURSO de TEORIA DE AUTOMATAS
Transcript of 4-6_a_traductor
-
El ProblemaOperaciones en el Autmata con Pila
Definiciones Formales
Traductores PushDownExtensin de Autmatas
Universidad de Cantabria
Traductores
-
El ProblemaOperaciones en el Autmata con Pila
Definiciones Formales
Outline
1 El Problema
2 Operaciones en el Autmata con Pila
3 Definiciones Formales
Traductores
-
El ProblemaOperaciones en el Autmata con Pila
Definiciones Formales
El Problema
Hemos estudiado anteriormente los autmatas con pila yhemos visto su relacin con los lenguajes libres de contexto.Hemos visto que resuelven el problema decisional de decidir siuna palabra est en un lenguaje.
Traductores
-
El ProblemaOperaciones en el Autmata con Pila
Definiciones Formales
El Problema
Hemos visto que la estructura esta en la forma que se haderivado una palabra de un lenguaje y para esto no tenemosningn autmata que devuelva la sucesin de produccionesque generan una palabra.
Traductores
-
El ProblemaOperaciones en el Autmata con Pila
Definiciones Formales
El Problema
Para ello, utilizaremos la estructura del autmata con pila yaadiremos una cinta donde el autmata pueda escribir, i. e.una cinta de output.Adems, exigiremos que nuestro autmata sea determinstico,ya que estos son los casos ms interesantes para aplicacionesprcticas. En resumen:
Un autmata con pila. Esto es, disponemos de una cintade entrada (IT), una unidad de control con una cantidadfinita de memoria, y una pila.Una cinta de output. En la que el autmata simplementepuede escribir, no puede leer sus contenidos, y puedeavanzar un paso a la derecha siempre que la celdaanterior no est vaca.
Traductores
-
El ProblemaOperaciones en el Autmata con Pila
Definiciones Formales
El Problema
Al finalizar la computacin, si el input est en el lenguajegenerado por la gramtica de input, el contenido de la cinta deoutput es la derivacin de la palabra.
Traductores
-
El ProblemaOperaciones en el Autmata con Pila
Definiciones Formales
Read
Lee una celda en la cinta de entrada y el top de la pila.Eventualmente puede hacer operaciones de lectura en lacinta de entrada. por supuesto, lee tambin el estado actual enla unidad de control.
Traductores
-
El ProblemaOperaciones en el Autmata con Pila
Definiciones Formales
Transition
De acuerdo con una funcin de transicin el autmata indicatres operaciones bsicas a realizar en cada uno de los cuatroelementos.
Traductores
-
El ProblemaOperaciones en el Autmata con Pila
Definiciones Formales
Write and Move
En cada na de las partes realiza la accin que se indica:En la cinta de input, si ha ledo, borra la celda que ocupa yse desplaza hasta la celda siguiente. Si la lectura es unaLambda-lectura, no hace nada en la cinta de input.En la unidad de control, modifica el estado conforme seindica en la Transicin.En la pila realiza la operacin push(pop(Pila), z) donde zes el smbolo indicado por la transicin. Ser unaoperacin push si z 6= y una operacin pop si z = .En la cinta de output escribe lo que se le indique. Puedeser que no escriba nada, en cuyo caso no se mueve, o queescriba un smbolo en cuyo caso se mueve un paso a laderecha hasta la siguiente celda vaca.
Traductores
-
El ProblemaOperaciones en el Autmata con Pila
Definiciones Formales
Final de la Computacin
La computacin se termina con pila y cinta vacas. Es decir, elautmata funciona con un gran ciclo while cuya condicin deparada es que la cinta y la pila estn vacas.
Traductores
-
El ProblemaOperaciones en el Autmata con Pila
Definiciones Formales
Definicin Formal
Un traductor con pila (pushdown transducer o PDT), es unalista T := (Q,, ,,Q0, z0,F , ) donde:
1 Q es un conjunto finito (espacio de estados)2 es un alfabeto finito, llamado alfabeto del input.3 es un alfabeto finito, llamado alfabeto de la pila.4 es un alfabeto finito, llamado alfabeto del output.5 q0 Q es el estado inicial.6 F Q son los estados finales aceptadores.7 z0 es un smbolo especial, llamado fondo de la pila.8 es una correspondencia llamada funcin de transicin:
: Q ( {}) ( {z0}) Q ( {z0}) .
Traductores
-
El ProblemaOperaciones en el Autmata con Pila
Definiciones Formales
Sistema de Transicin Asociado
Denominaremos configuraciones de un traductor push-down alos elementos del conjunto
S := Q Z0 .
De la manera obvia se describen las transiciones c c entredos transiciones del sistema.
Traductores
-
El ProblemaOperaciones en el Autmata con Pila
Definiciones Formales
Sistema de Transicin Asociado
La configuracin inicial en una palabra ser dada por:
I() := (q0, ,Z0, ),
es decir, est en la cinta de input, q0 en la unidad de control,la pila est vaca y la cinta de output tambin.Una configuracin final aceptadora es una configuracin conpila y cinta vacas, esto es, una configuracin de la forma(q, , , y) con y .
Traductores
-
El ProblemaOperaciones en el Autmata con Pila
Definiciones Formales
Sistema de Transicin Asociado
Una palabra es aceptada si alcanza una configuracinfinal aceptadora dentro del sistema de transicin. Esto es, siocurre que:
I() = (q0, ,Z0, ) ` (q, , , y).
la palabra y es el resultado de la traduccin de en el caso deque omega sea aceptada por el traductor (i.e. y = ()).
Traductores
-
El ProblemaOperaciones en el Autmata con Pila
Definiciones Formales
Observaciones
Los traductores son la forma natural hallar los rboles dederivacin.Pueden tener problemas de entrar en ciclos infinitos y noson fcilmente detectables.Los traductores otros usos, aunque el objetiva principal enesta asignatura sera hallar derivaciones de palabras.
Traductores
El ProblemaOperaciones en el Autmata con PilaDefiniciones Formales
