Talfi

TALFi 2.
0
Roco Barrig uete
Mario Huete
Luis San Juan
Director: Alberto de la Encina
Facultad de Informatica
Universidad Complutense de Madrid
Curso 2009-2010
Junio 2010
2
Se autoriza a la Universidad Complutense de Madrid a difundir y uti-
lizar con nes academicos, no comerciales y mencionando expresamente a
sus autores abajo rmantes, tanto la propia memoria, como el codigo, la
documentaci on y / o el prototipo desarrollado.
Fdo.:
Luis San Juan Germ an:
Mario Jose Huete Jimenez:
Roco Barrig uete Iba nez:
Indice general
1. Resumen 5
1.1. TALFi (Versi on en castellano) . . . . . . . . . . . . . . . . . . 5
1.2. TALFi (English version) . . . . . . . . . . . . . . . . . . . . . 5
2. Objetivos 7
3. Informaci on 9
3.1. Antecedentes . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2. Problemas encontrados y resueltos en
TALFi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.2.1. Minimizacion . . . . . . . . . . . . . . . . . . . . . . . 10
3.2.2. Intento de reconocimiento de palabras simulando la
ejecuci on de un automata de pila
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.3. Introducci on a la ampliaci on de la aplicacion . . . . . . . . . . 16
3.4. Conceptos te oricos de la ampliacion . . . . . . . . . . . . . . . 18
3.4.1. Aut omata de pila . . . . . . . . . . . . . . . . . . . . . 18
3.4.2. Gramatica independiente de contexto . . . . . . . . . . 22
3.4.3. Lenguaje independiente de contexto . . . . . . . . . . . 25
3.4.4. M aquina de Turing . . . . . . . . . . . . . . . . . . . . 26
3.4.5. Algoritmo CYK
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.5. Lenguaje generado por un automata de pila . . . . . . . . . . 33
3.5.1. Pasos de simplicacion antes y despues de realizar trans-
formaciones FNC o FNG . . . . . . . . . . . . . . . . . 33
3.5.2. Algoritmo de paso de AP gram atica
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.5.3. Algoritmo de simplicaci on gram atica independiente
de contexto a FNG . . . . . . . . . . . . . . . . . . . . 37
3
4

INDICE GENERAL
3.5.4. Algoritmo de simplicaci on gram atica independiente
de contexto a FNC
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.5.5. Generacion aleatoria de palabras . . . . . . . . . . . . 45
3.5.6. Palabras reconocidas por un aut omata de pila . . . . . 46
3.6. M aquinas de Turing . . . . . . . . . . . . . . . . . . . . . . . . 46
3.6.1. Diferencias entre m aquinas de Turing con y sin estados
nales . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.6.2. Algoritmo de reconocimiento . . . . . . . . . . . . . . . 47
3.6.3. Ampliaciones y problemas . . . . . . . . . . . . . . . . 48
3.7. Cambios destacables en TALFi 2.0 . . . . . . . . . . . . . . . 48
3.7.1. Interfaz gr aca . . . . . . . . . . . . . . . . . . . . . . 48
3.7.2. Ejercicios
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4. Entorno L
A
T
E
X 57
4.1. L
A
T
E
X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.1.1. Introduccon a L
A
T
E
X . . . . . . . . . . . . . . . . . . . 57
4.1.2. Descripci on: . . . . . . . . . . . . . . . . . . . . . . . . 57
4.2. Uso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.2.1. Uso de L
A
T
E
Xen la herramienta TALFi
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.3. LatexCodeConverter
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.4. TraductorHTML . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.5. Entornos L
A
T
E
X utilizados . . . . . . . . . . . . . . . . . . . . 67
5. Palabras clave 69
6. Anexos 71
6.1. Ampliaci on del Manual de Usuario . . . . . . . . . . . . . . . 71
6.2. Cambios en la implementacion . . . . . . . . . . . . . . . . . . 72
6.3. Estructura XML de los ejercicios de aut omatas de pila . . . . 74
6.4. Estructura XML de los ejercicios de m aquinas de Turing . . . 78
Captulo 1
Resumen
1.1. TALFi (Versi on en castellano)
TALFi naci o en el curso academico 2008-2009 como una aplicaci on de
apoyo y consulta sobre teora de automatas y lenguajes formales. Su primera
versi on contena funcionalidad acerca de aut omatas nitos (deterministas, no
deterministas y con transiciones vacas), y expresiones regulares, as como su
equivalencia, simplicaci on y dem as aspectos relacionados. Para TALFi 2.0
se han creado muchas mas caractersticas adicionales, as como la mejora de
ciertos aspectos de la primera versi on, que no resultaban del todo intuitivos
para el usuario y claros en la comprensi on. Como nueva funcionalidad pode-
mos encontrar el tratamiento de automatas de pila, m aquinas de Con esta
nueva ampliaci on, TALFi se convierte en una herramienta de gran expresivi-
dad dentro del entorno de los automatas y la generaci on de lenguajes, a la
altura de otras tecnologas ya conocidas como JFLAP, etc.
1.2. TALFi (English version)
TALFi was created in the academic course of 2008-2009 as a student
support program for automaton theories and formal lenguages. Its rst ver-
sion contained united-state automaton (deterministic, non-deterministic and
generalized nondeterministic inite automaton) and regular expressions, so as
their equivalence, simplicated and more related aspects. For TALFi 2.0 has
been created a lot more of addicional options, as the improvement of some
parts of the rst version, which was not completely intuitive for the user and
clear in its comprehension. With this new ampliation, TALFi turns into a
great tool into the automaton world and the language generations, in the
same leves as JFLAP, etc.
5
Captulo 2
Objetivos
En esta segunda versi on de TALFi, como se ha mencionado antes, se ha
buscado la ampliacion de la herramienta inicial a nadiendole funcionalidad
extra para el tratamiento de gramaticas independientes de contexto (GIC),
aut omatas de pila (AP) y m aquinas de Turing (MT), parte muy importante
de la teora de automatas y lenguajes formales, as como ciertos algoritmos
necesarios para su simplicaci on, correccion y tratamiento:
La inclusion de automatas de pila y m aquinas de Turing requirio nuevas
clases para implementar su comportamiento, as como nuevos elemen-
tos gracos para su tratamiento por parte del usuario (botones para
introducir la cinta de una m aquina de Turing, nuevos ejemplos de las
nuevas representaciones . . . ).
Posteriormente fue necesario diferenciar en cierta manera un aut omata
de pila de un automata de pila determinista. Aunque TALFi no ofrece
la posibilidad al usuario de decidir si el aut omata de pila que introduce
es o no determinista, internamente TALFi si distingue este caso, ya
que es una caracterstica importante de estos aut omatas dado que por
naturaleza son no deterministas.
De forma secundaria y sin formar parte de los objetivos, tuvieron que
incluirse gramaticas independientes de contexto, en sus formas nor-
males de Chomsky y Greibach. Esto era necesario porque, parte muy
importante de TALFi (el algoritmo de reconocimiento de una palabra
por un automata de pila) requera poder pasar de gramatica a automata
de pila y viceversa.
Como parte importante de los objetivos, podemos mencionar las mejo-
ras y arreglos realizados en TALFi 1.0:
7
8 CAP
ITULO 2. OBJETIVOS
Minimizaci on: la minimizacion en TALFi 1.0 tuvo que ser corregi-
da, s olo se poda aplicar a aquellos automatas que fueran nitos
y deterministas. Gracias a TALFi 2.0 la minimizaci on es posible
adem as para aut omatas nitos no deterministas y aut omatas ni-
tos no deterministas con transiciones vacas, gracias al previo paso
de transformaci on de estos dos ultimos tipos de aut omatas en un
aut omata nito determinista. Para cerrar de manera nal la mini-
mizaci on se imprime en un archivo HTML de forma detallada las
tablas que se generan en este algoritmo para que quedasen mas
claros los pasos que se van realizando.3.2.1
TALFi 1.0 diferenciaba entre ejercicios y ejemplos, pero era posi-
ble ver la soluci on de un ejercicio propuesto por el profesor, si lo
abramos como ejemplo.3.7.2 Este comportamiento no nos pare-
ci o muy adecuado debido al caracter docente y de aprendizaje de
TALFi. Dicho comportamiento fue subsanado, adem as de incluir
mayor n umero de ejemplos y ejercicios.
Inclusi on de un modo L
A
T
E
X 4.1 con el que podemos obtener en
dicho formato, tanto los automatas que se creen en TALFi, como
los ejemplos, as como la simplicaci on de las gramaticas ante-
riormente mencionadas.
Como posible mejora futura, proponemos incluir TALFi 2.0 como una
aplicaci on web dentro de un entorno como, por ejemplo, el Campus Vir-
tual UCM. Evidentemente la herramienta segura teniendo las mismas
aplicaciones, pero la identicaci on de usuario ya no sera necesaria den-
tro de la aplicacion: estara ligada al tipo de login que se realizase en la
web. No sera la unica adaptaci on necesaria, pues el envo de ejercicios
propuestos tambien requiere hacer uso de los medios de comunicacion
con tutor del Campus Virtual UCM, para poder hacer llegar al admi-
nistrador de la aplicacion la soluci on realizada por el alumno y terminar
la correccion. En TALFi 1.0 ya se diferenci o los tipos de usuarios que
tendra la aplicacion, simulando el comportamiento y garantizando su
eciencia.
Captulo 3
Informaci on
3.1. Antecedentes
Existen muchas y diversas aplicaciones que operan con aut omatas de ma-
nera similar a como lo hace TALFi, pero la mayora de estas est an enfocadas
a un tipo de problema en concreto. Algunas tratan automatas nitos, otras
se centran en operaciones de traduccion de lenguajes, algunas incorporan si-
mulaci on de m aquinas de Turing, pero ninguna cuenta con la expresividad y
riqueza de TALFi 2.0. Para m as detalle de estas aplicaciones conviene visitar
los siguientes enlaces:
http://www.versiontracker.com/dyn/moreinfo/win/35508
Crea y simula automatas nitos y maquinas de Turing, permite guardar
la informacion en archivo, y abrir varios de estos archivos a la vez.
http://www.cs.duke.edu/csed/jflap/
Quiz a el programa mas conocido, puesto que se usa en la asignatura
de TALF. Permite crear automatas nitos, expresiones regulares, al-
goritmos de conversion entre automatas nitos y a expresion regular,
aut omatas de pila, gram aticas independientes de contexto y simulaci on
de maquinas de Turing.
http://www.ucse.edu.ar/fma/sepa/
Es espa nol. Permite dise nar, desarrollar y evaluar un conjunto de he-
rramientas de software que ayude al personal docente en la ense nanza
de las teoras y tecnologas involucradas en los procesos de dise no y
construcci on de traductores de lenguajes formales.
9
10 CAP
ITULO 3. INFORMACI
ON
http://www.brics.dk/automaton/
Trata automatas nitos, expresiones regulares, y operaciones de cierre
sobre lenguajes regulares.
Todas estas versiones pueden ser descargadas gratuitamente. Obviamente,
como antecedente mas directo contamos con la primera versi on de TALFi. A
diferencia de los programas anteriormente mencionados, TALFi dispone de
la posibilidad de ver paso a paso como se simplica una gram atica, saber si
una palabra puede ser reconocida por un aut omata de pila, generaci on de
palabras que son reconocidas por un lenguaje y multitud de posibilidades
que TALFi contempla a diferencia de sus antecesores.
Adem as, resaltar que los programas que trabajan con teora de aut omatas
y lenguajes formales est an m as enfocados al estudiante que a los profesores
que imparten esta ense nanza, y ninguno de los mencionados esta concebido
para ser utilizado como una herramienta de comunicacion y evaluaci on. Es
el rasgo principal de TALFi, que diferencia dos perles de usuario, y m as
que un apoyo en el estudio se enfoca a un posible uso real al impartir una
asignatura. Y por ultimo lo que es unico en tal es la salida que genera en
HTML de los algoritmos aplicados, y por supuesto no tienen la opcion de
generar codigo en L
A
T
E
X.
3.2. Problemas encontrados y resueltos en
TALFi
En un primer momento, tuvimos que dedicar mucho tiempo a entender
el funcionamiento de la aplicaci on, y por tanto el c odigo creado por nues-
tros compa neros el a no pasado. A continuaci on describimos en que partes
encontramos dicultades.
3.2.1. Minimizaci on
Mientras nos dedic abamos a ir un paso m as all a con la minizacion, des-
cubrimos varios fallos en este algoritmo, teniendolo que rehacer en parte,
para poder cuadrarlo con los cambios que se nos haban pedido.
En primer lugar, introducimos un estado trampa llamado tramposo,
para aclarar el estado a donde llegan las transiciones que no estan denidas
ni tienen una arista equivalente en aut omatas nitos no deterministas y
aut omatas nitos con transiciones vacas.
En segundo lugar, ampliamos la informaci on que aparece en las casillas
de la tabla que se construye para comprobar que estados son colapsables en
3.2. PROBLEMAS ENCONTRADOS Y RESUELTOS EN TALFI 11
el algoritmo de minimizacion. Anteriormente, dentro de las celdas podamos
encontrar:
Una X si los estados no se colapsaban.
Un + si los estados son colapsables.
Ahora, ampliando la informaci on de la siguiente manera:
Si los estados no son colapsables, damos los m otivos de por que: uno
puede pertenecer a los estados nales y el otro no, o si es causado por
otros dos estados que se sabe que no son colapsables y tienen tambien
su casilla marcada. Adem as, como la tabla la revisamos hasta que no
hayamos marcado ninguna nueva casilla, incluimos en que n umero de
vuelta hemos realizado el cambio en la celda.
Si los estados son colapsables dejamos la casilla en blanco.
Vease un ejemplo de la ejecuci on actual de la minimizacion de dos automatas
nitos sobre uno de los ejemplos que el a no pasado se usaba para mostrar el
funcionamiento de este algoritmo:
Aqu tenemos el aut omata sobre el que vamos a aplicar la minimizaci on,
concretamente el ejemplo 7 de los automatas nitos no deterministas:
12 CAP
ITULO 3. INFORMACI
ON
Y la tabla que obtenemos en el HTML generado cuando queremos ver
todos los pasos que hemos seguido en la minimizaci on, es la siguiente:
En cada celda podemos ver:
1. Si el estado de la columna es nal y el de la la no nal, o viceversa, los
dos estados no podran colapsarse, y lo indicamos con Final-No nal.
2. A partir de las casillas marcadas con estados que nunca podr an colap-
sarse, procedemos a comprobar que ocurre con el resto de casillas. Para
terminar la explicacion de por que se marca esa casilla, debajo o al lado
indicamos que par de estados son los causantes.
Si los estados pudieran colapsarse, la casilla no tendra nada escrito dentro
de ella.
Aqu podemos ver que salida HTML se generaba para un ejemplo sencillo,
el ejemplo 6 de automatas nitos deterministas en TALFi 1.0.
Aut omata sobre el que aplicamos el algoritmo de minimizacion:
Y la tabla que se generaba era la siguiente:
3.2.2. Intento de reconocimiento de palabras simulan-
do la ejecucion de un aut omata de pila
Al tener la aplicaci on un enfoque did actico, la primera idea que nos vi-
no a la cabeza para saber si una palabra es reconocida por un aut omata de
pila, fue seguir la misma metodologa que vimos en clase de TALF. No tra-
ducamos el automata de pila en una gram atica, sino que bamos simulando el
comportamiento que tena el aut omata seg un lea los smbolos de una cadena.
14 CAP
ITULO 3. INFORMACI
ON
B asicamente la idea de funcionamiento de este algoritmo es muy sencilla:
Es un algoritmo recursivo, que posee backtracking, pues en muchos casos
tenemos m as de un camino posible a seguir al procesar una cadena. Si en
alg un momento, al terminar de consumir los smbolos de la cadena, llegaba
a un estado de aceptaci on, o se vaciaba la pila, se devolva un booleano
que indicaba que la palabra era aceptada y se terminaba la ejecucion del
algoritmo. En caso contrario, la palabra no se aceptaba y se devolva falso.
El procedimiento que contena este algoritmo recibe como parametros:
1. Lista de estados posibles a los que podemos ir. Tiene prioridad si existe
una transicion que no consume smbolos. La idea es la siguiente: cuan-
do vamos a procesar el primer smbolo de la cadena, con transiciones
vacas es trivial, porque no hemos consumido a un ning un smbolo, pero
si no las hubiera, recopilaramos todos los posibles estados destino, y
asumiramos que ya hemos consumido un smbolo de la cadena a re-
conocer.
2. Pila actual: El estado de la pila hasta el momento. En cada estado al que
nos movemos va cambiando, as que solo la modicamos si volvemos
a llamar al procedimiento. Si en alg un momento se vaca, y si esta-
mos comprobando si la palabra es reconocida por estado, abortamos el
procesamiento.
3. N umero de elementos que tiene la pila: Includo por si en alg un momen-
to sirve para detectar los ciclos de los que hemos hablado anteriormente.
4. Cima de la pila en el momento actual: Por comodidad, y por si se
quiere comprobar el caso extremo de que si se ha desapilado el smbolo
de fondo de pila, y solo queda un smbolo en la pila, pero no coinciden,
se pare la simulacion por no poder averiguar, si se ha terminado de
vaciar la pila o no. Aqu sera facil averiguarlo, pero en la teora de
aut omatas se restringe de esta manera.
5. Palabra a procesar: Se podra haber pasado s olo como par ametro el
smbolo actual que se procesa, pero para posibles explicaciones se in-
cluy o la palabra completa.
6.

Indice del smbolo procesado: Se incluye para poder ubicar por que
smbolo de la cadena va la ejecuci on.
7. Estado: Estado actual en el que estamos, que nos sirve para poder
calcular los posibles movimientos que podemos hacer.
Este procedimiento se apoya en otros dos, que se intuyen seg un se ha
explicado como funciona: el primero, que calcula como quedar a la pila para
la siguiente llamada al procedimiento, y el segundo, que devuelve la lista de
posibles estados a los que podemos seguir procesando con un smbolo o no,
si es que la transicion es vaca, el estado actual, y la cima de pila actual.
Nos dimos cuenta que el algoritmo no terminaba si incluamos ciclos de
transiciones vacas en los que la pila no se modicase o sufriera modica-
ciones que no acercaban la ejecucion a su nal. Esto se puede arreglar de dos
maneras:
Dando prioridad a las aristas que consuman smbolos, pues si alguna
sale de alguno de los estados que componen el ciclo tendremos la opor-
tunidad de seguir el c omputo por otro camino, esperando que llegue a
su n. En algunos casos es una soluci on valida, pero no es suciente
pues podra no llevarnos a un estado que estuviera fuera de los estados
que componen el ciclo, y seguiramos teniendo el mismo problema.
Fijando una cota que s olo utilizaremos en los casos en que simulando
la ejecucion del automata hayamos elegido seguir el camino marcado
por una arista que no consuma smbolos. Si entramos en un ciclo co-
mo los ya descritos, comenzamos a acumular las veces que ejecutamos
el algoritmo. Si ejecutamos (n umero de estados * n umero de aristas)
movimientos y no hemos avanzado en nuestro procesamiento de la ca-
dena, asumimos que el algoritmo no terminara forzando as que nalize
la ejecucion.
El algoritmo se basa en dos metodos: uno que indica si se reconoce o no
una cierta cadena por estado nal, y otro que realiza la misma accion pero
vaciando la pila. Los dividimos por un lado para mejorar la eciencia, ya
que se puede dar el caso de que el aut omata de pila no tenga ning un estado
nal, o ninguna arista desapile el smbolo de fondo de pila, y devolver m as
informaci on que unicamente concretar si la palabra es aceptada o no, dando
a conocer al usuario por cu al de los dos metodos reconoce una cadena el
aut omata de pila.
Metodo reconocedor de palabras por estado nal: Se comprobar a que
la cadena, que puede ser o si es o una cadena formada por uno o
m as smbolos del alfabeto de entrada es reconocida si hemos llegado a
un estado a partir del cual no podemos ir a ning un otro comprobando
16 CAP
ITULO 3. INFORMACI
ON
la longitud de la cadena la cadena a reconocer, o en cambio si tiene
transiciones posibles donde moverse pero hemos alcanzado el nal de
la cadena. En cualquier otro caso, se contin ua con la simulaci on.
Metodo reconocedor de palabras por pila vaca: Se comprobar a si cuan-
do llegamos a un estado donde ya no podemos movernos m as la pila
est a vaca o no, y si hemos alcanzado la longitud de la cadena, que
podra ser tambien o una cadena formada por uno o m as smbolos del
alfabeto de entrada . De forma identica al metodo reconocedor por es-
tado nal, si no estamos en ese caso, comprobamos como se quedara la
pila para el siguiente paso a realizar, y si es vaca revisamos la longitud
de la cadena. En caso contrario la ejecuci on sigue su curso.
Quiz a en un futuro sean pautas que alguien pueda seguir para explicar el
funcionamiento de los aut omatas de pila. Nosotros bamos a utilizarlo para
probar que una palabra perteneca al lenguaje de un automata de pila, pero
el coste se disparaba a exponencial, volviendose intratable. Optamos por el
algoritmo llamado CYK 3.4.5, cuyo coste es mucho mejor, ya que es c ubico
sobre la longitud de la cadena.
3.3. Introducci on a la ampliacion de la apli-
caci on
TALFi 1.0 es capaz de crear automatas nitos deterministas, no deter-
ministas, con transiciones vacas y expresiones regulares. Como algoritmos
importantes cuenta con:
Transformacion de un aut omata con transiciones vacas a uno no deter-
minista.
Transformacion de un automata no determinista a uno determinista.
Transformacion de automata nito determinista a expresi on regular.
Minimizaci on de aut omatas nitos no deterministas.3.2.1
La interfaz de usuario de TALFi 1.0 cuenta con un arbol desplegable donde
podemos encontrar ejemplos y ejercicios que la primera versi on de TALFi
es capaz de llevar a cabo. Tambien dispone de los usuales controles para
modicar, copiar, pegar, borrar cualquier aspecto de la gura que creemos
en la zona central de la interfaz.
3.3. INTRODUCCI
ON A LA AMPLIACI
ON DE LA APLICACI
ON 17
TALFi 2.0 respeta esta estructura y le a nade una coleccion de ejemplos
de ejercicios de automatas de pila y maquinas de Turing. Sobre los primeros,
podremos realizar un estudio a fondo del lenguaje independiente de contexto
que generan, obteniendo los siguientes resultados:
Lista de palabras aleatorias que pertenecen al lenguaje.
Gram atica independiente de contexto que genera un aut omata de pila
aplicando el algoritmo de transformaci on.
Simplicaci on detallada por pasos de la gram atica que se obtiene di-
rectamente de un aut omata de pila.
Transformacion de una gramatica independiente de contexto en forma
normal de Greibach.3.4.2
Transformacion de una gramatica independiente de contexto en forma
normal de Chomsky.3.4.2
En lo que se reere a m aquinas de Turing, podremos:
Saber si una cadena de entrada es reconocida por una m aquina de
Turing. 3.6.2
Obtener la cinta de salida generada por una maquina de Turing.
Conocer si una cierta cinta de entrada hace que una m aquina de Turing
cicle.
En cuanto a los ejercicios, sobretodo en los de maquinas de Turing, los
usuarios podr an comprobar f acilmente antes de mandar su solucion al enun-
ciado propuesto que realmente es correcto. El administrador de la aplicacion,
que sera el creador de los ejercicios, determinar a la dicultad de los mismos,
ya que ademas de dibujar la soluci on, debe incluir listas de palabras que se
simular an internamente, sirviendo como ltro para la correccion.
En los automatas de pila, se deben rellenar la lista de palabras re-
conocidas por el aut omata soluci on, y tambien la lista de palabras que
deber an ser rechazadas.
En m aquinas de Turing, seg un sea necesaria la cinta resultante del
c omputo o no, deber an especicarse la lista de palabras aceptadas con
su correspondiente cinta de salida si procede, la lista de palabras re-
chazadas junto con la cinta de salida si es que hace falta, y por ultimo
una lista de palabras con las que la m aquina nunca llegara a detenerse.
18 CAP
ITULO 3. INFORMACI
ON
Y destacamos la salida en L
A
T
E
X de cualquier tipo de aut omata y
m aquinas de Turing, ya sea unicamente el diagrama que tienen aso-
ciados, como cualquier resultado de aplicacion de algoritmos generada
en HTML.
3.4. Conceptos te oricos de la ampliacion
3.4.1. Automata de pila
El aut omata de pila es, en esencia, un aut omata nito no determinista en
el que se permiten transiciones- y con una capacidad adicional: una pila en
la que se puede almacenar una cadena de smbolos de pila. La presencia de
una pila signica que, a diferencia de los automatas nitos, el automata de
pila puede recordar una cantidad innita de informaci on. Al aut omata de
pila se le permite observar el smbolo de entrada y el smbolo de lo alto de
la pila. Alternativamente, podra hacer una transici on espont anea usando
como entrada en vez de leer un smbolo de entrada. En una transicion, el
aut omata de pila:
1. Consume de la entrada el smbolo que usa una transicion. Si se usa
como entrada no se consume ning un smbolo.
2. Pasa a un nuevo estado, que podra ser o no el mismo que el estado
anterior.
3. Reemplaza el smbolo que est a en lo alto de la pila por cualquier cade-
na. La cadena puede ser , que corresponde a una extraccion de la pila.
Podra ser el mismo smbolo que apareca anteriormente en lo alto de
la pila; es decir, no se hace ning un cambio en la pila. Podra tambien
reemplazar el smbolo de lo alto de la pila por cualquier otro smbolo,
lo que cambia la parte superior de la pila, pero no quita o a nade ning un
elemento. Finalmente el smbolo de lo alto de la pila podra ser reem-
plazado por dos o m as smbolos, lo que tiene el efecto de cambiar o no el
smbolo de lo alto de la pila e introducir uno o m as smbolos adicionales.
Denici on formal de los automatas de pila:
Nuestra notaci on formal para un automata de pila incluye siete com-
ponentes. Escribimos la especicaci on de un automata de pila P como
sigue:
3.4. CONCEPTOS TE
ORICOS DE LA AMPLIACI
ON 19
P = (Q,,,,q
0
,Z
0
,F) Las componentes tienen los siguientes signica-
dos:
Q: Un conjunto nito de estados, como los estados de un aut omata
nito.
: un conjunto nito de smbolos de entrada, tambien analogo a
la correspondiente componente de un automata nito.
: Un alfabeto de pila nito. Esta componente, que no tiene an alo-
go en un automata nito, es el conjunto de smbolos que se permite
introducir en la pila.
: La funcion de transici on. Como para un automata nito, go-
bierna el comportamiento del automata. Formalmente, toma co-
mo argumento (q,a,X), donde:
1. q es un estado en Q.
2. a es, o bien un smbolo de entrada en , o bien a = , la
cadena vaca, que se supone que no es un smbolo de entrada.
3. X es un smbolo de pila, es decir, un elemento de .
La salida de es un conjunto nito de pares (p, ), donde p es el
nuevo estado y es la cadena de smbolos de pila por los que se
reemplaza X en lo alto de la pila. Por ejemplo, si = se saca un
elemento de la pila; si = X la pila no se cambia, y si = YZ, X
se reemplaza por Z y se mete Y en la pila.
q
0
: El estado inicial. El aut omata de pila esta en este estado antes
de realizar cualquier transici on.
Z
0
: El smbolo inicial. Inicialmente, la pila del automata de pila
consta de este smbolo y de nada m as.
F: El conjunto de estados de aceptaci on o estados nales.
La interpretaci on intuitiva de (q
0
,a,Z
0
) = {(q
1
,
1
),(q
2
,
2
), . . . ,(q
n
,
n
)},
con q
i
Q, a ( {}),
i

es la siguiente:
Cuando el estado del aut omata es q
0
, el smbolo que la cabeza lectora
est a inspeccionando en ese momento es a, y en la cima de la pila nos
encontramos el smbolo Z, se realizan las siguientes acciones:
20 CAP
ITULO 3. INFORMACI
ON
1. Si a , es decir no es la palabra vaca, se avanza una posicion
la cabeza lectora para inspeccionar el siguiente smbolo.
2. Se elimina el smbolo Z de la pila del aut omata.
3. Se selecciona un par (q
i
,
i
) de entre los existentes en la denicion
de (q
0
,A,Z), la funci on de transici on del aut omata.
4. Se apila la cadena
i
= A
1
A
2
. . . A
k
en la pila del automata, quedan-
do el smbolo A
1
en la cima de la pila.
5. Se cambia el control del aut omata al estado q
i
.
Ejemplo Sea el siguiente lenguaje independiente de contexto
L = {a
k
b
k
| k 0 }; formado por las cadenas L = { , ab, aabb,
aaabbb, aaaabbbb, . . . }
Dicho lenguaje puede ser reconocido por el siguiente automata de pila:
M = ({q
0
, q
1
, q
2
, q
3
}, {a,b}, {A,A}, , q
0
, {q
0
, q
3
}), donde las transi-
ciones son:
(q
0
, a, ) = {(q
1
, A)}
(q
1
, a, ) = {(q
1
, A)}
(q
1
, b, A) = {(q
2
, )}
(q
1
, b, A) = {(q
3
, )}
(q
2
, b, A) = {(q
2
, )}
(q
2
, b, A) = {(q
3
, )}
(q, , ) = para cualquier (q,,)
El signicado de las transiciones puede ser explicado analizando la
primera transici on:
(q
0
, a, ) = {(q
1
, A)}
donde q
0
es el estado actual, a es el smbolo en la entrada y se extrae
de la cima de la pila. Entonces, el estado del aut omata cambia a q
1
y
el smbolo A se coloca en la cima de la pila.
La idea del funcionamiento del automata es que al ir leyendo los diferen-
tes smbolos del alfabeto de entrada , estos pasan a la pila en forma
3.4. CONCEPTOS TE
ON 21
de smbolos del alfabeto de pila. Al aparecer el primer smbolo b en la
entrada, se comienza el proceso de desapilado, de forma que coincida el
n umero de smbolos b ledos con el n umero de smbolos A que aparecen
en la pila.
Aut omata de pila determinista:
Aunque a los aut omatas de pila se les permite, por denici on, ser no
deterministas, el subcaso determinista es bastante importante. En par-
ticular, los analizadores sint acticos se comportan generalmente como
aut omatas de pila deterministas, por lo que el conjunto de lenguajes
que pueden ser aceptados por estos automatas es interesante, por las
ideas que nos da sobre que construcciones es adecuado usar en los
lenguajes de programaci on. En esta secci on deniremos los aut omatas
de pila deterministas e investigaremos algunas de las cosas que pueden
hacer y no hacer.
Denici on de un automata de pila determinista:
Intuitivamente, un automata de pila es determinista si en ninguna
situaci on puede elegir entre dos o mas movimientos alternativos. Es-
tas alternativas son de dos tipos. Si (q,a,X) contiene m as de un par, el
aut omata de pila es no determinista, porque se puede elegir entre estos
pares al decidir el siguiente movimiento. Sin embargo, incluso aunque
(q,a,X) tenga siempre un unico elemento, aun sera posible elegir entre
usar un smbolo de entrada o hacer un movimiento sobre . Decimos
que un automata de pila P = (Q,,,,q
0
,Z
0
,F) es determinista (y lo
llamamos APD, iniciales de aut omata de pila determinista), si y solo
si se cumplen las siguientes condiciones:
1. (q,a,X) tiene como m aximo un elemento para cualquier q en Q,
a en o a = , y X en .
2. Si (q,a,X) no est a vaco para alg un a en , (q,,X) debe estar
vaco.
22 CAP
ITULO 3. INFORMACI
ON
Ejemplo de un aut omata de pila determinista en TALFi:
3.4.2. Gramatica independiente de contexto
Una gramatica independiente de contexto es una notacion formal que
sirve para expresar las deniciones recursivas de los lenguajes. Una gram atica
consta de una o mas variables que representan las clases de cadenas, es decir,
los lenguajes. Existen reglas que establecen como se construyen las cadenas
de cada clase. La construcci on puede emplear smbolos del alfabeto, cadenas
que se sabe que pertenecen a una de las clases, o ambos elementos.
Deni on formal:
Existen cuatro componentes importantes en una descripci on gramatical
de un lenguaje:
1. Un conjunto nito de smbolos que forma las cadenas del lengua-
je que se esta deniendo. Denominamos a este conjunto alfabeto
terminal o alfabeto de smbolos terminales.
2. Un conjunto nito de variables, denominado tambien en ocasiones
smbolos no terminales o categoras sint acticas. Cada variable re-
presenta un lenguaje; es decir, un conjunto de cadenas.
3.4. CONCEPTOS TE
ON 23
3. Una de las variables representa el lenguaje que se esta deniendo;
se denomina smbolo inicial. Otras variables representan las clases
auxiliares de cadenas que se emplean para denir el lenguaje del
smbolo inicial.
4. Un conjunto nito de producciones o reglas que representan la
denici on recursiva de un lenguaje. Cada producci on consta de:
Una variable a la que dene (parcialmente) la producci on. Es-
ta variable a menudo se denomina cabeza de producci on.
El smbolo de produccion .
Una cadena formada por cero o mas smbolos terminales y
variables. Esta cadena, denominada cuerpo de la produccion,
representa una manera de formar cadenas pertenecientes al
lenguaje de la variable de la cabeza. De este modo, dejamos
los smbolos terminales invariables y sustituimos cada una
de las variables del cuerpo por una cadena que sabemos que
pertenece al lenguaje de dicha variable.
Los cuatro componentes que acabamos de describir denen una gramatica
independiente de contexto (GIC), o simplemente una gram atica. Re-
presentamos una gramatica independiente de contexto G mediante sus
cuatro componentes, es decir, G=(V,T,P,S), donde V es el conjunto
de variables, T son los smbolos terminales, P es el conjunto de pro-
ducciones y S es el smbolo inicial.
Ejemplos:
1. Una simple gram atica independiente de contexto es
S aSb |
donde | es un o l ogico y es usado para separar m ultiples opciones
para el mismo smbolo no terminal, indica una cadena vaca.
Esta gramatica genera el lenguaje no regular {a
n
b
n
: n 0 } .
2. Aqu hay una gram atica independiente de contexto para expre-
siones enteras algebraicas sintacticamente correctas sobre las vari-
ables algebraicas, que son smbolos terminales en la gram atica, x,
y, z:
24 CAP
ITULO 3. INFORMACI
ON
S x | y | z | S + S | S - S | S *S | S/S | (S)
Generara, por ejemplo, la cadena (x + y) *x - z *y / (x + x)
3. Una gramatica independiente de contexto para un lenguaje con-
sistente en todas las cadenas que se pueden formar con las letras
a y b, habiendo un n umero diferente de una que de otra, sera:
S U | V
U TaU | TaT
V TbV | TbT
T aTbT | bTaT |
T genera todas las cadenas con la misma cantidad de letras a que
b, U genera todas las cadenas con m as letras a, y V todas las
cadenas con m as letras b.
4. Otro ejemplo para un lenguaje es {a
n
b
m
c
m+n
: n 0, m 0 } . No
es un lenguaje regular, pero puede ser generado por la siguiente
gram atica independiente de contexto.
S aSc | B
B bBc | E
Formas normales:
Forma normal de Greibach:
Una gram atica independiente de contexto (GIC) est a en forma
normal de Greibach (FNG) si todas y cada una de sus reglas de
producci on tienen un consecuente que empieza por un caracter
del alfabeto, tambien llamado smbolo terminal. Formalmente,
cualquiera de las reglas tendr a la estructura:
A aw
Donde A es el antecedente de la regla, que en el caso de las GIC
debe ser necesariamente un solo smbolo auxiliar. Por su parte,
a es el mencionado comienzo del consecuente y, por tanto, un
smbolo terminal. Finalmente, w representa una concatenaci on
3.4. CONCEPTOS TE
ON 25
generica de elementos gramaticales, esto es, una sucesion exclusi-
vamente de auxiliares, inclusive, pudiera ser la palabra vaca; en
este caso particular, se tendra una regla llamada terminal:
A a
Existe un teorema que prueba que cualquier GIC, cuyo lenguaje
no contiene a la palabra vaca, si no lo est a ya, se puede transfor-
mar en otra equivalente que s este en FNG. Para su demostracion,
normalmente, se procede por construcci on, es decir, se plantea di-
rectamente un algoritmo capaz de obtener la FNG a partir de una
GIC dada.
Forma normal de Chomsky:
Una gram atica formal esta en forma normal de Chomsky si todas
sus reglas de producci on son de alguna de las siguientes formas:
A BC o
A a
donde A, B y C son smbolos no terminales (o variables) y a es
un smbolo terminal. Todo lenguaje independiente de contexto
que no posee a la cadena vaca, es expresable por medio de una
gram atica en forma normal de Chomsky (FNC) y recprocamente.
Adem as, dada una gram atica independiente de contexto, es posi-
ble algortmicamente producir una FNC equivalente, es decir, que
genera el mismo lenguaje.
3.4.3. Lenguaje independiente de contexto
Un lenguaje independiente de contexto es aquel generado por una gram atica
independiente de contexto. Estos conceptos pertenecen a un area de la Cien-
cia de la Computaci on llamada Computaci on Te orica.
Los lenguajes de programacion son lenguajes independientes del contexto.
Existe una forma mec anica de convertir la descripci on de un lenguaje como
GIC en un analizador sintactico: el componente del compilador descubre la
estructura del programa fuente y representa dicha estructura mediante un
arbol de derivacion.
Otro ejemplo es el lenguaje HTML, o tambien el lenguaje XML, cuya parte
fundamental es la DTD (Document Type Denition, denici on de tipo de
26 CAP
ITULO 3. INFORMACI
ON
documento), que principalmente es una gram atica independiente de contex-
to que describe las etiquetas permitidas y las formas en que dichas etiquetas
pueden anidarse.
3.4.4. Maquina de Turing
Descripci on:
La m aquina de Turing es un modelo computacional introducido por
Alan Turing en el trabajo On computable numbers, with an applica-
tion to the Entscheidungsproblem, publicado por la Sociedad Matem atica
de Londres en 1936, en el cual se estudiaba la cuesti on planteada por
David Hilbert sobre si las matem aticas son decidibles, es decir, si hay un
metodo denido que pueda aplicarse a cualquier sentencia matem atica
y que nos diga si esa sentencia es cierta o no. Turing ide o un modelo
formal de computador, la m aquina de Turing, y demostr o que existan
problemas que una m aquina no poda resolver. La m aquina de Turing
es un modelo matematico abstracto que formaliza el concepto de algo-
ritmo.
La maquina de Turing consta de un cabezal lector/escritor y una cinta
innita en la que el cabezal lee el contenido, borra el contenido anterior
y escribe un nuevo valor. Las operaciones que se pueden realizar en esta
m aquina se limitan a:
1. avanzar el cabezal lector/escritor hacia la derecha.
2. avanzar el cabezal lector/escritor hacia la izquierda.
El c omputo es determinado a partir de una tabla de estados de la forma:
(estado, valor) (nuevo estado, nuevo valor, direcci on)
Esta tabla toma como par ametros el estado actual de la m aquina y el
car acter ledo de la cinta, dando la direcci on para mover el cabezal, el
nuevo estado de la m aquina y el valor a ser escrito en la cinta.
Con este aparato extremadamente sencillo es posible realizar cualquier
c omputo que un computador digital sea capaz de realizar.
Mediante este modelo teorico y el analisis de complejidad de algorit-
mos, fue posible la categorizaci on de problemas computacionales de
3.4. CONCEPTOS TE
ON 27
acuerdo a su comportamiento, apareciendo as, el conjunto de proble-
mas denominados P y NP, cuyas soluciones en tiempo polin omico son
encontradas seg un el determinismo y no determinismo respectivamente
de la m aquina de Turing.
De hecho, se puede probar matematicamente que para cualquier pro-
grama de computadora es posible crear una m aquina de Turing equiva-
lente. Esta prueba resulta de la tesis de Church-Turing, formulada por
Alan Turing y Alonzo Church, de forma independiente a mediados del
siglo XX.
La idea subyacente es el concepto de que una maquina de Turing es una
persona ejecutando un procedimiento efectivo denido formalmente,
donde el espacio de memoria de trabajo es ilimitado, pero en un mo-
mento determinado s olo una parte nita es accesible. La memoria se
divide en espacios de trabajo denominados celdas, donde se pueden es-
cribir y leer smbolos.
Inicialmente todas las celdas contienen un smbolo especial denomina-
do blanco. Las instrucciones que determinan el funcionamiento de la
m aquina tienen la forma, si estamos en el estado x leyendo la posicion
y, donde hay escrito el smbolo z, entonces este smbolo debe ser reem-
plazado por este otro smbolo, y pasar a leer la celda siguiente, bien a
la izquierda o bien a la derecha.
La maquina de Turing puede considerarse como un aut omata capaz
de reconocer lenguajes formales. En ese sentido es capaz de recono-
cer los lenguajes recursivamente enumerables, de acuerdo a la jerar-
qua de Chomsky. Su potencia es, por tanto, superior a otros tipos de
aut omatas, como el automata nito, o el aut omata con pila, o igual a
otros modelos con la misma potencia computacional.
Nociones preliminares:
Podemos imaginarnos una m aquina de Turing de la manera siguiente: la
m aquina consta de una unidad de control, que puede estar en cualquier
estado tomado de un conjunto nito. Hay una cinta dividida en casillas,
que puede contener un smbolo, tomado de otro conjunto nito.
28 CAP
ITULO 3. INFORMACI
ON
Inicialmente, se sit ua en la cinta de entrada, que es una cadena de
smbolos de longitud nita, elegidos del alfabeto de entrada. El resto
de las casillas de la cinta, que se extiende innitamente hacia la derecha
y la izquierda, contiene, inicialmente, un smbolo denominado espacio
en blanco.
El espacio en blanco es un smbolo de cinta, pero no un smbolo de
entrada, y puede haber tambien otros smbolos de cinta adem as de los
smbolos de entrada y del espacio en blanco.
Existe una cabeza de cinta que siempre esta situada sobre una de las
casillas de la cinta. Se dice que la m aquina de Turing est a se nalando
dicha casilla. Al principio, la cabeza de la cinta se encuentra en la casilla
de entrada que se encuentra m as a la izquierda y no es un blanco.
Un movimiento de la m aquina de Turing es una funci on del estado de
la unidad de control, del smbolo de la cinta y de la direccion. En un
movimiento, la m aquina de Turing:
1. Cambiara de estado. Opcionalmente, el siguiente estado puede ser
el mismo que el actual.
2. Escribira un smbolo de cinta en la casilla se nalada por la cabeza.
Este smbolo de cinta sustituye al smbolo que estuviera ante-
riormente en la casilla. Opcionalmente, el smbolo escrito puede
ser el mismo que haba en dicha casilla.
3. Mover a la cabeza de la cinta hacia la izquierda o hacia la derecha.
En nuestro formalismo, no se exige que haya un movimiento, y se
permite que la cabeza permanezca en el mismo lugar.
3.4. CONCEPTOS TE
ON 29
Denici on formal de una maquina de Turing:
La notaci on formal que utilizaremos para una m aquina de Turing es
similar a la utilizada para los automatas nitos o para los automatas
de pila.
M = (Q,,,,q
0
,#,F) cuyas componentes tienen el siguiente signica-
do:
Q: El conjunto nito de estados de la unidad de control.
: El conjunto nito de smbolos de entrada.
: El conjunto completo de smbolos de cinta; siempre es un
subconjunto de .
: La funci on de transici on. Los argumentos de (q,X) son un esta-
do q y un smbolo de cinta X. El valor de (q,X), si est a denido,
es una tupla (p,Y,S), donde:
1. p es el estado siguiente de Q.
2. Y es el smbolo de , que se escribe en la casilla se nalada
por la cabeza de la cinta y que sustituye al smbolo que se
encontraba en dicha casilla.
3. S es un sentido, I, D o N (izquierda, derecha o ninguno
respectivamente), que nos indica el sentido en el que se mueve
la cabeza.
q
0
: El estado inicial (uno de los elementos de Q) en el cual se
encuentra inicialmente la unidad de control.
#: El smbolo de espacio en blanco. Este smbolo forma parte de
pero no de ; es decir, no es un smbolo de entrada. El espacio
en blanco aparece inicialmente en todas las casillas de la cinta,
excepto en aquellas que contienen los smbolos de la entrada.
F: El conjunto de estados nales o de aceptaci on, que constituye
un subconjunto de Q.
Ejemplo:
Denimos una maquina de Turing sobre el alfabeto {0,1}, donde 0
representa el smbolo blanco. La maquina comenzar a su proceso situa-
da sobre un smbolo 1 de una serie. La maquina de Turing copiara el
n umero de smbolos 1 que encuentre hasta el primer blanco detr as
de dicho smbolo blanco. Es decir, situada sobre el 1 situado en el ex-
tremo izquierdo, doblara el n umero de smbolos 1, con un 0 en medio.
30 CAP
ITULO 3. INFORMACI
ON
As, si tenemos la entrada 111 devolver a 1110111, con 1111 de-
volvera 111101111, y sucesivamente.
El conjunto de estados es {q
1
, q
2
, q
3
, q
4
, q
5
} y el estado inicial es q
1
.
La tabla que describe la funci on de transici on es la siguiente:
Estado Smbolo ledo Smbolo escrito Mov. Estado sig.
q
1
1 0 D q
2
q
1
1 0 D q
2
q
2
1 1 D q
2
q
2
0 0 D q
3
q
3
0 1 I q
4
q
3
1 1 D q
3
q
4
1 1 I q
4
q
4
0 0 I q
5
q
5
1 1 I q
5
q
5
0 1 D q
1
El funcionamiento de una computacion de esta maquina se puede mostrar
con el siguiente ejemplo (en negrita se resalta la posicion de la cabeza
lectora/escritora):
Paso Estado Cinta
1 q
1
11
2 q
2
01
3 q
2
010
4 q
3
0100
5 q
4
0101
6 q
5
0101
7 q
5
0101
8 q
1
1101
9 q
2
1001
10 q
3
1001
11 q
3
10010
12 q
4
10011
13 q
4
10011
14 q
5
10011
15 q
1
11011
Parada
3.4. CONCEPTOS TE
ON 31
La m aquina realiza su proceso por medio de un bucle, en el estado
inicial q1, reemplaza el primer 1 con un 0, y pasa al estado q2, con el que
avanza hacia la derecha, saltando los smbolos 1 hasta un 0 (que debe
existir), cuando lo encuentra pasa al estado q3, con este estado avanza
saltando los 1 hasta encontrar otro 0 (la primera vez no habra ning un
1). Una vez en el extremo derecho, a nade un 1. Despues comienza el
proceso de retorno; con q4 vuelve a la izquierda saltando los 1, cuando
encuentra un 0 (en el medio de la secuencia), pasa a q5 que contin ua
a la izquierda saltando los 1 hasta el 0 que se escribi o al principio. Se
reemplaza de nuevo este 0 por 1, y pasa al smbolo siguiente, si es un 1,
se pasa a otra iteraci on del bucle, pasando al estado q1 de nuevo. Si es
un smbolo 0, ser a el smbolo central, con lo que la m aquina se detiene
al haber nalizado su computo.
3.4.5. Algoritmo CYK
El algoritmo de Cocke-Younger-Kasami (CYK) determina si una cadena
puede ser generada por una gram atica independiente de contexto y, si es
posible, c omo puede ser generada. Este proceso es conocido como an alisis
sint actico de la cadena.
La versi on est andar CYK reconoce lenguajes denidos por una gramatica
independiente de contexto escrita en la forma normal de Chomsky. Cualquier
gram atica independiente de contexto puede ser convertida a FNC sin mucha
dicultad, CYK puede usarse para reconocer cualquier palabra de lenguaje
independiente de contexto.
Consiste en crear una tabla, de tama no como la cadena a reconocer, siem-
pre que la cadena sea distinta de , pues en ese caso solo basta comprobar
si es una producci on de la variable inicial. Cada celda la rellenamos con la
lista de variables que nos pueden permitir crear las subcadenas basadas en la
cadena dada, hasta que llegamos a la celda de la primera columna y la la de
la longitud de la cadena. Si esta contiene a la variable inicial, es que a partir
de ella podramos derivar la cadena original, y por tanto sera reconocida por
la gramatica, y en consecuencia por el aut omata de pila.
En el peor caso asint otico la complejidad temporal de CYK es c ubica
sobre la longitud de la cadena analizada. Esto hace a este algoritmo uno de
los m as ecientes en el reconocimiento de cadenas de los lenguajes indepen-
dientes de contexto.
32 CAP
ITULO 3. INFORMACI
ON
Podemos ver una codicacion simplicada en pseudocodigo del algoritmo:
Entrada : G=(V, T, P, S) en FNC y w = w
1
w
2
. . . w
n
(w= )
Salida : Cierto (si w L(G)) o Falso (si w / L(G))
Metodo :
Para i=1 hasta n
V
i1
= { A : A w
i
P }
finPara
Para j=2 hasta n
Para i=1 hasta n-j+1
V
ij
=
Para k=1 hasta j-1
V
ij
= V
ij
{ A : A BC P, B V
ik
, C V
i+k
, j-k }
finPara
finPara
finPara
Si S V
1n
devolver Cierto
sino devolver Falso
3.5. LENGUAJE GENERADO POR UN AUT
OMATA DE PILA 33
3.5. Lenguaje generado por un aut omata de
pila
Esta parte fue la que nos llevo m as tiempo, pues como hemos explicado
antes, seguimos una lnea de trabajo que desafortunadamente nos llevo a un
callej on sin salida. Nos centramos en palabras que pertenecan al lenguaje,
punto importante pero no el vital para el que sirven los automatas: denir
un lenguaje.
3.5.1. Pasos de simplicacion antes y despues de rea-
lizar transformaciones FNC o FNG
Estamos acostumbrados en los ejemplos a ver gram aticas con pocos smbo-
los de variable, y en general bastante simplicadas. Al aplicar el algoritmo
que nos da la gramatica independiente de contexto asociada, vimos que a un
teniendo pocos estados, en el momento que el n umero de aristas comienza a
crecer, obtenemos unas gram aticas bastante grandes, y nos vimos en la obli-
gaci on de reducirlas adaptando las reglas de simplicacion de una gramatica:
Eliminaci on de variables sin producciones.
Sustituci on de una variable por su produccion si s olo tiene asociada a
ella una unica produccion y es .
Sustituci on de una variable por su produccion si s olo tiene asociada a
ella una unica produccion.
Eliminaci on de producciones para variables inalcanzables.
Eliminaci on de producciones que cuya cabeza no sea la variable inicial.
Renombramiento de variables.
Las tres primeras normas se aplican antes de comentar la transformaci on
en forma normal de una gram atica. Nos permiten reducir y dejar mucho m as
claro el lenguaje que denen. Las dos siguientes las aplicamos para simpli-
car el resultado nal, pues las formas normales tienen unas caractersticas
estrictas, por tanto en algunos casos no hara ni falta aplicarlas, y en otros es
necesario porque no se aplicaron al principio.
A continuaci on mostramos algunos de estos resutados que aparecen en el
archivo HTML que se genera con la simplicaci on de gramaticas independi-
entes de contexto.
34 CAP
ITULO 3. INFORMACI
ON
Puede verse una breve descripci on del paso de simplicaci on a realizar,
y sobre que variables se hace, y a continuaci on mostramos la gramatica re-
sultante. As hasta renombrar las variables para que la gramatica quede a la
forma en la que estamos habituados a tratar.
OMATA DE PILA 35
3.5.2. Algoritmo de paso de AP gramatica
Encontramos muchas dicultades, pues este algoritmo viene detallado
muy formalmente y los ejemplos que pudimos encontrar no eran demasiado
aclaratorios. Para realizar esta nueva funcion, hemos incluido en el men u de
algoritmos el bot on Simplicacion GIC:
En primer lugar, tenemos que distinguir si el aut omata de pila tiene estados
nales o no. Si se da el primer caso, tenemos que convertir el automata dado
36 CAP
ITULO 3. INFORMACI
ON
en otro equivalente que reconozca el mismo lenguaje por pila vaca que por
estado nal. Para ello, seguimos el algoritmo que nos dice c omo hacerlo:
Se debe incluir un nuevo estado inicial y un nuevo fondo de pila. Se
a nade una transicion vaca que vaya al estado inicial antiguo, que apile
el antiguo fondo de pila sobre el nuevo.
Se incluye un nuevo estado, que sera donde se proceda a desapilar todos
los smbolos que pudiera haber apilados en el momento de aceptaci on
de la cadena cuando era aceptada por estado nal. Se a nade una tran-
sici on vaca desde cada estado nal que desapile para cada smbolo
del alfabeto de pila y que vaya al nuevo estado. Por ultimo, en este
nuevo estado existir an aristas con las mismas caractersticas que las
anteriores. As, nos aseguramos que, sea posible la transici on o no, se
desapilara siempre la pila.
En ning un caso modicamos el automata que dibuje el usuario, haremos
una copia de el. Creemos que no es necesario porque es una conversion nece-
saria para ejecutar el algoritmo, y es bastante intuitivo el cambio, pero si
en un futuro se desea se podra sustituir el original por el nuevo calculado a
partir de el.
Una vez que tenemos el aut omata libre de estados nales, aplicamos el
algoritmo que nos convierte un aut omata de pila en una gram atica indepen-
diente del contexto. Consiste en lo siguiente:
OMATA DE PILA 37
El smbolo inicial de la gram atica ser a S. Para cada estado p del
aut omata, siendo q
0
el estado inicial tendremos la producci on
S [q
0
Zp]
Si existe una transici on tal que desapile la cima de la pila,
(p,Z,a) = (q, ), a nadimos la producci on [pZq] a. Esta a puede ser
tambien .
Por ultimo, para transiciones (p,Z,a) = (q,A
1
A
2
. . . A
n
), debemos
construir todas las listas de estados de longitud n, y crear para ca-
da lista la produccion: [pZr
k
]= a[qA
1
r
1
][r
2
A
2
r
3
] . . . [r
k1
A
n
r
k
]. Aqu a
tambien puede ser .
Una vez que tenemos la gram atica, la simplicamos, pues en muchos casos
ayuda a reducir los smbolos de variable. Sustituimos todas las variables
con producciones unitarias excepto con la variable inicial, y eliminamos las
producciones que sean vacas siempre y cuando no aparezcan en S. Para hacer
m as f acil al usuario el entender la gram atica, cambiamos los smbolos de
producci on, que hasta el momento eran del tipo [qZp], por letras may usculas
del abecedario. Creemos que es bastante grande y que no es probable que
ninguna gram atica rebase ese n umero de variables.
3.5.3. Algoritmo de simplicaci on gramatica indepen-
diente de contexto a FNG
Cuando ya tenemos la gram atica simplicada podemos dedicarnos a con-
vertirla en una gram atica de Greibach. Se caracteriza porque las producciones
empiezan por un smbolo terminal, como ya sabemos.
Para poder localizar que variables tienen producciones que comiencen por
otra variable, construimos una tabla cuyas las y columnas son las variables
de la gramatica. Si alguna producci on de las variables de las las comienza con
alguna de las variables de las columnas, marcamos la casilla correspondiente.
Veamoslo paso por paso, para el ejemplo de la ultima imagen:
La gramatica que nos genera este automata, es la siguiente:
38 CAP
ITULO 3. INFORMACI
ON
Y la tabla que se genera tal y como hemos dicho antes es:
Y mientras que no marquemos una casilla diagonal, es sencillo. Selecciona-
mos las casillas de la columna mas a la izquierda, y sustituimos creando pro-
ducciones nuevas de la variable marcada en la columna, incluyendolas en la
variable de la la. Este proceso es autom atico y no se muestra al usuario por
pasos, se le vuelve a mostrar la gram atica resultante de las sustituciones:
OMATA DE PILA 39
Y volvemos a generar la tabla, hasta que llegamos a un punto que la tabla
no esta marcada, y eso quiere decir que ya est a en forma normal de Greibach.
Momento en el que ya hemos terminado y devolvemos la gram atica nal:
40 CAP
ITULO 3. INFORMACI
ON
A esta gram atica que devolvemos como nal, le aplicamos otro algoritmo
de simplicaci on, el de eliminar las producciones vacas siempre que no sean
producciones de la variable inicial. Este algoritmo consiste en lo siguiente:
1. Localizamos que variables, siempre que no sea la inicial, tiene una pro-
ducci on vaca. Eliminamos la producci on vaca de sus producciones para
cada una de las variables que cumplan esta caracterstica.
2. Buscamos en el resto de las producciones de las variables si existe alguna
que contenga la variable con la producci on vaca. La sustituimos, y la
a nadimos a la lista de producciones.
3. Nos deshacemos de variables que no fueran alcanzables desde el smbo-
lo inicial, repitiendo el proceso para comprobar si su eliminaci on ha
provocado alg un cambio en la gramatica.
Consideramos que cuando la tabla no contiene marcas es el momento ideal
de proceder a eliminarlas, porque si lo hacemos antes de que este en forma
normal de Greibach, no podemos asegurar que entremos en un bucle innito
y no podamos salir de el. Por ejemplo:
Tenemos dos producciones del tipo:
A . . . | E | | . . .
E . . . | A | . . .
OMATA DE PILA 41
Siendo A, E variables de la gram atica. Si eliminamos las producciones vacas,
ocurrira lo siguiente:
1. Sustituimos las apariciones de A por . Obtendramos lo siguiente:
A . . . | E | . . .
E . . . | | . . .
2. Volveramos a estar en la misma situacion, pues seguimos teniendo una
variable con una produccion vaca.
Este problema no lo tenemos si la gram atica tiene la forma normal de Greibach,
pues nos aseguramos que el primer smbolo de la producci on es un terminal,
y nunca ocurrira el caso anterior.
Por otro lado, puede ocurrir que se marque una casilla que este en la
diagonal de la tabla. En ese caso el proceso es algo m as delicado, pues hemos
de incluir una nueva variable, ya que existe recursividad y por mucho que se
sustituya una y otra vez no podramos eliminarla.
3.5.4. Algoritmo de simplicaci on gramatica indepen-
diente de contexto a FNC
Ya que hemos incluido simplicaciones de gramatica, no podemos no in-
cluir otras de las simplicaciones, quiz a m as importante incluso que la forma
normal de Greibach: La forma normal de Chomsky.
Convertir una gram atica en forma normal de Chomsky, consiste en dos pa-
sos muy sencillos. En primer lugar, una gram atica esta en forma normal de
Chomsky si las producciones son del tipo:
A BC Siendo A, B, C V
A a Siendo a T
Y solo se puede incluir la produccion S si S no aparece en ninguna de
las producciones del resto de variables y, por supuesto, aparece en los casos
que unicamente es reconocida por la gram atica.
Con esta idea en la cabeza, es f acilmente entendible el algoritmo de transfor-
maci on, que consta de dos fases:
42 CAP
ITULO 3. INFORMACI
ON
Fase 1: Para cada smbolo terminal que pertenece a T, creamos pro-
ducciones del tipo [Ca] a para todo a T.
Fase 1.1: Reemplazamos en todas las producciones las apariciones
de smbolos terminales a por sus variables terminales [Ca] aso-
ciados que acabamos de crear.
Fase 2: Ahora tenemos que conseguir que las producciones esten for-
madas solamente por dos variables. Para ello procedemos de la siguiente
manera:
Fase 2.2: Recorremos todas las producciones. Si la longitud es
mayor o igual a 3, esto es lo que hacemos:
Imaginemos que tenemos la siguiente produccion: AA
1
A
2
A
3
. . . A
n
.
Creamos una nueva variable, [D0], que contendr a la producci on
A
2
A
3
. . . A
n
, y modicamos la produccion que acabamos de en-
contrar suplant andola por A A
1
[D0].
Esta fase 2 se repite hasta que todas las producciones tengan longitud
menor que 3, o lo que es lo mismo, que ninguna cumpla la condici on
para ser modicada.
En teora habramos acabado aqu, pero puede ocurrir, que la gramatica
original, tuviera producciones de s olo una variable, y entonces no es-
tara la forma normal de Chomsky bien construida.
Este detalle en el algoritmo no se tiene en cuenta, pero es lo que nos
ha ocurrido a lo largo de todo este a no trabajando en el proyecto:
las diferencias entre las aplicaciones te oricas, y lo que en la practica
supone estudiar todos los casos, no unicamente el general, y buscar
soluciones ecientes para devolver el resultado correcto. As que, infor-
malmente, a nadiramos un tercer paso:
Fase 3: Si en alg un momento encontramos en las producciones alguna
que consista en una variable, sustituimos esa variable por todas sus pro-
ducciones, pues en principio tendran la forma adecuada que requiere
la forma normal de Chomsky. Y nalmente diremos que la gramatica
est a simplicada en el momento que hayamos revisado todas las pro-
ducciones y no hayamos hecho ninguna modicaci on.
A continuaci on, vamos a mostrar cu al es el resultado de obtener la forma
normal de Chomsky en un automata sencillo:
OMATA DE PILA 43
Y la salida HTML mostrada con su forma normal de Chomsky, que tiene
un formato identico a la salida de la forma normal de Greibach excepto en
los pasos que sigue para llegar al resultado nal, es la siguiente:
1. Lo primero, saber cu al es la gram atica primigenia:
2. La salida obtenida de aplicar la primera fase, cuyo resultado es clara-
mente intuitivo compar andolo con la gram atica original:
44 CAP
ITULO 3. INFORMACI
ON
3. La salida obtenida de terminar con la segunda fase:
4. Observemos la produccion S A y la produccion de [D0] c omo cam-
bia al terminar con la simplicaci on y conseguir una gram atica en FNC:
OMATA DE PILA 45
3.5.5. Generaci on aleatoria de palabras
Como ya sabemos, los aut omatas de pila denen lenguajes. El uso de la
pila diculta en algunos casos saber c omo son las cadenas reconocidas, por
tanto implementamos una manera de conseguir una lista que mostrase al-
gunas de las palabras reconocidas. Esta lista contiene como maximo cinco
palabras. En un primer momento pensamos en que tuviera diez, pero para
gram aticas con muchas variables, es muy probable que tengan muchas pro-
ducciones para cada una de ellas, aumentando considerablemente el coste
y el uso de memoria. Despues de tener esta informaci on, cogemos las pro-
ducciones de la variable inicial, y creamos una lista donde iremos guardando
las derivaciones por la izquierda que podramos construir con la gram atica.
Y a partir de aqu, el algoritmo consiste en lo siguiente:
Mientras que la lista de palabras construidas no llegue a cinco, haremos
lo siguiente:
Cogemos la primera derivaci on de la produccion y la eliminamos de la
lista.
Si est a formada solamente por smbolos terminales, la eliminamos de la
lista y la metemos en la lista de palabras reconocidas por el aut omata.
Si no, buscamos el primer smbolo de variable que aparezca por la
izquierda. En caso de que esa variable pertenezca a la lista que cal-
culamos antes de variables con producciones que son un terminal, la
sustituimos por todas las producciones que tenga de ese tipo, y se
a naden las diferentes derivaciones resultantes para cada sustitucion.
46 CAP
ITULO 3. INFORMACI
ON
La longitud de la lista es un par ametro f acilmente modicable para futuras
mejoras de la aplicacion, pues est a denida como una constante. Conside-
ramos no dejarla a la eleccion del usuario, porque la idea de mostrar esta
lista es que el usuario tenga una ligera intuici on del lenguaje generado por
el aut omata, animando a que sea el mismo el que profundice en las cadenas
que pertenecen al lenguaje y tambien en las que no.
3.5.6. Palabras reconocidas por un automata de pila
Ya explicamos al comienzo como fue nuestro primer intento de vericar
cu ando una cadena es reconocida por un automata de pila, y c omo al nal
optamos por utilizar el algoritmo CYK.
La salida de la tabla que se genera se puede ver por consola unicamente pues
consideramos que a el usuario no le importa como se obtiene el resultado,
sino el valor del mismo.
Para cada palabra que se va a comprobar en la correccion de ejercicios
de aut omata de pila, se guarda el resultado del CYK, por si en un futuro
quiere devolverse esta informacion para ampliar la funcionalidad de TALFi.
Nosotros mismos pensamos que sera interesante incluir alg un aparatado en
el men u con esta funci on, pero nalmente consideramos que la generacion
aleatoria de palabras era suciente para comprender las cadenas aceptadas
por un aut omata de pila.
3.6. Maquinas de Turing
3.6.1. Diferencias entre maquinas de Turing con y sin
estados nales
Hemos decidido un tratamiento diferente en las m aquinas de Turing que
contienen estados nales de las que no, al responder a la cuesti on de que infor-
maci on devolver cuando el c omputo para una determinada entrada de cinta
es terminante.
Para aquellas maquinas de Turing que no contienen estados nales, devolve-
mos c omo queda la cinta al nalizar el computo, pues asumimos que esta
informaci on es importante, ya que la simulaci on no se detiene en un estado
nal, tambien llamado de aceptacion. El usuario debe comprobar si su con-
tenido es el esperado o no.
En cambio, si existen estados nales, consideramos que el estado en el que
quede la cinta no es relevante, y unicamente mostramos un mensaje al usuario
3.6. M
AQUINAS DE TURING 47
inform andole de que su cinta de entrada se ha procesado con exito si ha -
nalizado la simulaci on en un estado nal, o que ha fallado su reconocimiento
en caso contrario.
3.6.2. Algoritmo de reconocimiento
Una vez comprendida la formalizaci on de Turing, la hemos usado de una
manera muy intuitiva, para comprobar si la palabra que introducimos puede
ser reconocida por el lenguaje que denota la m aquina de Turing dise nada.
Una vez hemos dise nado una m aquina de Turing en el area especca para
ello en TALFi, disponemos de un boton con el cual abrir el archivo de texto
que contiene la palabra a tratar.
Una vez pulsado el bot on, se abrira el usual dialogo de apertura de
archivos. Seleccionado el archivo, el algoritmo pasa a realizar los siguientes
pasos:
1. Busca el primer estado para iniciar el procesamiento de la cinta (archivo
de texto).
2. Coloca la cabeza lectora al principio de la cinta (primer smbolo que
no es un blanco).
3. Analiza que transicion entre las existentes en la m aquina, contienen el
estado inicial y el caracter actual de la cabeza lectora.
4. Si existe la transici on, actualiza el valor de la celda de la cinta y se
desplaza a la celda que indique la propia transici on (N = no se desplaza,
I = izquierda, D = derecha). Si no existe, la palabra no ser a reconocida,
mostrando en el archivo de texto dicha situacion.
5. Vuelve al paso 3 para ver si la nueva transicion existe (pero ahora con el
estado y el smbolo de cinta actualizados) y en caso armativo, tratarla
de la misma manera, modicando la cinta.
6. Si al nal de todo el computo, la palabra resulta reconocida, la salida
que se ofrecer a en la cinta (archivo de texto) de la maquina de Turing
(por denicion) ser a la celda que se encuentra inmediatamente a la
derecha de la ultima posici on de la cinta de entrada que no es un blanco
de cinta.
48 CAP
ITULO 3. INFORMACI
ON
3.6.3. Ampliaciones y problemas
No hemos mencionado en la anterior descripcion del algoritmo, el caso en
el que una maquina de Turing, no acabe nunca su computo, es decir, cicle
o no sea terminante. Este problema no es decidible, ni siquiera existe una
m aquina de Turing para esto. Por ello recurrimos a una idea que si bien
no sera capaz de solucionar todos los casos, si un alto porcentaje de ellos.
Supongamos una maquina de Turing y una palabra x dada, dicha m aquina
puede:
Aceptar a x, si existe una conguraci on de parada y aceptadora.
Rechazar a x, si existe una conguraci on de parada y no aceptadora.
Ciclar, si no existe una conguracion de parada.
Dado que en un principio este problema no fue contemplado, era necesario
a nadir alg un tipo de complemento para que se detectase el caso de ciclo
en el computo de una m aquina de Turing. Dicho complemento, es una cota
que utilizan varios algoritmos conocidos. Dicha cota esta relacionada con la
longitud de la cinta y el n umero de transiciones de la maquina de Turing y su
tratamiento consiste en consultar el n umero de transiciones visitadas hasta
el momento y compararlas con dicha cota.
3.7. Cambios destacables en TALFi 2.0
3.7.1. Interfaz graca
Ante todo hemos de decir que nuestro objetivo ha sido incluir las nuevas
funciones de TALFi alterando lo mnimo posible el dise no que hasta el mo-
mento tena la aplicaci on.
Notaci on graca para automatas de pila
Un diagrama que generaliza el diagrama de transici on de un automata
nito aclara determinados aspectos del comportamiento de un automata de
pila. Por lo tanto, introduciremos y usaremos a partir de ahora un diagrama
de transicion para automatas de pila en el que:
1. Los nodos corresponden a los estados del automata de pila.
2. Una triangulo blanco indica el estado inicial, y los estados con un doble
crculo son de aceptaci on, igual que en la primera versi on de TALFi
cuando se dibujan los automatas nitos.
3.7. CAMBIOS DESTACABLES EN TALFI 2.0 49
3. Los arcos corresponden a las transiciones del aut omata de pila en el
sentido siguiente:
un arco con la etiqueta a/X/ desde el estado q al estado p signica
que (q,a,X) contiene el par (p,), quiza entre otros pares. Es decir, la
etiqueta del arco dice que entrada se usa y tambien indica los elementos
de lo alto de la pila, antiguo y nuevos. La unica cosa que el diagrama
no nos dice es que smbolo de la pila es el smbolo inicial. Por convenio,
ser a Z
0
, a menos que se tenga que transformar un automata de pila
que acepte un lenguaje por estado nal en otro que acepte el mismo
lenguaje por pila vaca, siendo en ese caso X
0
.
Notaci on graca para maquinas de Turing
Las transiciones de una m aquina de Turing pueden representarse visual-
mente de una forma muy parecida como se hace para los aut omatas de pila.
Un diagrama de transicion est a formado por un conjunto de nodos que corres-
ponden a los estados de la maquina de Turing. En un arco que vaya del estado
q al estado p, aparecer an una o varias etiquetas de la forma X/Y/S, d onde
X e Y son smbolos de cinta, y S indica un sentido, que puede der I, D o N.
Es decir, si (q,X) = (p,Y,S), en el arco que va de q a p se encontrara la eti-
queta X/Y/S. Como en el resto de diagramas de transicion, el estado inicial
se indica mediante la colocacion de un triangulo blanco a su izquierda, y los
estados se aceptaci on se indican mediante crculos dobles.
Por tanto, la unica informaci on sobre la m aquina de Turing que habra
que a nadir al diagrama es el smbolo que se utiliza para denotar el espacio
50 CAP
ITULO 3. INFORMACI
ON
en blanco. Dicho smbolo es #.
Crear un nuevo automata de pila / maquina de Turing
Para no saturar m as de botones, no hemos incluido uno que fuera un acce-
so directo para crear un nuevo ejemplo de maquina de Turing o aut omata de
pila. Si el usuario desea un nuevo ejemplo de estas caractersticas, tendr a que
dirigirse y hacer click en el apartado Archivo del men u superior:
Botones
La segunda novedad son los tres botones para la generacion aleatoria de
palabras para automatas de pila, cargar la cinta inicial de la m aquina de
Turing y la generacion del c odigo en L
A
T
E
X del aut omata que visualizamos
en el canvas.
Al comienzo de la aplicacion aparecen los tres desactivados, y seg un las areas
que trabajemos se iran activando si corresponde.
Lo mismo ocurre con la secci on algoritmos, las opciones est an unicamente
disponibles cuando sea l ogico el poder aplicarlas.
Aspecto de la aplicaci on al arrancarla:
52 CAP
ITULO 3. INFORMACI
ON
Men u Algoritmos al iniciar la aplicaci on:
Muestra de los botones activos en un ejemplo de m aquina de Turing:
Cuadro de di alogo que aparece al modicar una arista de un aut omata
de pila:
3.7.2. Ejercicios
Ahora tambien es posible crear ejercicios de aut omatas de pila y m aquinas
de Turing. Hemos incluido una peque na colecci on, pero el administrador
puede ampliarla creando sus propios ejercicios y a nadiendolos a la base de
datos de los mismos. A continuaci on detallaremos como crearlos, que infor-
maci on interna generan, y la forma de corregirlos que hemos implementado.
Se siguen creando de la misma manera que los anteriores ejercicios,
seleccion andolos de la lista de todos los posibles:
54 CAP
ITULO 3. INFORMACI
ON
Hasta el momento, el administrador solamente tena que dibujar el aut o-
mata o escribir la expresion regular que fuera soluci on, y el enunciado del
ejercicio. Para los nuevos ejercicios necesitamos m as informacion para poder
asegurar que la solucion que proporcione el usuario es la suministrada por
el administrador de la aplicacion. A continuaci on describimos los cambios
introducidos.
Interfaz graca para ejercicios de automatas de pila
Un lenguaje independiente de contexto puede generarse con distintas
gram aticas independientes de contexto, y por tanto con diferentes automatas
de pila. Por este motivo, necesitamos tener una lista de palabras que ten-
dremos que comprobar que son aceptadas el automata de pila dibujado co-
mo soluci on, resultado que obtenemos facilmente mediante el resultado que
obtenemos al aplicar el algoritmo CYK. Para anar m as a un el resultado,
pedimos otra lista de palabras que no deben ser reconocidas por el a utoma-
ta. Ninguna de las dos tiene lmite, pero si es necesario que alguna de ellas
contenga alguna cadena, pues con ambas vacas no podramos comparar la
soluci on del ejercicio con la que nos proporcione el usuario.
Al aut omata que pinte el usuario se le aplicar a el algoritmo de CYK, y si
coinciden todos los resultados, se considerara el ejercicio como apto, en otro
caso no se dar a como no valido.
El usuario que vaya a enviar la correci on del ejercicio en ning un momen-
to tendra conocimiento de cuales son las palabras que pertenecen a estas
listas.
Simulaci on de la correcion del ejercicio 4 de la coleccion de ejer-
cicios de aut omatas de pila de TALFi
Interfaz graca para ejercicios de maquinas de Turing
La correci on de ejercicios dependera de si la soluci on tiene estados nales
o no, puesto que en el primer caso, en los computos que nalizan no nos
importa el contenido de la cinta, pero sin embargo en el segundo s. Como
no sabemos si se va a crear un ejercicio cuya solucion tenga estados nales,
incluimos cinco casillas, en las cu ales se podr an escribir las cintas de entrada
que seran aceptadas, las salidas de cinta generadas por las cintas de entrada
aceptadas, las cintas de entrada que no ser an aceptadas, las salidas de cinta
generadas por las cintas de entrada que no se aceptaran, y las cintas de
entrada que provocaran ciclos en la simulaci on. No es necesario rellenar toda
esta informacion, pero si alguno, pues sino es imposible corregir el ejercicio.
56 CAP
ITULO 3. INFORMACI
ON
Si la solucion del ejercicio no contiene estados nales, comprobaremos que
las cintas de entrada con sus cintas de salidas asociadas contienen el mismo
n umero de elementos. Si son distintos avisamos al administrador para que
las revise.
No se generaran las cintas de salida obtenidas en el caso de que pare la
simulaci on, ya que solo necesitamos saber si se ha obtenido la misma salida
en la soluci on que en la simulaci on de la respuesta dibujada por el usuario.
Captulo 4
Entorno L
A
T
E
X
4.1. L
A
T
E
X
La opcion de que TALFi imprimiese cualquier aut omata que se dibujase
en L
A
T
E
X o mostrase los pasos de una simplicaci on de gram aticas en dicho
formato, no fue uno de los riquisitos de la especicaci on en un principio.
Pero la opci on concedida gracias a una beca del PIE (Programa de Ini-
ciaci on a la Empresa), nos dio la oportunidad de a nadir esta funcionalidad
a la aplicaci on y poder trabajar con este formato de texto tan usado entre
profesionales.
4.1.1. Introducc on a L
A
T
E
X
L
A
T
E
X es un sistema de composicion de textos, orientado especialmente a
la creacion de libros, documentos cientcos y tecnicos que contengan f ormu-
las matematicas.
L
A
T
E
X esta formado por un gran conjunto de macros de T
E
X, escrito por
Leslie Lamport en 1984, con la intenci on de facilitar el uso del lenguaje de
composici on tipograca T
E
X, creado por Donald Knuth. Es muy utilizado
para la composicion de artculos academicos, tesis y libros tecnicos, dado que
la calidad tipogr aca de los documentos realizados con L
A
T
E
X es comparable
a la de una editorial cientca de primera lnea.
L
A
T
E
X es software libre bajo licencia LPPL.
4.1.2. Descripcion:
L
A
T
E
X es un sistema de composici on de textos que esta formado mayori-
tariamente por ordenes (macros) construidas a partir de comandos de T
E
X
57
58 CAP
ITULO 4. ENTORNO L
A
T
E
X
un lenguaje de bajo nivel, en el sentido de que sus acciones ultimas son
muy elementales pero con la ventaja a nadida, en palabras de Lamport, de
poder aumentar las capacidades de L
A
T
E
X utilizando comandos propios del
T
E
X descritos en The TeXbook. Esto es lo que convierte a L
A
T
E
X en una
herramienta pr actica y util pues, a su facilidad de uso, se une toda la potencia
de T
E
X. Estas caractersticas hicieron que L
A
T
E
X se extendiese rapidamente
entre un amplio sector cientco y tecnico, hasta el punto de convertirse en
uso obligado en comunicaciones y congresos, y requerido por determinadas
revistas a la hora de entregar artculos academicos.
Su codigo abierto permiti o que muchos usuarios realizasen nuevas utili-
dades que extendiesen sus capacidades con objetivos muy variados, a veces
ajenos a la intenci on con la que fue creado: aparecieron diferentes dialec-
tos de L
A
T
E
X que, a veces, eran incompatibles entre s. Para atajar este pro-
blema, en 1989 Lamport y otros desarrolladores iniciaron el llamado Proyec-
to LaTeX3. En oto no de 1993 se anunci o una reestandarizaci on completa
de L
A
T
E
X, mediante una nueva versi on que inclua la mayor parte de es-
tas extensiones adicionales (como la opci on para escribir transparencias o la
simbologa de la American Mathematical Society) con el objetivo de dar uni-
formidad al conjunto y evitar la fragmentaci on entre versiones incompatibles
de L
A
T
E
X 2.09. Esta tarea la realizaron Frank Mittlebach, Johannes Braams,
Chris Rowley y Sebastian Rahtz junto al propio Leslie Lamport. Hasta al-
canzar el objetivo nal del Proyecto 3, a las distintas versiones se las viene
denominando L
A
T
E
X2
(o sea, version 2 y un poco m as...). Actualmente

cada a no se ofrece una nueva version, aunque las diferencias entre una y otra
suelen ser muy peque nas y siempre bien documentadas.
Con todo, adem as de todas las nuevas extensiones, la caracterstica m as
relevante de este esfuerzo de reestandarizaci on fue la arquitectura modular: se
estableci o un n ucleo central (el compilador) que mantiene las funcionalidades
de la version anterior pero permite incrementar su potencia y versatilidad
por medio de diferentes paquetes que solo se cargan si son necesarios. De
ese modo, L
A
T
E
X dispone ahora de innumerables paquetes para todo tipo
de objetivos, muchos dentro de la distribuci on ocial, y otros realizados por
terceros, en algunos casos para usos especializados.
4.2. Uso
L
A
T
E
X presupone una losofa de trabajo diferente a la de los procesadores
de texto habituales (conocidos como WYSIWYG, es decir, lo que ves es lo
que obtienes) y se basa en comandos. Tradicionalmente, este aspecto se ha
considerado una desventaja (probablemente la unica). Sin embargo, L
A
T
E
X, a
4.2. USO 59
diferencia de los procesadores de texto de tipo WYSIWYG, permite a quien
escribe un documento centrarse exclusivamente en el contenido, sin tener que
preocuparse de los detalles del formato. Ademas de sus capacidades gr acas
para representar ecuaciones, formulas complicadas, notaci on cientca e in-
cluso musical, permite estructurar f acilmente el documento (con captulos,
secciones, notas, bibliografa, ndices analticos, etc.), lo cual brinda comodi-
dad y lo hace util para artculos academicos y libros tecnicos.
Con L
A
T
E
X, la elaboracion del documento requiere normalmente de dos
etapas: en la primera hay que crear mediante cualquier editor de texto llano
un chero fuente que, con las ordenes y comandos adecuados, contenga el
texto que queramos imprimir. La segunda consiste en procesar este chero;
el procesador de textos interpreta las ordenes escritas en el y compila el do-
cumento, dej andolo preparado para que pueda ser enviado a la salida corres-
pondiente, ya sea la pantalla o la impresora. Ahora bien, si se quiere a nadir o
cambiar algo en el documento, se debera hacer los cambios en el chero fuente
y procesarlo de nuevo. Esta idea, que puede parecer poco pr actica a priori,
es conocida a los que est an familiarizados con el proceso de compilaci on que
se realiza con los lenguajes de programaci on de alto nivel (C, C++, etc.), ya
que es completamente an alogo.
El modo en que L
A
T
E
X interpreta la forma que debe tener el documento
es mediante etiquetas. Por ejemplo, documentclass{article} le dice a L
A
T
E
X
que el documento que va a procesar es un artculo. Puede resultar extra no
que hoy en da se siga usando algo que no es WYSIWYG, pero las car-
actersticas de L
A
T
E
X siguen siendo muchas y muy variadas. Tambien hay
varias herramientas (aplicaciones) que ayudan a una persona a escribir estos
documentos de una manera m as visual (LyX, TeXmacs y otros). A estas he-
rramientas se les llama WYSIWYM (lo que ves es lo que quieres decir).
Una de las ventajas de L
A
T
E
X es que la salida que ofrece es siempre la
misma, con independencia del dispositivo (impresora, pantalla, etc.) o el sis-
tema operativo (MS Windows, MacOS, Unix, GNU/Linux, etc.) y puede ser
exportado a partir de una misma fuente a numerosos formatos tales como
Postscript, PDF, SGML, HTML, RTF, etc. Existen distribuciones e IDEs
de LaTeX para todos los sistemas operativos mas extendidos, que incluyen
todo lo necesario para trabajar. Hay, por ejemplo, programas para Windows
como TeXnicCenter, MikTeX o WinEdt, para Linux como Kile, o para Mac-
OS como TeXShop, todos liberados bajo la Licencia GPL. Existe adem as un
editor multiplataforma (para MacOS, Windows y Unix) llamado Texmaker,
que tambien tiene licencia GPL.
60 CAP
ITULO 4. ENTORNO L
A
T
E
X
4.2.1. Uso de L
A
T
E
Xen la herramienta TALFi
Aunque L
A
T
E
Xes primordialmente un sistema de composicion de textos
para la creacion de documentos que contengan f ormulas matem aticas, en
TALFi lo usaremos para poder colocar en nuestros textos automatas o sim-
plicaciones paso a paso de gramaticas.
Esto es posible debido a una gran cantidad y diversidad de bibliote-
cas/paquetes que podemos a nadir a nuestro editor de L
A
T
E
X. Gracias a esta
amplitud de posibilidades para crear gr acos complejos en L
A
T
E
X, el trabajo
inicial de poder imprimir los aut omatas o las simplicaciones acabo dando
como resultado 3 posibles representaciones en L
A
T
E
X. De esta manera y de-
bido a las diferencias entre las representaciones, el usuario podr a elegir entre
un dise no sobrio y con formas claras, un dise no colorido o un dise no en forma
matricial para poder modicarlo de manera m as intuitiva.
Sin embargo para la representaci on de los pasos en la simplicaci on de
gram aticas, s olo disponemos de un dise no, puesto que la representaci on se
hace mediante tablas y texto plano, siendo innecesaria la inclusi on de colores,
formas, etc.
4.3. LatexCodeConverter
Esta clase, es la encargada de traducir cualquier aut omata de TALFi en
un archivo T
E
X totalmente listo para ser compilado en cualquier entorno para
L
A
T
E
X.
Algoritmo conversor:
La implementaci on del algoritmo consiste b asicamente en traducir los
distintos campos de los que consta un automata en comandos L
A
T
E
X:
1. Para cada estado del aut omata se crea un crculo en el que den-
tro se incluye su etiqueta. Se detectan el estado inicial y los de
aceptaci on, para los que se usan otra representacion, ademas de
su crculo.
2. Se toma cada coordenada de cada nodo del aut omata TALFi para
colocarlo de la misma manera en el archivo que generemos con
L
A
T
E
X.
4.3. LATEXCODECONVERTER 61
3. Generamos las aristas viendo desde que estado parten y a cual se
dirigen.
4. Cerramos el archivo.
Representaciones:
1. Mediante biblioteca xy:
Esta es la representaci on mas able y visualmente mas clara,
puesto que siempre que se pueda dibujar un aut omata en TALFi,
su representaci on en L
A
T
E
Xser a pr acticamente identica.
62 CAP
ITULO 4. ENTORNO L
A
T
E
X
2. Mediante biblioteca TikZ:
Esta biblioteca es visualmente muy atractiva, pero tiene el in-
coveniente de que el modo en el que los estados se colocan en el
lienzo, se realiza especicando donde se encuentran cada uno de
ellos, en relacion a un estado dado. Como vemos en el c odigo,
partimos del estado A (q
a
en el dibujo), para luego indicar que
el estado B se encuentra arriba y a la derecha del estado A. Lo
mismo ocurre con el estado C, que se indica que est a abajo y a la
derecha del estado B,etc.
Aunque visualmente gane muchos enteros este tipo de representaci on,
debido a que el algoritmo construye el dibujo de manera de au-
tom atica, puede llevar a muchos problemas de superposicion de
estados cuando los aut omatas contienen un n umero de estados
elevado (inlcuso porda no poder visualizarse).
Conllevara una trabajo dicultoso de grafos para llevar a cabo
una representacion de aut omatas totalmente libre de errores para
esta representaci on. No obstante, si se quieren incluir automatas
en un texto L
A
T
E
X de manera manual, este es el mejor metodo
posible.
Lo comprobamos en un ejemplo:
64 CAP
ITULO 4. ENTORNO L
A
T
E
X
3. Mediante biblioteca Psmatrix:
En esta implementaci on, no cabe posibilidad de solapamiento de
estados, puesto que cada uno ocupara una celda de una matriz
virtual que se crea en el lienzo.
Sin embargo, al igual que ocurra en el caso anterior, ante automatas
con gran cantidad de estados, nos vamos a encontrar con un pro-
blema.
En este caso el problema, sera visual. Puesto que al haber tal can-
tidad de estados y debido a su disposicion matricial, las numerosas
aristas, pasaran por el centro de la matriz con toda seguridad, no
permitiendo observar bien las etiquetas de las transiciones e inclu-
so no pudiendo ver desde donde o hacia donde se dirigen.
66 CAP
ITULO 4. ENTORNO L
A
T
E
X
4.4. TraductorHTML
En TALFi 1.0 esta clase se encargaba de mostrar un archivo HTML en
un navegador web, con los pasos de la minimizaci on de aut omatas nitos.
Ahora se ha ampliado su funcionalidad para que muestre tambien la simpli-
caci on de gramaticas y la anteriormente mencionada minimizacion, en L
A
T
E
X.
Para ello usamos los comandos L
A
T
E
X tabular y hline para dar un formato
parecido a las tablas que se generebana en html. De esta manera podemos
crear lneas verticales y horizontales para dar aspecto de tabla en L
A
T
E
X.
El resto es introducir texto plano y los atributos de las distintas gram aticas
que se van simplicando.
4.5. ENTORNOS L
A
T
E
X UTILIZADOS 67
4.5. Entornos L
A
T
E
X utilizados
Miktex:
MiKTeX es una distribuci on T
E
X/L
A
T
E
X para Microsoft Windows que
fue desarrollada por Christian Schenk. Las caractersticas mas aprecia-
bles de MiKTeX son su habilidad de actualizarse por s mismo descar-
gando nuevas versiones de componentes y paquetes instalados previa-
mente, y su f acil proceso de instalacion.
La versi on actual de MiKTeX es 2.8 y est a disponible en su pagina o-
cial. Ademas, tiene caractersticas que incluyen MetaPost y pdfTeX y
compatibilidad con Windows 7. A partir de la version 2.7 se incluyo so-
porte integrado para XeTeX.
68 CAP
ITULO 4. ENTORNO L
A
T
E
X
Caractersticas:
Es libre y f acil de instalar.
Incluye m as de 800 paquetes con fonts, macros, etc.
Tiene un visor propio de archivos dvi denominado Yap.
Su codigo es abierto.
Posee compiladores T
E
X y L
A
T
E
X, convertidores para generar archivos
postscripts (.ps), pdf , html , etc.; y herramientas para generar
bibliografas e ndices.
Posee tres formas de instalaci on: peque na, mediana y completa.
WinEdt:
WinEdt es un editor de textos de gran alcance y versatilidad para Win-
dows, con una fuerte predisposici on hacia la creacion de documentos
L
A
T
E
X. La p agina de descargas del sitio web tiene mas informaci on so-
bre WinEdt, T
E
X, y enlaces a otros programas necesarios para hacer
operativo WinEdt en la plataforma Windows.
Captulo 5
Palabras clave
Aut omata, Turing, pila, Chomsky, Greibach, cinta, simplicacion, L
A
T
E
X,
pila vaca, determinista.
69
Captulo 6
Anexos
6.1. Ampliaci on del Manual de Usuario
Antes de que cualquier persona, administrador o no, quiera usar TALFi
2.0, debe conocer dos detalles para poder usar la aplicacion correctamente:
Si quiere incluir en las transiciones, tendra que hacerlo de forma
distinta que en TALFi 1.0, con el caracter \.
Por defecto el smbolo de fondo de pila es Z.
Para especicar un blanco en maquinas de Turing, tendr a que escribir
#.
Las direcciones posibles de movimiento en maquinas de Turing son I,
D, N para espa nol, y L,R,N para ingles. Ambas siempre en may usculas.
Necesariamente el contenido de la cinta para simular una maquina de
Turing debe cargarse en un archivo con extension txt.
Los enunciados de los ejercicios no pueden contener acentos ni el car acter
n.
Para especicar una cinta de blancos en los ejercicios de maquinas de
Turing, tendra que escribir #.
Al igual que en la primera versi on de TALFi, cuando se pide introducir los
smbolos, ya sean de cinta o de alfabeto, en ning un caso deben contener
espacios y tienen que ir separados por comas.
71
72 CAP
ITULO 6. ANEXOS
6.2. Cambios en la implementacion
A continuacion enumeraremos brevemente las nuevas clases y los nuevos
paquetes creados en este proyecto.
Ampliaci on de paquetes
Modelo.algoritmos:
AceptaTuring:
Contiene el algoritmo que simulara la ejecucion de una maquina
de Turing. Recibe el objeto creado para maquinas de Turing y la
ruta del archivo que contiene la cinta. Aqu se abre, si ocurriese
alg un problema no se realiza la simulaci on.
AutomataP to GramaticaIC:
Dado un aut omata de pila aplicamos el algoritmo que nos genera
su gramatica asociada.
GIC to FNC:
Recibe la gramatica que ha generado AutomataP to GramaticaIC,
y la transforma en Forma Normal de Greibach con el algoritmo
que utiliza las tablas de reemplazo.
GIC to Chomsky:
Al igual que GIC to FNC, genera la correspondiente Forma Nor-
mal de Chomsky a partir de la gram atica obtenida en Automa-
taP to GramaticaIC.
C Y K:
Implementa el algoritmo CYK y guarda la lista de palabras que
van a ejecutarse sobre el, al igual que la salida que generan, y
sobre que gram atica independiente de contexto lo hacen.
TuringResultado:
Contiene la maquina de Turing a corregir junto con la informacion
necesaria para ello y la lista de resultados que se obtienen.
Modelo.automatas:
Alfabeto Pila:
Interface con las operaciones de alfabetos de pila.
AlfabetoPila imp:
Implementa Alfabeto Pila y es la clase que como su nombre indica
crea y contiene informacion del alfabeto de pila.
6.2. CAMBIOS EN LA IMPLEMENTACI
ON 73
AlfabetoCinta:
Crea el alfabeto de cinta de una m aquina de Turing.
AutomataPila:
Sirve para crear objetos que identiquen aut omatas de pila.
MaquinaTuring:
Sirve para crear objetos que identiquen m aquinas de Turing.
Vista.vistaGraca:
AristaGeneral:
Clase abstracta con todos los atributos y metodos comunes a todos
los tipos de aristas.
Arista:
Arista utilizada para todos los aut omatas nitos.
AristaAP:
Arista que se utiliza en aut omatas de pila.
AristaTuring:
Arista que se emplea en m aquinas de Turing.
Vista.vistaGraca.events:
OyenteItemPopupAristaAP:
Crea el cuadro de di alogo cuando se modica una arista de un
aut omata de pila.
OyenteItemPopupAristaTuring:
Crea el cuadro de di alogo cuando se modica una arista de una
m aquina de Turing.
OyenteModicaAristaAPActionListener:
Procesa los nuevos atributos que se han cambiado al modicar la
arista de un aut omata de pila si se pulsa aceptar con el raton.
OyenteModicaAristaTuringActionListener:
arista de una m aquina de Turing si se pulsa aceptar con el raton.
OyenteModicaAristaAPKeyAdapter:
arista de un aut omata de pila si se aceptan pulsando Intro.
OyenteModicaAristaTuringKeyAdapter:
arista de una m aquina de Turing si se aceptan pulsando Intro.
74 CAP
ITULO 6. ANEXOS
Creaci on de paquetes:
Modelo.gramatica:
Chomsky:
Crea objetos que representen una gram atica en Forma Normal de
Chomsky.
Gramatica:
Clase abstracta con los atributos y metodos comunes a todas las
gram aticas que generamos en esta aplicaci on.
GramaticaIC:
Clase que extiende a Gramatica, y cuyos objetos representan la
gram atica resultante antes de transformarla en ninguna Forma
Normal.
Greibach:
Crea objetos que representen una gram atica en Forma Normal de
Greibach.
Produccion:
Crea los objetos que procesaremos como producciones.
6.3. Estructura XML de los ejercicios de aut omatas
de pila
Incluimos la estructura interna de los ejercicios de aut omatas de pila,
donde se apreciar la similitud con los ejercicios de la primera version de
TALFi y las novedades incluidas en su ampliaci on.
<ejercicio>
<tipo>TransformacionAPs</tipo>
<enunciado>
Dibuje un automata que genere por estado de aceptacion el lenguaje
{ab^n | n>=0}.
</enunciado>
6.3. ESTRUCTURAXML DE LOS EJERCICIOS DE AUT
OMATAS DE PILA75
<output>
<authomata>
<type>
<item>AutomataPila</item>
</type>
<alphabet>
<item>a</item>
<item>b</item>
</alphabet>
<alphabetP>
<item>Z</item>
</alphabetP>
<states>
<state>s2</state>
<state>s1</state>
</states>
<init>
<state>s1</state>
</init>
<finals>
76 CAP
ITULO 6. ANEXOS
<state>s1</state>
</finals>
<arrows>
<arrow>
<state>s1</state>
<state>s2</state>
<item>a</item>
<cima>Z</cima>
<trans>Z</trans>
</arrow>
<arrow>
<state>s2</state>
<state>s1</state>
<item>b</item>
<cima>Z</cima>
<trans>Z</trans>
</arrow>
</arrows>
<coordenadas>
<estadoCoord>
6.3. ESTRUCTURAXML DE LOS EJERCICIOS DE AUT
OMATAS DE PILA77
<nombre>s2</nombre>
<x>505</x>
<y>104</y>
</estadoCoord>
<estadoCoord>
<nombre>s1</nombre>
<x>304</x>
<y>139</y>
</estadoCoord>
</coordenadas>
</authomata>
<listaPalabras>
<item>ab</item>
<item>abab</item>
</listaPalabras>
</output>
</ejercicio>
78 CAP
ITULO 6. ANEXOS
6.4. Estructura XML de los ejercicios de maquinas
de Turing
Adjuntamos un ejemplo sencillo para mostrar de que manera almace-
namos los datos para un ejercicio de este tipo.
<ejercicio>
<tipo>EjMT</tipo>
<enunciado>
Dibuje una maquina de Turing que realice la funcion n = n+2
</enunciado>
<output>
<authomata>
<type>
<item>MaquinaTuring</item>
</type>
<alphabet>
<item>1</item>
</alphabet>
<alphabetP>
<item>1</item>
<item>#</item>
6.4. ESTRUCTURAXML DE LOS EJERCICIOS DE M
AQUINAS DE TURING79
</alphabetP>
<states>
<state>s0</state>
<state>s1</state>
<state>s2</state>
</states>
<init>
<state>s0</state>
</init>
<finals>
</finals>
<arrows>
<arrow>
<state>s0</state>
<state>s0</state>
<item>1</item>
<scinta>1</scinta>
<direc>D</direc>
</arrow>
<arrow>
80 CAP
ITULO 6. ANEXOS
<state>s0</state>
<state>s1</state>
<item>#</item>
<scinta>1</scinta>
<direc>D</direc>
</arrow>
<arrow>
<state>s1</state>
<state>s2</state>
<item>#</item>
<scinta>1</scinta>
<direc>I</direc>
</arrow>
<arrow>
<state>s2</state>
<state>s2</state>
<item>1</item>
<scinta>1</scinta>
<direc>I</direc>
</arrow>
6.4. ESTRUCTURAXML DE LOS EJERCICIOS DE M
AQUINAS DE TURING81
</arrows>
<coordenadas>
<estadoCoord>
<nombre>s0</nombre>
<x>217</x>
<y>110</y>
</estadoCoord>
<estadoCoord>
<nombre>s1</nombre>
<x>401</x>
<y>51</y>
</estadoCoord>
<estadoCoord>
<nombre>s2</nombre>
<x>576</x>
<y>131</y>
</estadoCoord>
</coordenadas>
</authomata>
<listaPalabras>
82 CAP
ITULO 6. ANEXOS
<item>111</item>
</listaPalabras>
<listaCintaPalabras>
<item>11111</item>
</listaCintaPalabras>
<listaPalabrasNo>
<item>1121</item>
</listaPalabrasNo>
<listaCintaPalabrasNo>
<item>21</item>
</listaCintaPalabrasNo>
<listaPalabrasBucle>
</listaPalabrasBucle>
</output>
</ejercicio>
Bibliografa
[1] Hopcraft, Motwani, Uliman.
Introducci on a la teora de automatas. Lenguajes y computaci on
Addison Wesley 2002.
[2] J. G. Brookshear.
Teora de la Computaci on: Lenguajes Formales, Aut omatas y Com-
plejidad
Addison-Wesley Iberoamericana, 1993.
[3] J.C. Martin.
Introduction to Languages and the Theory of Computation
McGraw-Hill, 1997, (Segunda edicion).
[4] D.C. Kozen
Automata and Computability
Springer Verlag, 1997.
[5] H.R. Lewis, C.H. Papadimitriou
Elements of the Theory of Computation
Prentice Hall, 1988, (Segunda edici on).
[6] P. Isasi, P. Martnez, D. Borrajo
Lenguajes, Gram aticas y Aut omatas, un enfoque pr actico
Addison-Wesley, 1997.
[7] Dean Kelley.
Teora de Automatas y Lenguajes Formales
Prentice Hall, 1997.
[8] http://es.wikipedia.org
83

Talfi

Cargado por

Copyright:

Formatos disponibles

Talfi

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Talfi

Cargado por

Copyright:

Formatos disponibles

TALFi 2.

(o sea, version 2 y un poco m as...). Actualmente

También podría gustarte