Manual.dvi Manual
manual
User Manual:
Open the PDF directly: View PDF 
.
Page Count: 28
Documentaci´on y Gu´ıa de Usuario
de la Librer´ıa ocaml-talf
´
Indice General
1 Introducci´on 1
1.1 Descarga e instalaci´on de la librer´ıa . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Compilaci´on y uso de la librer´ıa . . . . . . . . . . . . . . . . . . . . . . . . 2
2 Conjuntos 3
2.1 Definici´on de conjunto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Operaciones b´asicas sobre conjuntos . . . . . . . . . . . . . . . . . . . . . . 3
3 S´ımbolos 5
3.1 S´ımbolos individuales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3.2 Cadenasdes´ımbolos .............................. 6
4 Expresiones regulares 7
4.1 Definici´on de expresi´on regular . . . . . . . . . . . . . . . . . . . . . . . . . 7
4.2 Construcci´on de expresiones regulares . . . . . . . . . . . . . . . . . . . . . 7
5 Aut´omatas finitos 9
5.1 Definici´on de aut´omata finito . . . . . . . . . . . . . . . . . . . . . . . . . 9
5.2 Construcci´on de aut´omatas finitos . . . . . . . . . . . . . . . . . . . . . . . 9
5.3 Aut´omatas finitos y expresiones regulares . . . . . . . . . . . . . . . . . . . 11
5.4 Funcionamiento de un aut´omata finito . . . . . . . . . . . . . . . . . . . . 11
5.5 Visualizaci´on de aut´omatas finitos . . . . . . . . . . . . . . . . . . . . . . . 12
6 Gram´aticas independientes del contexto 13
6.1 Definici´on de gram´atica independiente del contexto . . . . . . . . . . . . . 13
6.2 Construcci´on de gram´aticas independientes del contexto . . . . . . . . . . . 14
6.3 Gram´aticas regulares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
7 Aut´omatas de pila 17
7.1 Definici´on de aut´omata de pila . . . . . . . . . . . . . . . . . . . . . . . . . 17
7.2 Construcci´on de aut´omatas de pila . . . . . . . . . . . . . . . . . . . . . . 17
7.3 Funcionamiento de un aut´omata de pila . . . . . . . . . . . . . . . . . . . . 19
7.4 Visualizaci´on de aut´omatas de pila . . . . . . . . . . . . . . . . . . . . . . 19
8 M´aquinas de Turing 21
8.1 Definici´on de m´aquina de Turing . . . . . . . . . . . . . . . . . . . . . . . 21
8.2 Construcci´on de m´aquinas de Turing . . . . . . . . . . . . . . . . . . . . . 22
iii
iv ´
INDICE GENERAL
8.3 Funcionamiento de una m´aquina de Turing . . . . . . . . . . . . . . . . . . 24
8.4 Visualizaci´on de m´aquinas de Turing . . . . . . . . . . . . . . . . . . . . . 24
Cap´ıtulo 1
Introducci´on
ocaml-talf es una librer´ıa OCaml dise˜nada espec´ıficamente para las clases pr´acticas
sobre Teor´ıa de Aut´omatas y Lenguajes Formales de la asignatura Teor´ıa de la
Computaci´on que se imparte en la Facultad de Inform´atica de la Universidad de La Coru˜na.
El objetivo principal de la librer´ıa es el de reforzar la comprensi´on de los conceptos que
conforman la materia de la asignatura, para lo cual se proporcionan implementaciones lo
m´as acordes posible con las definiciones fomales que se presentan en las clases te´oricas.
La eficiencia de dichas implementaciones es tambi´en tenida en cuenta, pero constituye un
objetivo secundario.
Actualmente, el n´ucleo principal de la librer´ıa ocaml-talf est´a formado por la
definici´on de los tipos de datos de las estructuras algebraicas introducidas en la asignatura
(expresiones regulares, gram´aticas, aut´omatas finitos, aut´omatas de pila, m´aquinas de
Turing, etc.), y por una serie de funciones de transformaci´on que permiten construir
c´omodamente valores de esos tipos. No obstante, la librer´ıa est´a todav´ıa en fase de
desarrollo y se espera que crezca mediante la incorporaci´on de nuevas funcionalidades
y mejoras.
1.1 Descarga e instalaci´on de la librer´ıa
La librer´ıa se encuentra en el fichero ocaml-talf.tar.gz que reside en el Moodle de la
asignatura. Una vez descargardo, este fichero debe descomprimirse y expandirse mediante
el comando
tar -zxvf ocaml-talf.tar.gz
Este proceso genera los siguientes directorios:
•El directorio src que contiene el c´odigo fuente de la librer´ıa.
•El directorio doc que contiene el presente manual.
•El directorio data que contiene algunos ejemplos de las estructuras algebraicas que
maneja la librer´ıa.
1
2 Introducci´on
1.2 Compilaci´on y uso de la librer´ıa
Para compilar la librer´ıa es preciso entrar en el directorio src y ejecutar el comando
make all
La librer´ıa consta principalmente de cuatro m´odulos:
•El m´odulo Conj proporciona una implementaci´on para realizar operaciones b´asicas
sobre conjuntos.
•El m´odulo Auto proporciona los tipos correspondientes a las estructuras algebraicas
anteriormente mencionadas y las operaciones b´asicas que se pueden realizar sobre
ellos.
•El m´odulo Ergo proporciona funciones para crear c´omodamente valores de dichos
tipos desde cadenas de caracteres o ficheros, y viceversa.
•El m´odulo Graf proporciona funciones para visualizar las representaciones gr´aficas
de los valores de dichos tipos. Para ello es necesario tener instalado el programa dot
(un preprocesador para el dibujo de grafos dirigidos1).
La librer´ıa puede utilizarse para crear ejecutables, pero puede manejarse tambi´en
directamente desde el lazo interactivo de OCaml, para lo cual se recomienda ejecutar
las siguientes instrucciones:
$ ocaml
# #load "talf.cma";;
# open Conj;;
# open Auto;;
# open Ergo;;
# open Graf;;
1Disponible en www.graphviz.org
Cap´ıtulo 2
Conjuntos
El m´odulo Conj proporciona una implementaci´on basada en listas para realizar operaciones
b´asicas sobre conjuntos de elementos de cualquier tipo. Esta implementaci´on intenta
resaltar la diferencia existente entre un conjunto y una lista, la cual se basa en los dos
siguientes aspectos:
•Los conjuntos no tienen elementos repetidos, mientras que las listas s´ı pueden
tenerlos.
•El orden de los elementos en un conjunto no es relevante, mientras que en la lista s´ı
puede serlo.
Las siguientes secciones muestran la definici´on del tipo de dato para los conjuntos, as´ı
como las funciones de manejo m´as usuales.
2.1 Definici´on de conjunto
Para representar los conjuntos, el m´odulo Conj define el siguiente tipo de dato:
type ’a conjunto =
Conjunto of ’a list;;
Para representar el conjunto vac´ıo, el m´odulo Conj proporciona tambi´en el valor
conjunto_vacio : ’a Conj.conjunto.
2.2 Operaciones b´asicas sobre conjuntos
Las operaciones sobre conjuntos que implementa el m´odulo Conj son las que se citan a
continuaci´on:
•es_vacio : ’a Conj.conjunto -> bool
Comprueba si un conjunto es vac´ıo o no.
•pertenece : ’a -> ’a Conj.conjunto -> bool
pertenece x c comprueba si el elemento xpertenece o no al conjunto c.
3
4 Conjuntos
•agregar : ’a -> ’a Conj.conjunto -> ’a Conj.conjunto
agregar x c devuelve el conjunto resultante de a˜nadir el elemento xal conjunto c.
Si xya est´a en c, el resultado es el propio c.
•conjunto_of_list : ’a list -> ’a Conj.conjunto
A partir de una lista, esta funci´on crea un conjunto sin elementos repetidos. Esto,
unido al hecho de que el orden de los elementos dentro de un conjunto no es relevante,
puede hacer que la lista soporte del conjunto difiera de la lista original.
•suprimir : ’a -> ’a Conj.conjunto -> ’a Conj.conjunto
suprimir x c devuelve el conjunto resultante de eliminar el elemento xdel conjunto
c. Si xno est´a en c, el resultado es el propio c.
•cardinal : ’a Conj.conjunto -> int
Devuelve el n´umero de elementos de un conjunto.
•union : ’a Conj.conjunto -> ’a Conj.conjunto -> ’a Conj.conjunto
interseccion : ’a Conj.conjunto -> ’a Conj.conjunto -> ’a Conj.conjunto
diferencia : ’a Conj.conjunto -> ’a Conj.conjunto -> ’a Conj.conjunto
Uni´on, intersecci´on y diferencia de conjuntos.
•incluido : ’a Conj.conjunto -> ’a Conj.conjunto -> bool
incluido c1 c2 comprueba si el conjunto c1 es o no un subconjunto del conjunto
c2.
•igual : ’a Conj.conjunto -> ’a Conj.conjunto -> bool
Comprueba si dos conjuntos son iguales o no.
•list_of_conjunto : ’a Conj.conjunto -> ’a list
Dado un conjunto, esta funci´on devuelve una lista con todos sus elementos. Es ´util
cuando se necesita procesar todos y cada uno de los elementos del conjunto.
•cartesiano : ’a Conj.conjunto -> ’b Conj.conjunto -> (’a * ’b)
Conj.conjunto
Calcula el producto cartesiano de dos conjuntos.
Para facilitar las tareas de programaci´on, no se ha ocultado el constructor del tipo. As´ı
pues, el usuario dispone de mecanismos para crear conjuntos con elementos repetidos. No
obstante, si los conjuntos se construyen ´unica y exclusivamente a trav´es de las funciones
descritas anteriormente, est´a garantizado que eso no ocurrir´a.
Cap´ıtulo 3
S´ımbolos
Como ya se ha mencionado, el m´odulo Auto de la librer´ıa proporciona los tipos
correspondientes a las estructuras algebraicas involucradas en la teor´ıa de aut´omatas y
lenguajes formales. La estructura m´as b´asica viene dada por la definici´on de los s´ımbolos
que permiten denotar los lenguajes.
3.1 S´ımbolos individuales
En general, existen dos tipos de s´ımbolos:
•Los s´ımbolos terminales son aqu´ellos que forman parte de las cadenas de los
lenguajes.
•Los s´ımbolos no terminales son aqu´ellos que no forman parte de las cadenas de los
lenguajes, sino que sirven para ayudar a definirlos.
Para ello, el m´odulo Auto define el siguiente tipo de dato:
type simbolo =
Terminal of string
| No_terminal of string;;
Como se puede observar, los nombres de los s´ımbolos podr´an constar de m´as de un caracter.
El juego de caracteres v´alido para los s´ımbolos est´a formado por todos los caracteres
imprimibles, excepto por #(que se reserva para lo introducci´on de comentarios). No
obstante, dicho caracter puede tambi´en incluirse en el nombre de un s´ımbolo a trav´es de
la secuencia \#.
El s´ımbolo especial ´epsilon lo representaremos mediante Terminal "". El s´ımbolo
especial de inicio de pila zeta (necesario para la implementaci´on de los aut´omatas de pila)
y el s´ımbolo especial blanco (necesario para la implementaci´on de las m´aquinas de Turing)
los representaremos mediante No_terminal "".
5
6 S´ımbolos
3.2 Cadenas de s´ımbolos
Las cadenas de s´ımbolos se pueden especificar en modo texto mediante cadenas de
caracteres donde los nombres de los s´ımbolos aparecen separados por espacios. Por
ejemplo, la cadena de caracteres
"a B ce"
es una posible representaci´on de la lista de s´ımbolos
[Terminal "a"; Terminal "B"; Terminal "ce"]
Adem´as, existe la palabra reservada epsilon, aunque cualquier aparici´on de la misma ser´a
siempre ignorada. As´ı pues, la cadena vac´ıa se puede representar mediante "epsilon" o
mediante "". Ambas representaciones producen la lista de s´ımbolos []. Por ´ultimo, existe
tambi´en la palabra reservada blanco, la cual ser´a siempre convertida en No_terminal "".
El m´odulo Ergo incluye una serie de funciones para manejar la sintaxis anteriormente
descrita. Dichas funciones son las que se citan a continuaci´on:
•cadena_of_string : string -> Auto.simbolo list
Funci´on que dada una cadena de caracteres devuelve la lista de s´ımbolos
correspondiente.
•cadena_of_file : string -> Auto.simbolo list
Funci´on que dado un nombre de fichero que contenga una cadena de caracteres
devuelve la lista de s´ımbolos correspondiente. Cuando la especificaci´on de una
cadena de s´ımbolos se escribe en un fichero, todo texto que aparezca desde un s´ımbolo
#hasta un final de l´ınea es considerado como un comentario.
•string_of_cadena : Auto.simbolo list -> string
Funci´on que dada una lista de s´ımbolos devuelve la cadena de caracteres
correspondiente.
•file_of_cadena : Auto.simbolo list -> string -> unit
Funci´on que dada una lista de s´ımbolos y un nombre de fichero escribe en ese fichero
la cadena de caracteres correspondiente.
Una vez m´as, para facilitar las tareas de programaci´on, no se han ocultado los constructores
del tipo. As´ı pues, el usuario dispone de mecanismos para crear cadenas de s´ımbolos
inconsistentes, como por ejemplo [Terminal ""]. No obstante, si las cadenas de s´ımbolos
se construyen mediante las funciones descritas anteriormente, est´a garantizado que eso no
ocurrir´a.
Cap´ıtulo 4
Expresiones regulares
La siguiente estructura algebraica que implementa el m´odulo Auto es la correspondiente a
las expresiones regulares, las cuales constituyen el mecanismo m´as c´omodo para denotar
los lenguajes regulares.
4.1 Definici´on de expresi´on regular
Las expresiones regulares se definen recursivamente como sigue:
•En primer lugar, ∅(el conjunto vac´ıo), ǫ(´epsilon) y cualquier s´ımbolo terminal son
expresiones regulares b´asicas.
•Y adem´as, si rysson expresiones regulares, entonces tambi´en lo son: r∪s(uni´on),
r·s(concatenaci´on), y r∗(repetici´on).
Para ello, el m´odulo Auto define el siguiente tipo de dato:
type er =
Vacio
| Constante of simbolo
| Union of (er * er)
| Concatenacion of (er * er)
| Repeticion of er;;
As´ı pues, en este tipo de dato, la expresi´on regular ´epsilon debe representarse como
Constante (Terminal "").
4.2 Construcci´on de expresiones regulares
Las expresiones regulares se pueden construir a partir de una especificaci´on en modo
texto, cuya sintaxis es como sigue. Los operadores permitidos, en orden de mayor a menor
prioridad son: *(para la repetici´on), .(para la concatenaci´on) y |(para la uni´on). Por
supuesto, se pueden utilizar par´entesis cuando sea necesario variar este orden. Por ejemplo,
la cadena de caracteres
7
8 Expresiones regulares
"a.be|ce*"
es una posible representaci´on de la expresi´on regular
Union (Concatenacion (Constante (Terminal "a"),
Constante (Terminal "be")),
Repeticion (Constante (Terminal "ce")))
mientras que
"a.(be|ce)*"
es una posible representaci´on de
Concatenacion (Constante (Terminal "a"),
Repeticion (Union (Constante (Terminal "be"),
Constante (Terminal "ce"))))
Como se puede observar, los nombres de los s´ımbolos pueden constar de m´as de un
caracter. El juego de caracteres v´alido para los s´ımbolos est´a formado por todos los
caracteres imprimibles, excepto por #(reservado para comentarios), y por ( ) | . *
(reservados para las operaciones anteriormente descritas). No obstante, dichos caracteres
pueden tambi´en incluirse en el nombre de un s´ımbolo si aparecen precedidos de \. Existen
tambi´en las palabras reservadas vacio yepsilon para denotar las expresiones regulares
Vacio yConstante (Terminal ""), respectivamente.
El m´odulo Ergo incluye una serie de funciones para manejar la sintaxis anteriormente
descrita. Dichas funciones son las que se citan a continuaci´on:
•er_of_string : string -> Auto.er
Funci´on que dada una cadena de caracteres devuelve la expresi´on regular
correspondiente.
•er_of_file : string -> Auto.er
Funci´on que dado un nombre de fichero que contenga una cadena de caracteres
devuelve la expresi´on regular correspondiente. Cuando la especificaci´on de una
expresi´on regular se escribe en un fichero, todo texto que aparezca desde un s´ımbolo
#hasta un final de l´ınea es considerado como un comentario.
•string_of_er : Auto.er -> string
Funci´on que dada una expresi´on regular devuelve la cadena de caracteres
correspondiente.
•file_of_er : Auto.er -> string -> unit
Funci´on que dada una expresi´on regular y un nombre de fichero escribe en ese fichero
la cadena de caracteres correspondiente.
Una vez m´as, para facilitar las tareas de programaci´on, no se han ocultado los constructores
del tipo. As´ı pues, el usuario dispone de mecanismos para crear expresiones regulares
inconsistentes, como por ejemplo Constante (No_terminal "A"). No obstante, si las
expresiones regulares se construyen mediante las funciones descritas anteriormente, est´a
garantizado que eso no ocurrir´a.
Cap´ıtulo 5
Aut´omatas finitos
La siguiente estructura algebraica que implementa el m´odulo Auto es la correspondiente
a los aut´omatas finitos, los cuales constituyen el mecanismo reconocedor de los lenguajes
regulares.
5.1 Definici´on de aut´omata finito
Un aut´omata finito est´a definido por la tupla (Q, Σ, q0,∆, F ) donde: Qes un conjunto
de estados, Σ es el alfabeto de s´ımbolos terminales de entrada, q0es el estado inicial, ∆
es la funci´on de transici´on (es decir, un conjunto de arcos o transiciones que constan de
estado origen, estado destino y s´ımbolo terminal de entrada), y Fes el conjunto de estados
finales. Para ello, el m´odulo Auto define los siguientes tipos de datos:
type estado =
Estado of string;;
type arco_af =
Arco_af of (estado * estado * simbolo);;
type af =
Af of (estado conjunto * simbolo conjunto * estado *
arco_af conjunto * estado conjunto);;
Como se puede observar, al igual que ocurre con los s´ımbolos, los nombres de los estados
de un aut´omata pueden constar de m´as de un caracter.
5.2 Construcci´on de aut´omatas finitos
Los aut´omatas finitos se pueden construir a partir de una especificaci´on en modo texto,
cuya sintaxis es como sigue. Primeramente, deber´an aparecer los nombres de los estados,
separados por espacios y finalizando la secuencia con un punto y coma. Seguidamente,
deber´a aparecer la secuencia de los nombres de los s´ımbolos de entrada, finalizada tambi´en
con un punto y coma. El juego de caracteres v´alido para los nombres de los estados y de
los s´ımbolos est´a formado por todos los caracteres imprimibles, excepto por #(reservado
9
10 Aut´omatas finitos
para comentarios) y por ;(reservado para la finalizaci´on de las secuencias de declaraci´on,
tal y como hemos visto anteriormente). No obstante, dichos caracteres pueden tambi´en
incluirse en el nombre de un estado o de un s´ımbolo si aparecen precedidos de \. Eso s´ı, el
espacio de nombres de estados y el espacio de nombres de s´ımbolos deben ser disjuntos. A
continuaci´on, deber´a aparecer el nombre del estado inicial, seguido de un punto y coma.
El estado inicial debe ser uno de los estados previamente declarados. Seguidamente,
deber´a aparecer la secuencia de los nombres de los estados finales, separados por espacios
y seguida tambi´en de un punto y coma. Los estados finales deben ser tambi´en estados
previamente declarados. Y por ´ultimo, deber´a aparecer la secuencia de arcos. Cada uno
de estos arcos debe tener el formato estado_origen estado_destino simbolo; donde
estado_origen yestado_destino deben ser estados previamente declarados, y simbolo
puede ser un terminal previamente declarado o bien la palabra reservada epsilon. As´ı
pues, por ejemplo, la cadena de caracteres
"0 1 2 3; a b c; 0; 1 3;
0 1 a; 1 1 b; 1 2 a; 2 0 epsilon; 2 3 epsilon; 2 3 c;"
es una posible representaci´on del aut´omata finito
0
1
b
2
a
3
aepsilon
c
epsilon
cuya representaci´on interna ser´ıa
Af (Conjunto [Estado "0"; Estado "1"; Estado "2"; Estado "3"],
Conjunto [Terminal "a"; Terminal "b"; Terminal "c"],
Estado "0",
Conjunto [Arco_af (Estado "0", Estado "1", Terminal "a");
Arco_af (Estado "1", Estado "1", Terminal "b");
Arco_af (Estado "1", Estado "2", Terminal "a");
Arco_af (Estado "2", Estado "0", Terminal "");
Arco_af (Estado "2", Estado "3", Terminal "");
Arco_af (Estado "2", Estado "3", Terminal "c")],
Conjunto [Estado "1"; Estado "3"])
El m´odulo Ergo incluye una serie de funciones para manejar la sintaxis anteriormente
descrita. Dichas funciones son las que se citan a continuaci´on:
•af_of_string : string -> Auto.af
Funci´on que dada una cadena de caracteres devuelve el aut´omata finito
correspondiente.
5.3 Aut´omatas finitos y expresiones regulares 11
•af_of_file : string -> Auto.af
Funci´on que dado un nombre de fichero que contenga una cadena de caracteres
devuelve el aut´omata finito correspondiente. Cuando la especificaci´on de un
aut´omata finito se escribe en un fichero, todo texto que aparezca desde un s´ımbolo
#hasta un final de l´ınea es considerado como un comentario.
•string_of_af : Auto.af -> string
Funci´on que dado un aut´omata finito devuelve la cadena de caracteres
correspondiente.
•file_of_af : Auto.af -> string -> unit
Funci´on que dado un aut´omata finito y un nombre de fichero escribe en ese fichero
la cadena de caracteres correspondiente.
Una vez m´as, para facilitar las tareas de programaci´on, no se han ocultado los constructores
de los tipos. As´ı pues, el usuario dispone de mecanismos para crear aut´omatas finitos
inconsistentes. En este caso, las inconsistencias no s´olo se refieren a la aparici´on de
s´ımbolos no terminales en el alfabeto de entrada Σ o en las etiquetas de los arcos de
∆. Son tambi´en causas de inconsistencias la no equivalencia de los diferentes estados y
s´ımbolos que aparecen en los arcos de ∆ con los conjuntos Qy Σ, respectivamente, o la
no inclusi´on de los estados finales de Fen Q. No obstante, si los aut´omatas finitos se
construyen mediante las funciones descritas anteriormente, est´a garantizado que este tipo
de fen´omenos no se dar´an.
5.3 Aut´omatas finitos y expresiones regulares
Los aut´omatas finitos aceptan lenguajes regulares, los cuales, como hemos visto, se pueden
denotar mediante expresiones regulares. En relaci´on con esto, el m´odulo Auto implementa
la siguiente funci´on:
•af_of_er : Auto.er -> Auto.af
Funci´on que dada una expresi´on regular devuelve el aut´omata que acepta
exactamente el lenguaje regular denotado por dicha expresi´on regular.
5.4 Funcionamiento de un aut´omata finito
Para simular el funcionamiento de un aut´omata finito en el ordenador, el m´odulo Auto
implementa las siguientes funciones:
•epsilon_cierre : Auto.estado Conj.conjunto -> Auto.af -> Auto.estado
Conj.conjunto
Funci´on que dado un conjunto de estados y un aut´omata calcula la uni´on de
los ´epsilon-cierres de todos esos estados, a partir de las ´epsilon-transiciones del
aut´omata.
•escaner_af : Auto.simbolo list -> Auto.af -> bool
Funci´on que dada una lista de s´ımbolos terminales y un aut´omata finito indica si
12 Aut´omatas finitos
dicha cadena de s´ımbolos es aceptada o no por el aut´omata. Se trata de una versi´on
de la funci´on de reconocimiento m´as general posible, es decir, aqu´ella que es capaz
de simular el funcionamiento de cualquier tipo de aut´omata finito (determinista, no
determinista, e incluso no determinista con ´epsilon-transiciones).
5.5 Visualizaci´on de aut´omatas finitos
Para visualizar las representaciones gr´aficas de los aut´omatas finitos, el m´odulo Graf
proporciona la siguiente funci´on:
•dibuja_af : ?titulo:string -> Auto.af -> unit
Funci´on que dado un aut´omata finito, llama al comando dot para visualizar el grafo
de dicho aut´omata en una ventana x11. Opcionalmente, se puede dar un t´ıtulo para
el grafo.
Cap´ıtulo 6
Gram´aticas independientes del
contexto
La siguiente estructura algebraica que implementa el m´odulo Auto es la correspondiente a
los gram´aticas. M´as concretamente, se trata del tipo de gram´aticas que permiten denotar
los lenguajes independientes del contexto.
6.1 Definici´on de gram´atica independiente del
contexto
Una gram´atica independiente del contexto est´a definida por la tupla (N, T, P, S) donde:
Nes el conjunto de s´ımbolos no terminales, Tes el conjunto de s´ımbolos terminales, Pes
el conjunto de reglas de producci´on, y Ses un elemento destacado de Nque denominamos
s´ımbolo inicial o axioma de la gram´atica. Cada regla de producci´on reescribe un s´ımbolo
no terminal en una lista de s´ımbolos que pueden ser tanto terminales como no terminales,
en cualquier n´umero y en cualquier orden. Para ello, el m´odulo Auto define los siguientes
tipos de datos:
type regla_gic =
Regla_gic of (simbolo * simbolo list);;
type gic =
Gic of (simbolo conjunto * simbolo conjunto * regla_gic conjunto *
simbolo);;
En particular, el tipo regla_gic deja clara constancia de la diferencia entre una lista y
un conjunto, y justifica la inclusi´on de los s´ımbolos terminales y no terminales bajo un
mismo tipo de dato, con el fin de que tanto unos como otros puedan aparecer juntos en la
parte derecha de una regla de reescritura.
13
14 Gram´aticas independientes del contexto
6.2 Construcci´on de gram´aticas independientes del
contexto
Las gram´aticas se pueden construir a partir de una especificaci´on en modo texto, cuya
sintaxis es como sigue. Primeramente, deber´an aparecer los nombres de los s´ımbolos
no terminales, separados por espacios y finalizando la secuencia con un punto y coma.
Seguidamente, deber´a aparecer la secuencia de los nombres de los s´ımbolos terminales,
finalizada tambi´en con un punto y coma. El juego de caracteres v´alido para los nombres
de los estados y de los s´ımbolos est´a formado por todos los caracteres imprimibles, excepto
por #(reservado para comentarios), por ;(reservado para la finalizaci´on de las secuencias
de declaraci´on, tal y como hemos visto anteriormente) y por |(reservado para que varias
partes derecha de una regla compartan la misma parte izquierda, como veremos m´as
adelante). No obstante, dichos caracteres pueden tambi´en incluirse en el nombre de un
estado o de un s´ımbolo si aparecen precedidos de \. Eso s´ı, el espacio de nombres de los no
terminales y el espacio de nombres de los terminales deben ser disjuntos. A continuaci´on,
deber´a aparecer el nombre del s´ımbolo inicial, seguido de un punto y coma. El s´ımbolo
inicial debe ser uno de los no terminales previamente declarados. Y por ´ultimo, deber´a
aparecer la secuencia de producciones o reglas de reescritura. Cada una de estas reglas
debe tener el formato
no_terminal -> simbolo_1 simbolo_2 ... simbolo_n;
donde todos los s´ımbolos que aparecen en la parte derecha de la flecha deben ser terminales
o no terminales previamente declarados. Las reglas que compartan la misma parte
izquierda se pueden escribir tambi´en de la forma
no_terminal -> parte_dcha_1 | parte_dcha_2 | ... | parte_dcha_n;
Existe la palabra reservada epsilon para denotar una parte derecha vac´ıa. As´ı pues, por
ejemplo, la cadena de caracteres
"S A B; a b c; S; S -> a A; A -> a b c A | b B; B -> b c B | epsilon;"
es una posible representaci´on de la gram´atica
Gic (Conjunto [No_terminal "S"; No_terminal "A"; No_terminal "B"],
Conjunto [Terminal "a"; Terminal "b"; Terminal "c"],
Conjunto [
Regla_gic (No_terminal "S", [Terminal "a"; No_terminal "A"]);
Regla_gic (No_terminal "A",
[Terminal "a"; Terminal "b"; Terminal "c";
No_terminal "A"]);
Regla_gic (No_terminal "A", [Terminal "b"; No_terminal "B"]);
Regla_gic (No_terminal "B",
[Terminal "b"; Terminal "c"; No_terminal "B"]);
Regla_gic (No_terminal "B", [])],
No_terminal "S")
6.3 Gram´aticas regulares 15
El m´odulo Ergo incluye una serie de funciones para manejar la sintaxis anteriormente
descrita. Dichas funciones son las que se citan a continuaci´on:
•gic_of_string : string -> Auto.gic
Funci´on que dada una cadena de caracteres devuelve la gram´atica independiente del
contexto correspondiente.
•gic_of_file : string -> Auto.gic
Funci´on que dado un nombre de fichero que contenga una cadena de caracteres
devuelve la gram´atica independiente del contexto correspondiente. Cuando la
especificaci´on de una gram´atica independiente del contexto se escribe en un fichero,
todo texto que aparezca desde un s´ımbolo #hasta un final de l´ınea es considerado
como un comentario.
•string_of_gic : Auto.gic -> string
Funci´on que dada una gram´atica independiente del contexto devuelve la cadena de
caracteres correspondiente.
•file_of_gic : Auto.gic -> string -> unit
Funci´on que dada una gram´atica independiente del contexto y un nombre de fichero
escribe en ese fichero la cadena de caracteres correspondiente.
Una vez m´as, para facilitar las tareas de programaci´on, no se han ocultado los constructores
de los tipos. As´ı pues, el usuario dispone de mecanismos para crear gram´aticas
inconsistentes. En este caso, las inconsistencias pueden referirse a la mezcla de terminales
y no terminales en los conjuntos NyT, a la no equivalencia de los diferentes s´ımbolos
que aparecen en las producciones de Pcon los conjuntos NyT, a la presencia de un
s´ımbolo terminal como parte izquierda de una producci´on, a la no inclusi´on del axioma de
la gram´atica en N, etc. No obstante, si las gram´aticas se construyen mediante las funciones
descritas anteriormente, est´a garantizado que no aparecer´an este tipo de fen´omenos.
6.3 Gram´aticas regulares
Una gram´atica independiente del contexto es regular cuando todas las partes derechas de
sus reglas de producci´on contienen como m´aximo un s´ımbolo no terminal y, adem´as, si
dicho s´ımbolo aparece, es siempre el ´ultimo s´ımbolo de la regla. En relaci´on con esto, el
m´odulo Auto implementa las siguientes funciones:
•es_regular : Auto.gic -> bool
Funci´on que dada una gram´atica independiente del contexto indica si es o no regular.
La funci´on comprueba ´unicamente el formato de las reglas. Por tanto, se recomienda
usarla sobre gram´aticas generadas con las funciones gic_of_string ogic_of_file
del m´odulo Ergo, ya que las comprobaciones que no se realizan aqu´ı las hacen
autom´aticamente esas funciones. As´ı pues, en principio, si la gram´atica resulta
no ser regular, sigue siendo una gram´atica correcta, lo que ocurre es que ser´a una
gram´atica independiente del contexto no regular.
16 Gram´aticas independientes del contexto
•af_of_gic : Auto.gic -> Auto.af
Funci´on que dada una gram´atica regular devuelve el aut´omata finito que acepta
exactamente el mismo lenguaje regular generado por dicha gram´atica.
•gic_of_af : Auto.af -> Auto.gic
Funci´on que dado un aut´omata finito devuelve la gram´atica regular que genera
exactamente el mismo lenguaje regular aceptado por dicho aut´omata.
Cap´ıtulo 7
Aut´omatas de pila
La siguiente estructura algebraica que implementa el m´odulo Auto es la correspondiente a
los aut´omatas de pila, los cuales constituyen un posible mecanismo reconocedor para los
lenguajes independientes del contexto.
7.1 Definici´on de aut´omata de pila
Un aut´omata de pila est´a definido por la tupla (Q, Σ,Γ, q0,∆, Z, F ) donde: Qes un
conjunto de estados, Σ es el alfabeto de s´ımbolos terminales de entrada, Γ es el alfabeto de
la pila, q0es el estado inicial, ∆ es la funci´on de transici´on (es decir, un conjunto de arcos
o transiciones que constan de estado origen, estado destino, s´ımbolo terminal de entrada,
s´ımbolo de la cima de la pila, y cadena de s´ımbolos que reemplazan a dicho s´ımbolo en la
cima de la pila), Zes el s´ımbolo de inicio de pila, y Fes el conjunto de estados finales.
Para ello, el m´odulo Auto define los siguientes tipos de datos:
type arco_ap =
Arco_ap of (estado * estado * simbolo * simbolo * simbolo list);;
type ap =
Ap of (estado conjunto * simbolo conjunto * simbolo conjunto *
estado * arco_ap conjunto * simbolo * estado conjunto);;
Como viene siendo habitual, tanto los nombres de los estados como los nombres de los
s´ımbolos pueden constar de m´as de un caracter. El s´ımbolo especial de inicio de pila
ser´a representado mediante No_terminal "", y existir´a la palabra reservada zeta para
denotarlo.
7.2 Construcci´on de aut´omatas de pila
Los aut´omatas de pila se pueden construir a partir de una especificaci´on en modo texto,
cuya sintaxis es como sigue. Primeramente, deber´an aparecer los nombres de los estados,
separados por espacios y finalizando la secuencia con un punto y coma. Seguidamente,
deber´a aparecer la secuencia de los nombres de los s´ımbolos de entrada, finalizada tambi´en
con un punto y coma. Seguidamente, deber´a aparecer la secuencia de los nombres de los
17
18 Aut´omatas de pila
s´ımbolos de la pila, finalizada tambi´en con un punto y coma. El juego de caracteres
v´alido para los nombres de los estados y de los s´ımbolos est´a formado por todos los
caracteres imprimibles, excepto por #(reservado para comentarios) y por ;(reservado para
la finalizaci´on de las secuencias de declaraci´on, tal y como hemos visto anteriormente).
No obstante, dichos caracteres pueden tambi´en incluirse en el nombre de un estado o de
un s´ımbolo si aparecen precedidos de \. Eso s´ı, el espacio de nombres de estados, y el
espacio de nombres de s´ımbolos de entrada y de pila deben ser disjuntos entre s´ı. Por
otra parte, existe la palabra reservada zeta para hacer referencia al s´ımbolo de inicio de
pila. A continuaci´on, deber´a aparecer el nombre del estado inicial, seguido de un punto y
coma. El estado inicial debe ser uno de los estados previamente declarados. Seguidamente,
deber´a aparecer la secuencia de los nombres de los estados finales, separados por espacios
y seguida tambi´en de un punto y coma. Los estados finales deben ser tambi´en estados
previamente declarados. Y por ´ultimo, deber´a aparecer la secuencia de arcos. Cada uno
de estos arcos debe tener el formato
estado_origen estado_destino simbolo_de_entrada
simbolo_en_cima_de_pila nuevos_simbolos_en_cima_de_pila;
As´ı pues, por ejemplo, la cadena de caracteres
"0 1 2 3; a b; zeta A; 0; 3; 0 1 a zeta A zeta; 1 1 a A A A; 1 2 b A epsilon;
2 2 b A epsilon; 2 3 epsilon zeta zeta;"
es una posible representaci´on del aut´omata de pila
0 31
a, zeta / A zeta
a, A / A A
2
b, A / epsilon epsilon, zeta / zeta
b, A / epsilon
cuya representaci´on interna ser´ıa
Ap (Conjunto [Estado "0"; Estado "1"; Estado "2"; Estado "3"],
Conjunto [Terminal "a"; Terminal "b"],
Conjunto [No_terminal ""; No_terminal "A"],
Estado "0",
Conjunto [Arco_ap (Estado "0", Estado "1", Terminal "a",
No_terminal "",
[No_terminal "A"; No_terminal ""]);
Arco_ap (Estado "1", Estado "1", Terminal "a",
No_terminal "A",
[No_terminal "A"; No_terminal "A"]);
Arco_ap (Estado "1", Estado "2", Terminal "b",
No_terminal "A",
[]);
Arco_ap (Estado "2", Estado "2", Terminal "b",
No_terminal "A",
[]);
7.3 Funcionamiento de un aut´omata de pila 19
Arco_ap (Estado "2", Estado "3", Terminal "",
No_terminal "",
[No_terminal ""])],
No_terminal "",
Conjunto [Estado "3"])
El m´odulo Ergo incluye una serie de funciones para manejar la sintaxis anteriormente
descrita. Dichas funciones son las que se citan a continuaci´on:
•ap_of_string : string -> Auto.ap
Funci´on que dada una cadena de caracteres devuelve el aut´omata de pila
correspondiente.
•ap_of_file : string -> Auto.ap
Funci´on que dado un nombre de fichero que contenga una cadena de caracteres
devuelve el aut´omata de pila correspondiente. Cuando la especificaci´on de un
aut´omata de pila se escribe en un fichero, todo texto que aparezca desde un s´ımbolo
#hasta un final de l´ınea es considerado como un comentario.
•string_of_ap : Auto.ap -> string
Funci´on que dado un aut´omata de pila devuelve la cadena de caracteres
correspondiente.
•file_of_ap : Auto.ap -> string -> unit
Funci´on que dado un aut´omata de pila y un nombre de fichero escribe en ese fichero
la cadena de caracteres correspondiente.
Una vez m´as, para facilitar las tareas de programaci´on, no se han ocultado los constructores
de los tipos. As´ı pues, el usuario dispone de mecanismos para crear aut´omatas de pila
inconsistentes. No obstante, si los aut´omatas de pila se construyen mediante las funciones
descritas anteriormente, est´a garantizado que este fen´omeno no se producir´a.
7.3 Funcionamiento de un aut´omata de pila
Para simular el funcionamiento de un aut´omata de pila en el ordenador, el m´odulo Auto
implementa la siguiente funci´on:
•escaner_ap : Auto.simbolo list -> Auto.ap -> bool
Funci´on que dada una lista de s´ımbolos terminales y un aut´omata de pila indica si
dicha cadena de s´ımbolos es aceptada o no por el aut´omata.
7.4 Visualizaci´on de aut´omatas de pila
Para visualizar las representaciones gr´aficas de los aut´omatas de pila, el m´odulo Graf
proporciona la siguiente funci´on:
20 Aut´omatas de pila
•dibuja_ap : ?titulo:string -> Auto.ap -> unit
Funci´on que dado un aut´omata de pila, llama al comando dot para visualizar el
grafo de dicho aut´omata en una ventana x11. Opcionalmente, se puede dar un t´ıtulo
para el grafo.
Cap´ıtulo 8
M´aquinas de Turing
La siguiente estructura algebraica que implementa el m´odulo Auto es la correspondiente
a las m´aquinas de Turing, las cuales representan un posible mecanismo reconocedor para
los lenguajes recursivos y recursivamente enumerables. Adem´as de esto, la m´aquina de
Turing constituye en s´ı misma un modelo abstracto de computaci´on.
8.1 Definici´on de m´aquina de Turing
Una m´aquina de Turing est´a definida por la tupla (Q, Σ,Γ, q0,∆, B, F ) donde: Qes un
conjunto de estados, Σ es el alfabeto de s´ımbolos terminales de entrada, Γ es el alfabeto
de la cinta, q0es el estado inicial, ∆ es la funci´on de transici´on (es decir, un conjunto
de arcos o transiciones que constan de estado origen, estado destino, s´ımbolo que se lee
en la cinta, s´ımbolo que se escribe en la cinta, y movimiento que realiza la cabeza de
lectura/escritura), Bes el s´ımbolo blanco, y Fes el conjunto de estados finales. Para ello,
el m´odulo Auto define los siguientes tipos de datos:
type movimiento_mt =
Izquierda
| Derecha;;
type arco_mt =
Arco_mt of (estado * estado * simbolo * simbolo * movimiento_mt);;
type mt =
Mt of (estado conjunto * simbolo conjunto * simbolo conjunto *
estado * arco_mt conjunto * simbolo * estado conjunto);;
Como viene siendo habitual, tanto los nombres de los estados como los nombres de los
s´ımbolos pueden constar de m´as de un caracter. El s´ımbolo blanco ser´a representado
mediante No_terminal "", y existir´a la palabra reservada blanco para denotarlo.
21
22 M´aquinas de Turing
8.2 Construcci´on de m´aquinas de Turing
Las m´aquinas de Turing se pueden construir a partir de una especificaci´on en modo texto,
cuya sintaxis es como sigue. Primeramente, deber´an aparecer los nombres de los estados,
separados por espacios y finalizando la secuencia con un punto y coma. Seguidamente,
deber´a aparecer la secuencia de los nombres de los s´ımbolos de entrada, finalizada tambi´en
con un punto y coma. Seguidamente, deber´a aparecer la secuencia de los nombres de los
s´ımbolos de la cinta, finalizada tambi´en con un punto y coma. El juego de caracteres
v´alido para los nombres de los estados y de los s´ımbolos est´a formado por todos los
caracteres imprimibles, excepto por #(reservado para comentarios) y por ;(reservado para
la finalizaci´on de las secuencias de declaraci´on, tal y como hemos visto anteriormente).
No obstante, dichos caracteres pueden tambi´en incluirse en el nombre de un estado o de
un s´ımbolo si aparecen precedidos de \. Eso s´ı, el espacio de nombres de estados, y el
espacio de nombres de s´ımbolos de entrada y de la cinta deben ser disjuntos entre s´ı. Por
otra parte, existe la palabra reservada blanco para hacer referencia al s´ımbolo blanco. A
continuaci´on, deber´a aparecer el nombre del estado inicial, seguido de un punto y coma. El
estado inicial debe ser uno de los estados previamente declarados. Seguidamente, deber´a
aparecer la secuencia de los nombres de los estados finales, separados por espacios y seguida
tambi´en de un punto y coma. Los estados finales deben ser tambi´en estados previamente
declarados. Y por ´ultimo, deber´a aparecer la secuencia de arcos. Cada uno de estos arcos
debe tener el formato
estado_origen estado_destino simbolo_de_lectura_en_la_cinta
simbolo_de_escritura_en_la_cinta movimiento_de_la_cabeza;
As´ı pues, por ejemplo, la cadena de caracteres
"0 1 2 3 4 5 6 7; a b c; blanco a b c; 0; 4 7;
0 1 blanco blanco derecha; 1 1 a a derecha; 1 1 b b derecha;
1 1 c c derecha; 1 2 c c derecha; 2 3 a a derecha; 3 4 b b derecha;
1 5 c c izquierda; 5 6 b b izquierda; 6 7 a a izquierda;"
es una posible representaci´on de la m´aquina de Turing
0
4
7
1
blanco / blanco, derecha
a / a, derecha
b / b, derecha
c / c, derecha
2
c / c, derecha
5
c / c, izquierda
3
a / a, derecha b / b, derecha
6
b / b, izquierda a / a, izquierda
cuya representaci´on interna ser´ıa
Mt (Conjunto [Estado "0"; Estado "1"; Estado "2"; Estado "3";
Estado "4"; Estado "5"; Estado "6"; Estado "7"],
Conjunto [Terminal "a"; Terminal "b"; Terminal "c"],
Conjunto [No_terminal ""; Terminal "a"; Terminal "b"; Terminal "c"],
8.2 Construcci´on de m´aquinas de Turing 23
Estado "0",
Conjunto [Arco_mt (Estado "0", Estado "1",
No_terminal "", No_terminal "", Derecha);
Arco_mt (Estado "1", Estado "1",
Terminal "a", Terminal "a", Derecha);
Arco_mt (Estado "1", Estado "1",
Terminal "b", Terminal "b", Derecha);
Arco_mt (Estado "1", Estado "1",
Terminal "c", Terminal "c", Derecha);
Arco_mt (Estado "1", Estado "2",
Terminal "c", Terminal "c", Derecha);
Arco_mt (Estado "2", Estado "3",
Terminal "a", Terminal "a", Derecha);
Arco_mt (Estado "3", Estado "4",
Terminal "b", Terminal "b", Derecha);
Arco_mt (Estado "1", Estado "5",
Terminal "c", Terminal "c", Izquierda);
Arco_mt (Estado "5", Estado "6",
Terminal "b", Terminal "b", Izquierda);
Arco_mt (Estado "6", Estado "7",
Terminal "a", Terminal "a", Izquierda)],
No_terminal "",
Conjunto [Estado "4"; Estado "7"])
El m´odulo Ergo incluye una serie de funciones para manejar la sintaxis anteriormente
descrita. Dichas funciones son las que se citan a continuaci´on:
•mt_of_string : string -> Auto.mt
Funci´on que dada una cadena de caracteres devuelve la m´aquina de Turing
correspondiente.
•mt_of_file : string -> Auto.mt
Funci´on que dado un nombre de fichero que contenga una cadena de caracteres
devuelve la m´aquina de Turing correspondiente. Cuando la especificaci´on de una
m´aquina de Turing se escribe en un fichero, todo texto que aparezca desde un s´ımbolo
#hasta un final de l´ınea es considerado como un comentario.
•string_of_mt : Auto.mt -> string
Funci´on que dada una m´aquina de Turing devuelve la cadena de caracteres
correspondiente.
•file_of_mt : Auto.mt -> string -> unit
Funci´on que dada una m´aquina de Turing y un nombre de fichero escribe en ese
fichero la cadena de caracteres correspondiente.
Una vez m´as, para facilitar las tareas de programaci´on, no se han ocultado los constructores
de los tipos. As´ı pues, el usuario dispone de mecanismos para crear m´aquinas de Turing
inconsistentes. No obstante, si las m´aquinas de Turing se construyen mediante las
funciones descritas anteriormente, est´a garantizado que este fen´omeno no se producir´a.
24 M´aquinas de Turing
8.3 Funcionamiento de una m´aquina de Turing
Para simular el funcionamiento de una m´aquina de Turing en el ordenador, el m´odulo
Auto implementa las siguientes funciones:
•escaner_mt : Auto.simbolo list -> Auto.mt -> bool
Funci´on que dada una lista de s´ımbolos terminales y una m´aquina de Turing indica
si dicha cadena de s´ımbolos es aceptada o no por la m´aquina. Se trata de la versi´on
m´as b´asica de la funci´on, es decir, aqu´ella que simplemente indica si la m´aquina se
detiene, y si lo hace en un estado final o de aceptaci´on, pero no devuelve el contenido
de la cinta despu´es de la parada.
•scpm : Auto.mt -> Auto.simbolo list -> (string * string) list
Funci´on que dada una m´aquina de Turing y una cadena de entrada, devuelve el
SCPM (Sistema de Correspondecia de Post Modificado) asociado.
8.4 Visualizaci´on de m´aquinas de Turing
Para visualizar las representaciones gr´aficas de las m´aquinas de Turing, el m´odulo Graf
proporciona la siguiente funci´on:
•dibuja_mt : ?titulo:string -> Auto.mt -> unit
Funci´on que dada una m´aquina de Turing, llama al comando dot para visualizar el
grafo de dicha m´aquina en una ventana x11. Opcionalmente, se puede dar un t´ıtulo
para el grafo.
