Mathematics">
Teoriaautomatas y Len..
Teoriaautomatas y Len..
Teoriaautomatas y Len..
ISBN 84-7723-747-6
ISBN 978-84-7723-747-1
Teorías de Autómatas
y Lenguajes Formales
9 788477 237471
50 Elena 55
Jurado Málaga
Teoría de autómatas
y lenguajes formales
manuales uex
55 (E.E.E.S.)
Espacio
Europeo
Educación
Superior
Elena jurado málaga
teoría de autómatas
y lenguajes formales
2008
La publicación del presente manual fue subvencionada por el Vicerrectorado de
Calidad y Formación Continua de la Universidad de Extremadura en la Convocatoria
de Acciones para la Mejora de la Calidad Docente del curso 2007/08 dentro de la
modalidad B.2: “Diseño y desarrollo de materiales docentes adaptados a la metodo-
logía derivada del E.E.E.S.” Esta convocatoria de acciones forma parte del Plan de
Adaptación de la UEX al Espacio Europeo de Educación Superior.
FSE
Fo n d o S o c i a l E u ro p e o
Edita
ISSN 1135-870-X
ISBN 978-84-691-6345-0
Depósito Legal M-45.211-2008
curso para impartirla. Por tanto, y teniendo en cuenta sobre todo esto último, los
contenidos han sido seleccionados de forma realista con la intención de que puedan
ser abarcados por completo a lo largo del curso académico. Por este motivo, la alta
carga formal que suele acompañar a los libros de esta materia ha sido aligerada,
procurando no incluir, siempre que ha sido posible, demostraciones complejas y otras
cuestiones formales que harı́an el texto inabordable en una única asignatura. Como
contrapartida se han intentado presentar los conceptos e ideas básicos de una manera
intuitiva y clara.
Otro de los aspectos que se ha tenido en cuenta al diseñar los contenidos del
manual ha sido destacar una de las aplicaciones prácticas más interesantes de esta
materia: el diseño de lenguajes de programación y de compiladores. Esto ha motivado
que, al clásico estudio de la jerarquı́a para las gramáticas formales de Chomsky, de
los Autómatas Finitos, de los Autómatas de Pila y de las Máquinas de Turing, se
hayan añadido temas como el de las gramáticas atribuidas, los reconocedores LR o
un anexo sobre la generación automática de analizadores léxicos y sintácticos. Si bien
estás últimas cuestiones pueden considerarse al margen de la asignatura, tienen un
claro interés desde el punto de vista práctico.
Considerando la próxima implantación de los nuevos planes de estudio dentro del
espacio europeo de educación superior, se ha incluido un apartado en el que se describe
el plan docente de la asignatura, indicando la metodologı́a docente, el plan de trabajo
del estudiante, ası́ como las competencias especı́ficas de la materia y de la titulación.
En este sentido, y teniendo en cuenta que el trabajo no presencial del estudiante
tiene cada vez más relevancia en el nuevo marco de las enseñanzas universitarias,
consideramos que este manual puede convertirse en una herramienta de gran utilidad
para los estudiantes, como complemento a los apuntes y como material de ayuda en
la preparación previa de los temas.
Quisiera terminar este prólogo agradeciendo la colaboración de los estudiantes que
han cursado esta asignatura durante los últimos años. Sus comentarios y sugerencias
han resultado imprescindibles para mejorar los contenidos y el diseño de las primeras
versiones de este manual.
X
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
Plan Docente
I. Descripción y contextualización
Identificación y caracterı́sticas de la materia
Denominación: Teorı́a de Autómatas y Lenguajes Formales
Curso y Titulaciones:
3o Ingenierı́a Informática,
3o Ingenierı́a Técnica en Informática de Sistemas,
3o Ingenierı́a Técnica en Informática de Gestión
Área: Lenguajes y Sistemas Informáticos
Departamento: Ingenierı́a de Sistemas Informáticos y Telemáticos
Tipo:
Troncal en Ingenierı́a Informática,
Troncal en Ingenierı́a Técnica en Informática de Sistemas,
Optativa en Ingenierı́a Técnica en Informática de Gestión
Coeficientes:
Practicidad: 3 (Medio)
Agrupamiento: 3 (Medio)
Duración: Anual, 8.18 créditos ECTS (204.5 horas)
Distribución ECTS:
Grupo Grande: 62 horas (30.31 %)
Seminario-Laboratorio: 20 horas (9.77 %)
Tutorı́a ECTS: 10 horas (4.88 %)
No presencial: 112.5 horas (55.01 %)
Descriptores (según BOE): Teorı́a de Autómatas y Lenguajes Formales
XI
Elena Jurado Málaga
2. Comunicar de forma efectiva, tanto por escrito como oral, conocimientos, pro-
cedimientos, resultados e ideas relacionadas con las TIC y, concretamente de la
Informática, conociendo su impacto socioeconómico.(Todos)
XII
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
15. Ser capaz de demostrar que algunas funciones son recursivas primitivas o µ-
recursivas.(5,6,7)
16. Entender el concepto y conocer ejemplos de problemas de la clase P, NP o
NP-completo.(5,6,7)
XIII
Elena Jurado Málaga
III. Contenidos
Los contenidos de la asignatura son los que se describen a lo largo de este docu-
mento (ver Índice General ).
Interrelaciones
1. Las asignaturas de 1o curso, Elementos de Programación y Laboratorio
de Programación I, y de 2o curso, Estructuras de Datos y Algoritmos y
Laboratorio de Programación II, son requisitos para esta asignatura ya que
proporcionan los conocimientos sobre programación necesarios para abordar la
tarea de la construcción de un compilador. También permiten que el alumno
conozca con antelación conceptos básicos para la asignatura como el de lenguaje
de programación y el de compilador.
XIV
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
XV
Elena Jurado Málaga
V. Evaluación
Criterios de Evaluación
1. Aplicar los conceptos y métodos estudiados para la resolución de problemas
manuales uex
XVI
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
XVII
Índice General
1. Preliminares 5
1.1. Antecedentes históricos y conceptos básicos . . . . . . . . . . . . . . . 5
1.2. Desarrollo de la asignatura . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3. Conceptos básicos sobre compiladores . . . . . . . . . . . . . . . . . . 10
1.3.1. Componentes de un compilador . . . . . . . . . . . . . . . . . 11
1
1
ELENA JURADO MÁLAGA
2 ÍNDICE GENERAL
4. Autómatas Finitos 39
4.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.2. Definición de Autómata Finito Determinista . . . . . . . . . . . . . . 40
4.3. Representación de Autómatas . . . . . . . . . . . . . . . . . . . . . . 40
4.4. Los AFD como reconocedores de lenguajes . . . . . . . . . . . . . . . 43
4.5. Minimización de un AFD . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.6. Autómatas Finitos No Deterministas(AFND) . . . . . . . . . . . . . 47
4.7. Lenguaje aceptado por un AFND . . . . . . . . . . . . . . . . . . . . 50
4.8. Simulación de un AFD y AFND . . . . . . . . . . . . . . . . . . . . . 51
4.9. Paso de un AFND a AFD . . . . . . . . . . . . . . . . . . . . . . . . 52
4.10. Relación entre AF, gr. y exp. reg. . . . . . . . . . . . . . . . . . . . . 55
4.10.1. Construcción de la expresión regular reconocida por un AF . . 55
4.10.2. Construcción del AF que reconoce una expresión regular . . . 58
4.10.3. Relación entre A.F. y gramáticas regulares . . . . . . . . . . . 62
4.11. Lı́mites para los leng. regulares . . . . . . . . . . . . . . . . . . . . . 65
4.11.1. El lema del bombeo(pumping lemma) . . . . . . . . . . . . . . 65
4.11.2. El teorema de Myhill-Nerode . . . . . . . . . . . . . . . . . . 66
4.12. Problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
6. Gramáticas Atribuidas 97
6.1. Concepto de Semántica y de Gramática Atribuida . . . . . . . . . . . 97
6.2. Atributos heredados y sintetizados . . . . . . . . . . . . . . . . . . . 99
Manuales Uex
2
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
ÍNDICE GENERAL 3
3
ELENA JURADO MÁLAGA
4 ÍNDICE GENERAL
4
Tema 1
Preliminares
Contenido
1.1. Antecedentes históricos y conceptos básicos . . . . . . . 5
1.2. Desarrollo de la asignatura . . . . . . . . . . . . . . . . . . 8
1.3. Conceptos básicos sobre compiladores . . . . . . . . . . . 10
5
5
ELENA JURADO MÁLAGA
6 TEMA 1. PRELIMINARES
bases de la asignatura ası́ como los campos cientı́ficos que han influido fundamental-
mente en el desarrollo de esta materia y que nos ayudarán a entender sus aplicaciones
más importantes.
Veamos, en primer lugar, la relación entre conceptos que trataremos a lo largo
de todo el temario: lenguaje, gramática y autómata. Toda comunicación conlle-
va la utilización de un lenguaje, que podemos definir como un conjunto de palabras
(también llamadas cadenas) formadas por sı́mbolos de un alfabeto. Las gramáticas
permitirán definir la estructura de los lenguajes, es decir, proporcionarán las formas
válidas en las que se pueden combinar los sı́mbolos del alfabeto para construir ca-
denas correctas. Una máquina abstracta o autómata es un dispositivo teórico que
recibe como entrada una cadena de sı́mbolos y los procesa, cambiando de estado, de
manera que genera una determinada salida. Los autómatas pueden servir, entre otras
cosas, para determinar si una palabra pertenece o no a un determinado lenguaje. Por
lo tanto, las gramáticas nos permitirán definir lenguajes y los autómatas podrán re-
conocer las palabras de dichos lenguajes. A pesar de la conexión que existe entre estos
conceptos, los trabajos iniciales sobre autómatas y lenguajes tienen, como veremos a
continuación, un origen diferente.
Para encontrar los principios de la Informática Teórica debemos remontarnos a
los años 30, década en la que el mundo de las matemáticas se hallaba ocupado, sobre
todo, en temas como la lógica y la definición de sistemas axiomáticos.
El método axiomático requiere una colección de enunciados básicos, llamados
axiomas, que describen las propiedades fundamentales del sistema que se estudia.
A partir de estos axiomas, se derivan enunciados adicionales, llamados teoremas,
aplicando secuencias finitas de reglas de inferencia.
Una ventaja del método axiomático es que ofrece un modelo de razonamiento
deductivo en el cual todas las suposiciones están aisladas en los axiomas iniciales y
las reglas de inferencia. Cualquier enunciado que se derive posteriormente será una
consecuencia de estas suposiciones.
A principios del siglo XX, muchos matemáticos creı́an que era posible encontrar un
único sistema axiomático en el que podrı́an basarse todas las matemáticas. Su meta
era encontrar un conjunto de axiomas y reglas de inferencia correctos de manera que
las matemáticas pudieran reducirse a un sistema computacional con el cual pudiera
deducirse la veracidad o falsedad de cualquier enunciado matemático. Uno de los
principales defensores de esta idea era el conocido matemático alemán Hilbert.
Sin embargo, en 1931, el austriaco Kurt Gödel publicó el “Teorema de la in-
completitud”, en el que demostraba que era imposible la completa axiomatización
de las matemáticas. Este teorema incrementó el debate por el poder de los métodos
Manuales Uex
6
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
1
Un algoritmo puede considerarse como un método genérico que, en un número finito de pasos
o computaciones, permite resolver un determinado problema. Recordemos que la palabra algoritmo
debe su nombre a un matemático persa Abu Ja’far Mohamed ibn Musa al-Jowâizmı̂, autor de un
tratado de aritmética publicado en el año 825.
7
ELENA JURADO MÁLAGA
8 TEMA 1. PRELIMINARES
Leng. LR(k)
Gr. Autómatas
Leng. LR(1) tipo 2 de Pila
Leng. LL(k)
8
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
(los de tipo 3) y de los autómatas asociados a ellos, para acabar con el estudio de
los lenguajes de tipo 0 y de las M.T. Los nombres de los lenguajes de la jerarquı́a
de Chomsky aparecen destacados en esta figura, pero también aparecen otros con-
juntos de lenguajes que representan niveles intermedios de esta jerarquı́a y que por
su interés serán también estudiados en la asignatura. Concretamente, los lenguajes
LL(1) y LR(1), incluidos en el conjunto de los lenguajes independientes del contexto
se estudiarán en el tema 5 y los lenguajes recursivos serán tratados en el tema 8.
Como muestra la figura 1.1, en los tres conceptos estudiados (gramáticas, lengua-
jes y autómatas) cada nivel contiene al anterior. Por ejemplo, cualquier lenguaje de
tipo 3 es a su vez un lenguaje de tipo2 (sin embargo, comprobaremos que lo contrario
no es cierto), es decir (L3�L2�L1�L0). De la misma forma, un Autómata Finito
puede considerarse como un caso particular de Autómata de Pila y éste como un
caso particular de Máquina de Turing.
A continuación comentaremos cuáles son las principales aplicaciones de los temas
que se estudiarán en esta asignatura.
El estudio de las gramáticas formales será una herramienta muy útil para el
diseño de los lenguajes de programación. El estudio de determinados autómatas
(concretamente los autómatas finitos y los de pila) permitirá construir de ma-
nera sistemática algunos de los componentes básicos de los compiladores.
9
ELENA JURADO MÁLAGA
10 TEMA 1. PRELIMINARES
Los autómatas son también esenciales para el estudio de los lı́mites de la com-
putación. En este terreno, existen dos cuestiones importantes que nos podemos
plantear y que se estudiarán en los últimos temas de la asignatura:
10
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
El compilador tiene una visión completa del programa, por lo que puede dar
una información más detallada de los errores cometidos por el programador.
Análisis léxico El analizador léxico, también conocido como scanner, lee los ca-
racteres del programa fuente, uno a uno, desde el fichero de entrada y va formando
grupos de caracteres con alguna relación entre sı́ (tokens). Cada token es tratado co-
mo una única entidad, constituyendo la entrada de la siguiente fase del compilador.
Existen diferentes tipos de tokens y a cada uno se le puede asociar un tipo y, en
algunos casos, un valor. Los tokens se pueden agrupar en dos categorı́as:
Manuales Uex
Cadenas especı́ficas, como las palabras reservadas (if, while, . . .), signos de pun-
tuación (., ,, =, . . .), operadores aritméticos (+,*, . . .) y lógicos (AND, OR, . . .),
etc. Habitualmente, las cadenas especı́ficas no tienen asociado ningún valor, sólo
su tipo.
11
ELENA JURADO MÁLAGA
12 TEMA 1. PRELIMINARES
12
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
Estas fases se añaden al compilador para conseguir que el programa objeto sea
más rápido y necesite menos memoria para ejecutarse.
Veamos en los siguientes párrafos algunos ejemplos de optimización:
Optimizar los bucles. Se trata de sacar de los bucles aquellas expresiones que
sean invariantes.
REPEAT
B := 1
A := A-B
UNTIL A = 0 La asignación B := 1 se puede sacar del bucle
13
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
Tema 2
Contenido
2.1. Definiciones básicas . . . . . . . . . . . . . . . . . . . . . . 15
2.2. Operaciones con palabras . . . . . . . . . . . . . . . . . . . 16
2.3. Lenguajes y operaciones con lenguajes . . . . . . . . . . . 17
2.4. Concepto de gramática formal . . . . . . . . . . . . . . . . 19
2.5. Clasificación de las gr. formales . . . . . . . . . . . . . . . 24
2.6. Gramáticas equivalentes . . . . . . . . . . . . . . . . . . . 26
2.7. Problemas y cuestiones . . . . . . . . . . . . . . . . . . . . 29
15
15
ELENA JURADO MÁLAGA
Σ1 = {a,b,c,...,z} Σ2 = {0,1}
Palabra vacı́a: es una palabra que no tiene ningún sı́mbolo y se representa como λ.
16
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
xi+j = xi xj
|xi | = i|x|
x0 = λ
L = L1 ∪ L2 = {x/x ∈ L1 ∨ x ∈ L2 }
Propiedades:
17
ELENA JURADO MÁLAGA
Conmutativa. L1 ∪ L2 = L2 ∪ L1
Idempotencia. L ∪ L = L
L = L1 L2 = {xy/x ∈ L1 ∧ y ∈ L2 }
Propiedades:
No es conmutativa.
Li+j = Li Lj
L0 = Lλ = {λ}
∞
�
L∗ = Li
i=0
18
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
Propiedades:
L∗ = L+ ∪ {λ}
L+ = L∗ L = LL∗
ω(Σ) = Σ∗
En este caso el alfabeto es considerado como un lenguaje, concretamente el
formado por todas las cadenas de longitud 1.
Σ+ = Σ∗ \ {λ}
19
ELENA JURADO MÁLAGA
x1 ::= y1
x2 ::= y2
P =
···
xn ::= yn
y v, w ∈ Σ∗ .
Decimos que v produce directamente a w, o que w deriva directamente de v, si
∃z, u ∈ Σ∗ y una producción xi ::= yi tal que v = zxi u y w = zyi u
La notación utilizada para representar una derivación directa es v → w
∗
La notación utilizada en este caso es v → w
20
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
Reglas gramaticales:
Aplicando la pr. 1 < sentencia >−→ < sujeto > < predicado >
∗
Aplicando la pr. 2 < sentencia >−→ < articulo >< nombre > < predicado >
∗
Aplicando la pr. 4 < sentencia >−→ < articulo > < nombre >< verbo >
∗
Aplicando la pr. 6 < sentencia >−→ la< nombre > < verbo >
∗
Aplicando la pr. 8 < sentencia >−→ la gata< verbo >
∗
Aplicando la pr. 9 < sentencia >−→ la gata corre
Sin embargo, la forma más habitual de representar este mismo proceso de gen-
eración de una cadena de sı́mbolos es mediante un árbol de derivaciones (o árbol
parser ) como el que se muestra en la figura 2.1.
21
ELENA JURADO MÁLAGA
<oracion>
<sujeto> <predicado>
la gata corre
1. < asignacion > ::= < variable > � =� < expresion >
2. < expresion > ::= < numero >
3. < expresion > ::= < variable >
4. < expresion > ::= < expresion > � +� < expresion >
5. < expresion > ::= < expresion > � ∗� < expresion >
Si consideramos que A, B y C pueden ser considerados como < variable > y que
2 y 4 pueden ser considerados como < numero >, es fácil comprobar que a partir
del sı́mbolo < asignacion > y utilizando diferentes producciones podemos llegar a
construir instrucciones como:
A=B+C
B=B*2
C=C+4
Sin embargo, no podrı́amos construir sentencias como A = + 2 * / + 4 o 4=A
Es decir, en los ejemplos anteriores podemos ver que hay construcciones grama-
ticalmente correctas y otras que no lo son.
22
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
S ∈ ΣN
ΣT ∩ ΣN = Ø
Σ = ΣT ∪ ΣN
Hasta este momento hemos distinguido los sı́mbolos no terminales de los termi-
nales encerrando a los primeros entre <>. Sin embargo, en los ejemplos que veremos
a partir de ahora y por simplicidad, utilizaremos las letras mayúsculas para repre-
sentar a los sı́mbolos no terminales y las minúsculas para los terminales. Además,
utilizaremos la notación BNF (Backus Normal Form). Con esta notación se utilizan
los sı́mbolos ::= para separar la parte izquierda de una producción de la derecha y
Manuales Uex
además, se emplea el sı́mbolo | para indicar que la parte izquierda de una producción
coincide con la de la anterior, ası́ no se repite la parte izquierda de determinadas
producciones. Por tanto, en el ejemplo anterior la descripción de las producciones
quedarı́a ası́:
23
ELENA JURADO MÁLAGA
< Numero >::=< Signo >< Digito >
< Signo >::= +
|−
< Digito >::=< Caracter >< Digito >
P = | < Caracter >
< Caracter >::= 0
|1
|···
|9
24
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
Sin embargo, es posible demostrar que cualquier lenguaje de tipo 0 puede ser tam-
bién generado por una gramática que pertenece a un grupo algo más restringido, las
gramáticas con estructura de frase. Podemos decir, por tanto, que las gr. de tipo 0 y
las gr. con estructura de frase tienen el mismo poder generativo.
Las producciones de las gramáticas con estructura de frase tienen la forma:
Es obvio que todas las gramáticas de tipo 1 son también gramáticas con estructura
de frase, pero en este caso hay una restricción añadida y es que la longitud de la parte
derecha de las producciones es siempre mayor o igual que la de la parte izquierda, es
decir, no hay producciones compresoras.
El nombre de gramáticas dependientes del contexto se debe a que las producciones
se pueden interpretar como que “A se convierte en v, siempre que se encuentre en
un determinado contexto, es decir, precedida por x y seguida por y”. Por lo tanto,
es necesario conocer el contexto en el que se encuentra A para poder aplicar la
producción.
A ::= v donde A ∈ ΣN v ∈ Σ∗
Manuales Uex
25
ELENA JURADO MÁLAGA
a) A ::= a
b) A ::= aV donde A, V ∈ ΣN , a ∈ ΣT
c) S ::= λ y S es el sı́mbolo inicial de la gramática.
a) A ::= a
b) A ::= V a donde A, V ∈ ΣN , a ∈ ΣT
c) S ::= λ y S es el sı́mbolo inicial de la gramática.
Cualquier lenguaje de tipo 3 puede ser generado tanto por una gramática lineal por la
derecha como por una lineal por la izquierda. Es decir, estos dos grupos de gramáticas
tienen el mismo poder generativo.
26
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
27
ELENA JURADO MÁLAGA
izquierda de una producción que tiene sólo sı́mbolos terminales o la cadena nula en
la parte derecha. Veamos el algoritmo:
Tanto las reglas innecesarias como los sı́mbolos no generativos o los inaccesibles
pueden eliminarse de cualquier gramática, ya que no aportan información relevante
a la misma.
Definición 2.12 (Gramática Limpia)
Decimos que una gramática es limpia si no tiene reglas innecesarias, ni sı́mbolos no
generativos, ni sı́mbolos inaccesibles.
Definición 2.13 (Reglas de redenominación)
Son reglas en las que hay un único sı́mbolo no terminal tanto en la parte izquierda
de la producción como en la derecha. Es decir, tienen la forma:
A ::= B, A, B ∈ ΣN
Para eliminar las reglas de redenominación de una gramática es necesario susti-
tuirlas por otras producciones que sean equivalentes.
Por ejemplo, si tenemos las producciones
A::=B
B::=x
B::=y donde x,y ∈ Σ∗
y deseamos eliminar A::=B, las producciones anteriores deben ser sustituidas por
las siguientes producciones:
A::=x
A::=y
B::=x
Manuales Uex
B::=y
Definición 2.14 (Reglas no generativas)
Son aquellas en las que sólo aparece λ en la parte derecha de la producción.
28
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
1. A = {a} B = {b}
2. A = {a} B = {b, λ}
3. A = {a, λ} B = {b, λ}
4. A = {a, λ} B = {b}
2.2 Dado el alfabeto Σ = {a, b}, y el lenguaje definido sobre él, L = {aa, bb} ¿cómo
son las palabras del lenguaje L4 ?
2.4 Dadas las siguientes gramáticas, indicar de qué tipo son y cómo es el lenguaje
que generan:
1. ΣT = {a, b, c, 0, 1} ΣN = {S}
S ::= a
|b
|c
|Sa
P =
|Sb
Manuales Uex
|Sc
|S0
|S1
29
ELENA JURADO MÁLAGA
2. ΣT = {a, b} ΣN = {S, A}
S ::= A
|λ
P =
A ::= aAb
|ab
3. ΣT = {a, b} ΣN = {S, A}
S ::= A
|λ
A ::= aA
P =
|Ab
|a
|b
4. ΣT = {a} ΣN = {S, A}
S ::= A
|λ
P =
A ::= AaA
|a
2.5 Dados los siguientes lenguajes, diseñar una gramática que los genere
1. L1 = {abn a/ n = 0, 1, . . .}
2. L2 = {am bn / m ≥ n ≥ 0}
3. L3 = {ak bm an / n = k + m}
4. L4 = {waw −1/ w es una cadena binaria definida en el alfabeto {0, 1}}
2.6 Dadas las siguientes gramáticas, obtener gramáticas equivalentes a ellas que
sean limpias y bien formadas
1. ΣT = {a, b} ΣN = {S, A, B, C, D, E}
S ::= Aa
|Ca
|a
B ::= Aa
P = |Ca
|a
Manuales Uex
C ::= Bb
D ::= Ca
E ::= Cb
30
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
2. ΣT = {x, y, z} ΣN = {S, P, Q}
S ::= zP zQz
P ::= xP x
P = |Q
Q ::= yP y
|λ
Manuales Uex
31
Tema 3
Contenido
+ representa la unión
33
33
ELENA JURADO MÁLAGA
Sólo son e.r. aquellas que puedan ser definidas utilizando los 6 puntos vistos ante-
riormente.
La prioridad de las operaciones, que puede modificarse utilizando paréntesis, es
de mayor a menor: ∗ . +
2. 0∗ 10∗ es una e.r. que representa a cualquier cadena binaria en la que hay un
solo 1, L = {0n 10m /n, m ≥ 0}
Sea Σ = {a, b, c}
1. Asociativa (α + β) + γ = α + (β + γ)
4. Idempotencia α+α=α
34
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
4. αØ = Ø
5. No es conmutativa
1. λ∗ = λ
2. Ø∗ = λ
3. α∗ α∗ = α∗
4. α∗ α = αα∗
5. (α∗ )∗ = α∗
6. α∗ = λ + αα∗
7. α∗ = λ + α + α2 + . . . + αn + αn+1 α∗
Si tenemos una función f : EΣn −→ EΣ (por ejemplo f (α, β) = α∗ β), donde EΣ
representa al conjunto de las expresiones regulares definidas sobre Σ, entonces:
1. A ::= a
Manuales Uex
2. A ::= aV donde A, V ∈ ΣN , a ∈ ΣT
35
ELENA JURADO MÁLAGA
3.4. Ejemplos
Supongamos que Σ1 = {a, b, . . . , z}
1. El lenguaje L1 = {λ, a, aa, aaa, . . .} puede representarse con la e.r. a∗ y puede
ser generado por la gr. lineal por la izquierda
P = {S ::= λ|Sa}
y por la gr. lineal por la derecha
P = {S ::= λ|aS}
2. El lenguaje de todas las palabras que empiezan por a puede representarse con
la e.r. a(a + b + . . . + z)∗ y puede ser generado por la gr. lineal por la izquierda
S ::= a
|Sa
P = |Sb
···
|Sz
y por la gr. lineal por la derecha
S ::= aA
A ::= aA
|bA
Manuales Uex
P =
···
|zA
|λ
36
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
3.4. EJEMPLOS 37
Los lenguajes regulares son especialmente adecuados para representar las carac-
terı́sticas léxicas de un lenguaje de programación, como veremos en los siguien-
tes ejemplos en los que consideraremos un lenguaje de programación similar a
C.
4. Las cadenas que pueden ser consideradas como un identificador del lenguaje
(nombres inventados por el programador para definir variables, funciones, etc.)
están formadas por letras (mayúsculas y minúsculas), dı́gitos y el guión bajo
( ), pero no pueden comenzar por un dı́gito. Este lenguaje definido sobre el
alfabeto Σ2 = {a, . . . , z, A, . . . , Z, 0, . . . , 9, } se puede representar por la e.r.
(a + . . . + z + A + . . . + Z + )(a + . . . + z + A + . . . + Z + + 0 + . . . + 9)∗
Esta e.r. representa palabras como Suma o T otal1 pero no representarı́a a 1Ab
Si trabajamos con el alfabeto Σ3 = {0, . . . , 9, .,+ , −, e, E} (el sı́mbolo de la suma
+ ha sido representado en un tamaño menor del habitual para distinguirlo con
claridad del operador unión (+))
37
ELENA JURADO MÁLAGA
3.5. Problemas
3.1 Describir los lenguajes representados por las siguientes expresiones regulares
definidas sobre el alfabeto Σ = {a, b, c}
1. (a + b)∗ c
2. (aa+ )(bb∗ )
3. (aa+ ) + (bb∗ )
4. a∗ b∗ c∗
3.3 Dadas las siguientes expresiones regulares escribir, para cada una de ellas, una
palabra que pertenezca al lenguaje que la expresión representa y otra que no pertenez-
ca a dicho lenguaje
1. (1∗ + 0∗ )(1∗ + 0∗ )(1∗ + 0∗ ) 3. 1∗ (0 + 10∗ )1∗
2. (1 + 0)∗ 10(1 + 0)∗ 4. 10∗ + 01∗
3.4 Simplificar las siguientes expresiones regulares
1. (a + b + ab + ba)∗ 3. a(a∗ a + a∗ ) + a∗
2. (a + λ)∗ 4. (a + b)∗ ba(a + b)∗ + a∗ b∗
3.5 Dadas dos expresiones regulares
α = 0 ∗ + 1∗ β = 01∗ + 10∗ + 1∗ 0 + (0∗ 1)∗
encontrar
1. una palabra que pertenezca a α pero no a β
2. una palabra que pertenezca a β pero no a α
Manuales Uex
38
Tema 4
Autómatas Finitos
Contenido
4.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.2. Definición de Autómata Finito Determinista . . . . . . . 40
4.3. Representación de Autómatas . . . . . . . . . . . . . . . . 40
4.4. Los AFD como reconocedores de lenguajes . . . . . . . . 43
4.5. Minimización de un AFD . . . . . . . . . . . . . . . . . . . 43
4.6. Autómatas Finitos No Deterministas(AFND) . . . . . . 47
4.7. Lenguaje aceptado por un AFND . . . . . . . . . . . . . . 50
4.8. Simulación de un AFD y AFND . . . . . . . . . . . . . . 51
4.9. Paso de un AFND a AFD . . . . . . . . . . . . . . . . . . 52
4.10. Relación entre AF, gr. y exp. reg. . . . . . . . . . . . . . 55
4.11. Lı́mites para los leng. regulares . . . . . . . . . . . . . . . 65
4.12. Problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.1. Introducción
Aunque no se puede considerar como una definición correcta de autómata, está muy
extendida una idea que confunde el concepto de autómata con el de robot. Por lo
tanto, se considera erróneamente que un autómata es una máquina que imita fun-
ciones tı́picas de los seres vivos, sobre todo relacionadas con el movimiento, pudiendo
Manuales Uex
39
39
ELENA JURADO MÁLAGA
AF D = (Σ, Q, f, q0 , F ), donde
Σ es el alfabeto de entrada
Q es el conjunto finito y no vacı́o de los estados del Autómata
f es la función de transición que indica en qué situaciones el Autómata pasa de
un estado a otro, se define f : Q × Σ −→ Q
q0 ∈ Q es el estado inicial
F ⊂ Q es el conjunto de estados finales de aceptación (F �= Ø)
40
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
a
a
p q
b b
r
a,b
ciones del autómata. Los estados finales de aceptación se identifican por estar ence-
rrados en un doble circulo. El estado inicial se destaca con una flecha arrugada.
Al analizar el autómata del ejemplo es evidente que sólo considera como cadenas
aceptadas aquellas que están formadas solamente por a’s. Cualquier cadena que con-
tenga una b hará que el autómata acabe en el estado r , que es un estado muerto.
Diremos que un estado está muerto si no es un estado final de aceptación y no parte
de él ninguna transición hacia otro estado. Es evidente que si durante el análisis de
una cadena se llega a un estado muerto, como ya no es posible salir de dicho estado,
la cadena no será aceptada por el autómata.
que no están definidas todas las transiciones. Las situaciones que no están definidas
deben ser consideradas como situaciones de error, es decir, si una cadena hace llegar
al autómata hasta una situación no definida, consideraremos que la cadena no ha
sido reconocida por dicho autómata.
41
ELENA JURADO MÁLAGA
a
p a
q p q
a,b
b a
b a
a,b
s
s
r
b
a
a
p q
b
a r
Manuales Uex
42
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
f (q, λ) = q ∀q ∈ Q
L = {x ∈ Σ∗ / f (q0 , x) ∈ F }
43
ELENA JURADO MÁLAGA
equivalentes entre sı́. Todos los estados que sean equivalentes entre sı́ se fundirán en un
único estado en el autómata resultante. Para conseguir este objetivo se construirá una
partición de Q, que se irá refinando paulatinamente, de manera que finalmente cada
elemento de la partición agrupará estados equivalentes. Inicialmente, se construye
una partición de Q formada por dos únicos elementos: los estados de aceptación y los
que no lo son. Dicha partición se irá refinando todo lo posible, separando en diferentes
elementos a los estados que no son equivalentes. Recordemos que una partición de Q
consiste en dividir Q en varios subconjuntos {Gi }1≤i≤n de tal forma que:
�
Gi ∩ Gj = Ø ∀i �= j y Gi = Q
1≤i≤n
G2 sı́mbolo a G2 sı́mbolo b
A → B ∈ G2 A → C ∈ G2
B → B ∈ G2 B → D ∈ G2
C → B ∈ G2 C → C ∈ G2
Manuales Uex
D → B ∈ G2 D → E ∈ G1
Analizando el comportamiento de los cuatro estados con el sı́mbolo b, es evidente
que D no es equivalente a los otros tres estados. Por tanto, es necesario dividir G2
en dos nuevos elementos.
44
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
b
C E
b
a
a
b
A
a
b
B D
a a
45
ELENA JURADO MÁLAGA
b G1
a
b
G’’2
a
b
G4 G3
b
a a
A veces es fácil comprobar de manera intuitiva si dos AFD son equivalentes, pero
esto no siempre ocurre. Un método para comprobar si dos AFD son equivalentes
consiste en unirlos de manera que formen un único AFD que, por supuesto, no es
conexo. Formalmente, la unión de los dos autómatas se llevarı́a a cabo ası́:
Sean A1 = {Σ, Q1 , f1 , q01 , F1 } A2 = {Σ, Q2 , f2 , q02 , F2 }
El autómata resultante tras la unión serı́a
A = A1 + A2 = {Σ, Q1 ∪ Q2 , f, q0 , F1 ∪ F2 } donde
�
f1 (q, a) si q ∈ Q1
f (q, a) =
f2 (q, a) si q ∈ Q2
El nuevo estado inicial q0 puede ser tanto q01 como q02 .
Una vez construido el autómata unión, éste se minimiza. Si al concluir el proceso
de minimización, los dos estados iniciales q01 y q02 forman parte del mismo elemento de
la partición, los autómatas originales son equivalentes y el AFD que hemos obtenido
es el autómata mı́nimo equivalente a ambos.
Ejemplo 4.4 Dados los autómatas de la figura 4.6, aplicaremos el método anterior
para decidir si son equivalentes o no.
Como hemos visto inicialmente, Partición = {G1 , G2 }
donde G1 = {q, r, w} G2 = {p, s, v, u}
Hay que comprobar cómo se comportan los elementos de G1 y G2 con los sı́mbolos
a y b.
Manuales Uex
G1 sı́mbolo a G1 sı́mbolo b
q → r ∈ G1 q → p ∈ G2
r → q ∈ G1 r → p ∈ G2
w → w ∈ G1 w → v ∈ G2
46
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
b
b
a
a a
p q v w
b b
a
a,b a b
a
b
s r u
Autómata 1 Autómata 2
G2 sı́mbolo a G2 sı́mbolo b
p → q ∈ G1 p → p ∈ G2
s → p ∈ G2 s → p ∈ G2
v → w ∈ G1 v → v ∈ G2
u → w ∈ G1 u → v ∈ G2
En principio, parece que los estados del elemento G1 son equivalentes, sin embargo,
analizando el comportamiento de los estados del elemento G2 con el sı́mbolo a, es
evidente que s no es equivalente a los otros tres estados. Por tanto, es necesario dividir
G2 en dos subgrupos.
Partición = {G1 , G�2 , G3 } G1 = {q, r, w} G�2 = {p, v, u} G3 = {s}
Veamos cómo se comporta G�2 con los sı́mbolos a y b.
G�2 sı́mbolo a G�2 sı́mbolo b
p → q ∈ G1 p → p ∈ G�2
v → w ∈ G1 v → v ∈ G�2
u → w ∈ G1 u → v ∈ G�2
�
Es evidente que todos los estados de G2 son equivalentes. Por tanto, no es posible
refinar más la partición. Podemos determinar que los Autómatas 1 y 2 son equiva-
lentes ya que los estados iniciales p y v son equivalentes. Además, el autómata que
se muestra en la figura 4.7 es equivalente a ambos y es mı́nimo.
Como el estado G3 es inaccesible se puede eliminar. Ası́ el autómata quedarı́a
como muestra la figura 4.8.
47
ELENA JURADO MÁLAGA
a
b
G’2 G1
a
a, b
G3
a
b
G’2 G1
a
T es una relación binaria definida sobre Q que indica las λ-transiciones del
autómata (si pT q ⇒ existe una λ-transición desde p hasta q)
48
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
a b λ
→ ∗p {q} Ø Ø
q {p, s} {r, p} {s}
r Ø {s, p} {r, s}
∗s Ø Ø {r}
a
p q
a,b
b a, λ b
s λ
r λ
λ,b
Es evidente que un AFD no es más que un caso particular de AFND, es decir, AFD
⊂ AFND. En realidad, un AFD es un AFND que cumple
T = Id y |f (q, a)| = 1 ∀q ∈ Q, ∀a ∈ Σ
p 0 0 0 0 0 0 0 0
q
0 0 0 1
(BT )2 = BT 2 = 0 0 1 0
BT =
r 0 0 1 1 0 0 1 1
s 0 0 1 0 0 0 1 1
49
ELENA JURADO MÁLAGA
0 0 0 0 1 0 0 0
0 0 1 1 0 1 1 1
BT 3 = BT 4 = ... =
0
B ∗ = BId + BT + BT 2 + BT 3 =
0 1 1 T 0 0 1 1
0 0 1 1 0 0 1 1
λ − clausura(q) = {p ∈ Q/qT ∗ p}
Esta definición se puede ampliar a conjuntos
� de estados de manera natural.
Si R ⊂ Q, entonces λ − clausura(R) = q∈R λ − clausura(q)
Aunque para calcular la λ-clausura de un estado se pueden utilizar las matrices
booleanas que acabamos de ver, a continuación se describe un algoritmo que también
nos permite calcular la λ-clausura.
50
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
f � (q, λ) = λ − clausura(q)
λ − clausura(R), siendo R ⊂ Q
Manuales Uex
51
ELENA JURADO MÁLAGA
1. Q� = 2Q
2. q0� = λ − clausura(q0 )
3. F � = {C ⊂ Q/C ∩ F �= Ø}
�
4. f � (C, a) = {C � ⊂ Q/C � = q∈C λ − clausura(f (q, a))}, siendo C ⊂ Q
El autómata que se obtiene por este método no tiene porqué ser mı́nimo y podrı́a
llegar a tener, como máximo, 2|Q| estados.
Manuales Uex
52
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
B b
a,b
A a λ D
λ
a
a
a
C E
b a,b
λ
53
ELENA JURADO MÁLAGA
q1
a a
a
q0 b
q3
b
b
a
b b q5
q2
a a
a,b
q6 q4
b
G1 sı́mbolo a G1 sı́mbolo b
q2 → q4 ∈ G1 q2 → q2 ∈ G1
q3 → q3 ∈ G1 q3 → q2 ∈ G1
q4 → q5 ∈ G1 q4 → q6 ∈ G1
q5 → q3 ∈ G1 q5 → q2 ∈ G1
q6 → q6 ∈ G1 q6 → q6 ∈ G1
G2 sı́mbolo a G2 sı́mbolo b
q0 → q1 ∈ G2 q0 → q2 ∈ G1
q1 → q3 ∈ G1 q1 → q2 ∈ G1
Todos los estados de G1 son equivalentes, sin embargo, esto no ocurre con los
de G2 , por lo que es necesario separarlos en dos elementos diferentes. La nueva y
definitiva partición serı́a:
Manuales Uex
54
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
a, b
b
G’2 G1
a
a, b
G3
Demostración:
55
ELENA JURADO MÁLAGA
Xi = Ø si F es inaccesible desde qi
necesario resolver el sistema completo ya que la única incógnita que nos interesa es
X0 (considerando que q0 es el estado inicial) que es la e.r. buscada.
56
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
b b
a
q0 q1
a
57
ELENA JURADO MÁLAGA
k
Ejemplo 4.8 Dado el siguiente AFD, calculamos las e.r. Rij
b
a
q1 q2
Las dos últimas columnas se han calculado mediante la fórmula recursiva vista
anteriormente.
0 ∗ 0
1
R11 0
= R11 0
+ R11 (R11 ) R11 = λ + λλ∗ λ = λ
R12 = R12 + R11 (R11 ) R12 = a + λλ∗ a = a
1 0 0 0 ∗ 0
0 ∗ 0
1
R21 0
= R21 0
+ R21 (R11 ) R11 = Ø + Øλ∗ λ = Ø
R22 = R22 + R21 (R11 ) R12 = (b + λ) + Øλ∗ a = b + λ
1 0 0 0 ∗ 0
1 ∗ 1
2
R11 1
= R11 1
+ R12 (R22 ) R21 = λ + a(b + λ)∗ Ø = λ
1 ∗ 1
2
R12 1
= R12 1
+ R12 (R22 ) R22 = a + a(b + λ)∗ (b + λ) = a + ab∗ = ab∗
1 ∗ 1
2
R21 1
= R21 1
+ R22 (R22 ) R21 = Ø + (b + λ)(b + λ)∗ Ø = Ø
1 ∗ 1
2
R22 1
= R22 1
+ R22 (R22 ) R22 = (b + λ) + (b + λ)(b + λ)∗ (b + λ) = b∗
Teniendo en cuenta que sólo hay un estado final de aceptación q2 , la e.r. que
estamos buscando será R12 2
= ab∗
Paso de expresión regular a AFND De la misma forma que las e.r. se definieron
Manuales Uex
de forma recursiva, este método para construir el AFND, que está basado en la
definición de las e.r., también puede considerarse recursivo. Para cada tipo de e.r.
construiremos un AFND, de esta manera diferentes autómatas pueden ensamblarse
para construir otro más complejo.
58
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
1 - e.r. = ∅
q1 qf
2 - e.r. = λ q1
3 – e.r. = a ∈ Σ a
q1 qf
Mα
q1 qf1 λ
λ
4 – e.r. = α + β q0 qf
λ
λ Mβ
q2 qf2
5 – e.r. = α β Mα λ Mβ
q1 qf1 q2 qf
Mα
q1 qf1
λ
6 – e.r. = α∗ λ
q0 λ
qf
En la figura anterior se detallan los esquemas asociados a cada una de las opera-
ciones que podemos encontrar en una e.r., Mα y Mβ representan a los autómatas que
reconocen a las e.r. α y β respectivamente.
59
ELENA JURADO MÁLAGA
( a + b ) * a b b #
1 2 3 4 5 6
Para cada una de las posiciones es necesario definir su conjunto siguiente que
estará formado por las posiciones que pueden seguir a una dada en cualquier pala-
bra que pertenezca al lenguaje representado por la e.r. Para calcular estos conjuntos
es necesario analizar cada una de las operaciones que intervienen en la e.r. y estu-
diar cómo afectan a las diferentes posiciones. Para este ejemplo, los valores de estos
conjuntos serı́an:
Cada estado de nuestro AFD será un conjunto de posiciones. Los estados finales
de aceptación serán aquellos que contienen a la posición asociada al sı́mbolo # (en el
ejemplo, la posición 6). Se calculan simultáneamente estos estados y las transiciones
correspondientes mediante el algoritmo 4.5. En este algoritmo hay que tener en cuenta
que simb(i) indica el sı́mbolo del alfabeto asociado a la posición i. En nuestro caso:
60
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
q1 a
q3
a
b a b
q0
b
b
q2
Manuales Uex
61
ELENA JURADO MÁLAGA
a
A ::= a A
P
A ::= aB a
A B
S ::= λ λ
S P
Manuales Uex
62
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
A
S ::= 1A 1
| 0B S 0
|1 1
P
A ::= 0S
| 1B 1
0
B ::= 0B
| 1B
B
0, 1
Paso de AFND a GLD En este caso debemos tener en cuenta las mismas rela-
ciones que hemos visto en el caso anterior. Sin embargo, las transiciones que llevan
a un estado final dan lugar a dos producciones diferentes como indica la siguiente
figura.
1
S A
0
S ::= 1A
| 1P S ::= 1A
1 |1
|1
A ::= 0S A ::= 0S
P
Paso de GLI a AFND Si trabajamos con GLI’s, debemos tener en cuenta que:
63
ELENA JURADO MÁLAGA
a
A ::= a P A
A ::= Ba a
B A
S ::= λ λ
P S
A 0
1
S ::= A0 P 1
| B1 S
A ::= S1
|1 0
0
B ::= S0 1
|0 B
Paso de AFND a GLI En este caso debemos tener en cuenta las mismas relaciones
que hemos visto en el caso anterior. Sin embargo, hay que tener en cuenta que puede
haber varios estados finales, en ese caso las transiciones que llevan a un estado final
dan lugar a dos producciones según se indica en el siguiente esquema.
64
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
1 1 F
0 B D
0
A 1 0
1 0
C E G
0
1 0
2. |uv| ≤ n
3. ∀i ≥ 0 ⇒ uv i w ∈ L
65
ELENA JURADO MÁLAGA
Ejemplo 4.13 Utilizaremos el lema del bombeo para demostrar que el lenguaje L =
{ak bk /k ≥ 0} no es regular. La demostración se realizará por el método de reducción
al absurdo. Es decir, supondremos que L es regular, si partiendo de esta hipótesis
llegamos a una situación absurda habremos comprobado que nuestra suposición inicial
era falsa.
Supongamos que L es regular y que n ≥ 0 es la constante asociada a L que
menciona el lema del bombeo. Evidentemente sea cual sea el valor de n siempre es
posible encontrar una palabra en L cuya longitud sea mayor que n, por ejemplo, sea
z = an bn , en este caso |z| = 2n > n. Veamos diferentes formas de dividir z en tres
partes:
1. z = uvw = a . . . |a . . . a| . . . ab . . . b
2. z = uvw = a . . . ab . . . |b . . . b| . . . b
3. z = uvw = a . . . |a . . . ab . . . b| . . . b
En el primer caso sólo se bombearı́an a’s con los que conseguirı́amos cadenas con
más a’s que b’s, que no pertenecerı́an a L. En el segundo caso ocurrirı́a lo contrario ya
que sólo bombearı́amos b’s. En el tercer caso bombeamos a’s y b’s simultáneamente,
por tanto serı́a posible obtener el mismo número de a’s que de b’s. Sin embargo,
las cadenas obtenidas contendrı́an subcadenas del tipo ababab o aabbaabbaabb, de
cualquier forma estas palabras nunca pertenecerı́an a L. No existe ninguna otra forma
de dividir la cadena en tres partes; por tanto, hemos comprobado que el lema no se
cumple y podemos asegurar que el lenguaje no es regular.
si xRy ⇒ ∀z ∈ X, x ◦ zRy ◦ z
Manuales Uex
66
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
1. L ⊂ Σ∗ es regular
xRL y ⇐⇒ ∀z ∈ Σ∗ xz ∈ L ⇔ yz ∈ L
Demostración.
Para demostrar este teorema comprobaremos en primer lugar que 1 ⇒ 2, después
que 2 ⇒ 3 y finalmente que 3 ⇒ 1.
67
ELENA JURADO MÁLAGA
xRL y ⇐⇒ ∀z ∈ Σ∗ xz ∈ L ⇔ yz ∈ L
Es evidente que RL es una relación de equivalencia. Veamos que es invariante por
la derecha:
xRL y =⇒ ∀z ∈ Σ∗ xz ∈ L ⇔ yz ∈ L
=⇒ ∀z, z � ∈ Σ∗ xzz � ∈ L ⇔ yzz � ∈ L
=⇒ ∀z ∈ Σ∗ xzRL yz
Comprobaremos a continuación que xRM y ⇒ xRL y. Si esto ocurre el número de
clases de equivalencia que genera RM será mayor o igual que el número de clases de
RL , lo que permitirá afirmar que RL es de ı́ndice finito.
�
si [xz] ⊆ L ⇒ xz ∈ L, yz ∈ L
xRM y =⇒ ∀z ∈ Σ∗ xzRM yz =⇒ como[xz] = [yz]
si [xz] � L ⇒ xz ∈
/ L, yz ∈
/L
=⇒ xz ∈ L ⇔ yz ∈ L =⇒ xzRL yz c.q.d.
68
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
0 0 0,1
1 1
q0 q1 q2
Es importante destacar que el estado q0 = [λ] = [0] representa a todas las cadenas
binarias que no tienen ningún 1, el estado q1 = [1] = [10] representa a las cadenas
binarias que tienen un solo 1 y, por tanto, pertenecen al lenguaje (por ese motivo es
el único estado final de aceptación), y el estado q2 = [11] representa a las cadenas
que tienen más de un 1. Es evidente que q0 , q1 y q2 o, lo que es lo mismo, las clases de
equivalencia [λ], [1] y [11] constituyen una partición del lenguaje universal (0 + 1)∗ .
69
ELENA JURADO MÁLAGA
4.12. Problemas
4.1 Minimizar el siguiente autómata
a b
→ q0 q1 q2
q1 q3 q2
q2 q4 q1
∗ q3 q4 q3
∗ q4 q3 q4
A
0 1
0,1
1 0
B
0 1
1 0 1
1
C
1 0,1
0 0 0
0
D 0,1
0 1
1 0 1 0,1
Manuales Uex
70
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
4.12. PROBLEMAS 71
a b λ 0 1
→ A {B, D} − − → A B C
B C − A B − D
∗ C − − − C E −
∗ D − A − ∗ D B −
∗ E − C
construir una GLD y una GLI, limpias y bien formadas, para generar los lenguajes
que reconocen dichos autómatas. Calcular las expresiones regulares que describen
dichos lenguajes utilizando el método del sistema de ecuaciones.
4.5 Utilizando el método de los conjuntos siguientes calcular el AFD que reconoce
a cada uno de los siguientes lenguajes:
1. ab∗ c + a∗ c∗
2. b∗ (a + bc)
3. a(bc)∗ + ab(cb)∗ cd
Manuales Uex
71
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
Tema 5
Contenido
5.7. Problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
En este tema se estudiarán las Gramáticas Independientes del Contexto (GIC), los
lenguajes que éstas definen, llamados lenguajes independientes del contexto (LIC),
y los autómatas que reconocen a estos últimos, los Autómatas de Pila (AP). Con-
siderando la jerarquı́a de Chomsky, también se les llama respectivamente gramáticas
y lenguajes de tipo 2. Estas gramáticas, igual que ocurre con las regulares, tienen una
gran importancia práctica en la definición de lenguajes de programación, ya que nos
permiten formalizar el concepto de sintaxis, de la misma forma que los Autómatas
Manuales Uex
73
73
ELENA JURADO MÁLAGA
A ::= v donde A ∈ ΣN , v ∈ Σ∗
En este tipo de gramáticas, la conversión de A en v se realiza independientemente
del contexto en el que se encuentre A, de ahı́ su nombre.
AP = {Q, Σ, f, Γ, q0 , z0 , F }
74
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
Γ es el alfabeto de la pila
q0 ∈ Q es el estado inicial
f : Q × (Σ ∪ λ) × Γ −→ P(Q × Γ∗ )
f (q, a, z) = {(p1 , ψ1 ), (p2 , ψ2 ), . . . , (pn , ψn )}
Estas transiciones indican que si el Autómata de Pila se encuentra en el estado
q, recibe como entrada el sı́mbolo a y z es el sı́mbolo que se encuentra en la
cima de la pila, el Autómata puede pasar al estado p1 y reemplazar en la pila el
carácter z por la cadena ψ1 , o bien elegir cualquiera de las otras posibilidades.
75
ELENA JURADO MÁLAGA
Ejemplo 5.1 Construiremos un Autómata de Pila con estados finales para el lengua-
je L = {0n 1n /n ≥ 0}, generado por la GIC S ::= 0S1|λ
La estrategia será la siguiente: mientras se procesan los primeros caracteres de
la cadena (que deberán ser 0’s), éstos se almacenan en la pila. Cuando se llega a
la segunda mitad de la cadena y comienzan a llegar 1’s, se pasa a otro estado cuya
misión será eliminar un 0 de la pila por cada 1 que se procese. Cuando se termine de
procesar la cadena, la pila deberá estar vacı́a (en realidad, sólo almacenará el sı́mbolo
inicial de la pila z0 ).
El AP se define: Q = {q0 , q1 , q2 } Σ = {0, 1} Γ = {z0 , 0} F = {q0 }
Y la función de transición se define de la siguiente forma:
En este caso el estado inicial también es estado final debido a que λ ∈ L. Cualquier
situación que no haya sido definida indicará un error. Por ejemplo, si la cadena
comienza con 1 el autómata detectará el error, nótese que la función de transición no
está definida para la situación (q0 , 1, z0 ).
S ::= 0S0
| 1S1
| 2
76
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
entender su significado. Por esa razón, en los mecanismos para reconocer lenguajes
independientes del contexto no es suficiente con indicar si una cadena determinada
pertenece o no al lenguaje, también es muy importante que el reconocedor construya
el árbol de derivación de dicha cadena.
77
ELENA JURADO MÁLAGA
Cada nodo interno del árbol será un sı́mbolo no terminal de la gramática mientras
que las hojas serán los sı́mbolos terminales. Una producción como A ::= X1 . . . Xn se
representará como un subárbol cuyo nodo padre es A siendo sus hijos los sı́mbolos
X1 , . . . , Xn .
Si en un paso de la construcción del árbol, se aplica una producción al sı́mbolo no
terminal que está situado más a la izquierda del árbol, se dice que es una derivación
por la izquierda. La misma definición se aplica a derivación por la derecha.
5.3.1. Ambigüedad.
Una gramática es ambigua cuando es posible construir dos o más árboles de
derivación diferentes para una misma palabra. El problema de la ambigüedad es muy
complejo ya que no existe ningún algoritmo que permita reconocer si una gramática
es o no ambigua y, en el caso de que lo sea, tampoco existe ningún algoritmo que
permita eliminar dicha ambigüedad (ni siquiera es posible eliminarla en todos los
casos). Los lenguajes independientes del contexto para los cuales todas las GIC que
los generan son ambiguas, se dice que tienen una ambigüedad inherente.
|/
Es fácil demostrar que esta gramática es ambigua construyendo dos árboles dife-
rentes para generar la misma expresión, concretamente id + cte * id
78
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
<expre> <expre>
id + cte * id id + cte * id
Para resolver este caso de ambigüedad hay que imponer una jerarquı́a entre los
operadores. Como suele ser habitual consideraremos que la multiplicación y la división
tienen una prioridad más alta que la suma y la resta. Si aparecen varias operaciones
con la misma prioridad se ejecutarán de izquierda a derecha, aunque en este caso el
resultado de la expresión siempre serı́a el mismo. Para definir la jerarquı́a se van a
introducir en la gramática nuevos sı́mbolos no terminales:
< termino > y < op − adt > estarán asociados a los operadores aditivos suma y
resta.
< f actor > y < op − mult > estarán asociados a los operadores multiplicación y
división.
ΣN = {< expre >, < termino >, < f actor >, < op − adt >, < op − mult >}
79
ELENA JURADO MÁLAGA
< expre >::=< expre >< op − adt >< termino >
| < termino >
< termino >::=< termino >< op − mult >< f actor >
| < f actor >
< f actor >::= (< expre >)
P = |id
|cte
< op − adt >::= +
|−
< op − mult >::= ∗
|/
Con esta nueva gramática, a la que llamaremos G Exp 1, la expresión anterior
tendrı́a un único árbol de derivación que se representa en la figura 5.2.
<expre>
<termino>
<termino> <op_mult> <factor>
<factor> <factor>
id + cte * id
80
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
81
ELENA JURADO MÁLAGA
Estas producciones se pueden sustituir por las siguientes, en las que ha sido
necesario añadir un nuevo sı́mbolo no terminal A� :
82
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
∗
INIC(w) = {a ∈ ΣT / w −→ aβ, β ∈ Σ∗ }
Método para calcular los Sı́mbolos Iniciales Hay que tener en cuenta las
siguientes consideraciones:
1. Si w comienza por un sı́mbolo terminal es trivial: w = aβ, a ∈ ΣT =⇒
INIC(w) = {a}
2. Si w comienza por un sı́mbolo no terminal, hay que considerar la posibilidad
de que el sı́mbolo por el que comienza sea anulable y aplicar esta consideración
reiteradamente. w = Xβ, X ∈ ΣN =⇒
Manuales Uex
�
INIC(X) ∪ INIC(β) si X es anulable
INIC(w) =
INIC(X) si X no es anulable
83
ELENA JURADO MÁLAGA
Una vez que han sido consideradas estas tres situaciones se obtiene una lista
provisional de sı́mbolos seguidores que es necesario ampliar con la segunda fase.
α ∈ Σ∗ =⇒ SEG(Y ) ⊂ SEG(X)
Situación E. Si hay una producción de la forma: Y ::= αXδ donde
δ ∈ Σ+ ∗
N es anulable y α ∈ Σ =⇒ SEG(Y ) ⊂ SEG(X)
84
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
Tras considerar las situaciones D y E con todas las producciones, se obtiene una
colección de relaciones de inclusión entre los conjuntos de sı́mbolos seguidores
previamente calculados. Si se consideran ordenadamente todas estas inclusiones,
tomando como punto de partida la lista provisional calculada en la fase 1, se
consigue la lista definitiva.
Si consideramos que el sı́mbolo $ aparece al final de cualquier cadena, hay que
tener en cuenta siempre que $ ∈ SEG(S)
Ejemplo 5.6 Los seguidores de los sı́mbolos no terminales para la gramática G Exp 2
son los siguientes:
Fase 1 Fase 2
E )$
E’ )$
T +- )$
T’ +-)$
F */ +-)$
A ( id cte
M ( id cte
Para llevar a cabo la segunda fase del método se han considerado las siguientes
relaciones de inclusión:
SEG(E) ⊂ SEG(E � ) ⊂ SEG(T ) ⊂ SEG(T � ) ⊂ SEG(F )
Gramáticas LL(1)
Una gramática será LL(1) si es posible construir para ella un reconocedor LL(1)
determinista. Para que esto ocurra es necesario que la consulta del siguiente sı́mbolo
85
ELENA JURADO MÁLAGA
Ejemplo 5.7 Los sı́mbolos directores para las producciones de la gramática G Exp 2
son los siguientes:
DIR1 = DIR(E ::= T E � ) = {(, cte, id}
DIR2 = DIR(E � ::= AT E � ) = {+, −}
DIR3 = DIR(E � ::= λ) = SEG(E � ) = {), $}
DIR4 = DIR(T ::= F T �) = {(, cte, id}
DIR5 = DIR(T � ::= MF T � ) = {∗, /}
DIR6 = DIR(T � ::= λ) = SEG(T � ) = {+, −, ), $}
DIR7 = DIR(F ::= (E)) = {(}
DIR8 = DIR(F ::= id) = {id}
DIR9 = DIR(F ::= cte) = {cte}
DIR10 = DIR(A ::= +) = {+}
DIR11 = DIR(A ::= −) = {−}
DIR12 = DIR(M ::= ∗) = {∗}
DIR13 = DIR(M ::= /) = {/}
Es fácil comprobar que es una gramática LL(1) ya que:
DIR2 ∩ DIR3 = ∅ DIR5 ∩ DIR6 = ∅ DIR7 ∩ DIR8 ∩ DIR9 = ∅
DIR10 ∩ DIR11 = ∅ DIR12 ∩ DIR13 = ∅
ΣN = {S, E, R}
ΣT = {i, t, a, e, b}
Los sı́mbolos gramaticales tienen el siguiente significado:
S = Sentencia E = Expresión R = Resto de la sentencia
86
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
Fase 1 Fase 2
S e$
R e$
E t
Son más potentes que los reconocedores LL(1). Es decir, el conjunto de los
Manuales Uex
Un analizador LR(1) detecta un error en una cadena tan pronto como sea
posible.
87
ELENA JURADO MÁLAGA
Los analizadores LR(1) también utilizan una pila en la que se van almacenando
los caracteres que se van procesando ası́ como los estados por los que el reconocedor
ha pasado.
Veamos con un sencillo ejemplo como funcionarı́a un reconocedor LR(1), conocien-
do su Tabla de Acciones. Posteriormente estudiaremos cómo construir dicha tabla.
$ a ( ) A
q0 D2 D3 D1
q1 R1
q2 R2
q3 D4
q4 D5
Manuales Uex
q5 R3
88
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
89
ELENA JURADO MÁLAGA
Desplazamiento Si Accion(qm , aj ) = Dr
La nueva configuración será: (q0 X1 q1 . . . Xm qm aj qr , aj+1 . . . an $)
Se añade a la pila el carácter procesado y el estado actual.
Determinación del núcleo de q0 . Para cada una de las producciones que tienen
al sı́mbolo inicial en la parte izquierda (S::=x), añadir al estado q0 el LR-item
[S::= .x, $]
Manuales Uex
90
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
Para la producción B::=z, hay que añadir el LR-item [B::= .z, u] donde
u = INIC(yw).
Ejemplo 5.10 Veamos cómo se crea la Tabla de Sı́mbolos para el ejemplo anterior:
2. Cerrar q0
q0 = {[S::=.A, $], [A::=.(a), $], [A::=.a, $]}
Analizando estos tres LR-items y los que se construyen después, es evidente
que:
Accion(q0 , A) = D1 Accion(q0 , () = D3 Accion(q0 , a) = D2
q5 = {[A::=BA., $]}
q6 = {[B::=aB., a, b, $]}
Analizando los LR-items de los estados se construye la siguiente tabla de acciones:
91
ELENA JURADO MÁLAGA
$ a b A B
q0 R3 D3 D4 D1 D2
q1 R1
q2 R3 D3 D4 D5 D2
q3 D3 D4 D6
q4 R5 R5 R5
q5 R2
q6 R4 R4 R4
Gramáticas LR(1)
Una gramática es LR(1) siempre que sea posible construir un reconocedor LR(1)
que sea determinista. Para que esto pueda ocurrir deben cumplirse las siguientes
condiciones:
1. La gramática debe ser aumentada, es decir, el sı́mbolo inicial no debe aparecer
nunca en la parte derecha de ninguna producción. Si no es ası́, basta con añadir
una producción como S’ ::= S, en la que S’ se convierte en el nuevo sı́mbolo
inicial de la gramática.
tado q hay dos items del siguiente tipo: [A ::= α.aβ, u1] y [B ::= γ.aδ, u2 ].
La acción asociada al estado q ante la llegada del sı́mbolo a podrı́a ser un
desplazamiento al estado que contiene al LR-item [A ::= αa.β, u1] o un
desplazamiento al que contiene a [B ::= γa.δ, u2 ].
92
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
Teorema 5.2
El conjunto de los LIC no está cerrado para la intersección ni para la comple-
mentación.
Manuales Uex
93
ELENA JURADO MÁLAGA
Teorema 5.3
Si L es un LIC y R es un Lenguaje regular, entonces L ∩ R es un LIC.
Teorema 5.4
El conjunto de los LIC está cerrado para las sustituciones y (como caso particular)
para los homomorfismos.
1. |vx| ≥ 1
Manuales Uex
2. |vwx| ≤ n
94
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
5.7. PROBLEMAS 95
5.7. Problemas
5.1 Construir un Autómata de Pila Vacı́a para los siguientes lenguajes definidos
sobre el alfabeto Σ = {a, b, c, 0, 1}
1. L1 = {a2n bn , n ≥ 0}
−
2. L2 = {awbw 1 c, w ∈ (0 + 1)∗ }
3. L3 = {ab∗ c}
4. L4 = {abn cdn , n ≥ 0}
5.2 Demuestra que cada una de las siguientes gramáticas de tipo 2 es ambigua y
encuentra otra gramática equivalente que no lo sea
1. S ::= A A ::= AA|a|b
5.3 Para cada una de las siguientes gramáticas de tipo 2 hay que comprobar si son
LL(1) y/o LR(1). Si lo son hay que construir el correspondiente reconocedor y si no
lo son hay que explicar el motivo
1. S ::= aA A ::= bA|λ
5.4 Utliza el lema del bombeo para demostrar que los siguientes lenguajes no son
independientes del contexto
1. L1 = {an bn cn , n ≥ 0}
2. L2 = {an bn cm , m ≥ n ≥ 0}
Manuales Uex
3. L3 = {an bm cn dm , n, m ≥ 0}
4. L4 = {an bn cm , n �= m n, m ≥ 0}
95
ELENA JURADO MÁLAGA
5. L5 = {an bn cm , 0 ≤ n ≤ m ≤ 2n}
5.5 Demuestra que la gramática que aparece en el ejemplo 5.8 (página 86) es am-
bigua y no es LR(1)
5.8 Diseña una gramática que genere paréntesis anidados y demuestra que es LR(1)
5.9 Modifica la siguiente gramática de manera que sea LL(1) y demuestra que real-
mente lo es
ΣN = {D, T, L} S=D ΣT = {entero, real, id, ,}
D ::= T L T ::= entero|real L ::= L, id|id
Manuales Uex
96
Tema 6
Gramáticas Atribuidas
Contenido
6.1. Concepto de Semántica y de Gramática Atribuida . . . 97
6.2. Atributos heredados y sintetizados . . . . . . . . . . . . . 99
6.3. Gramáticas S-atribuidas y L-Atribuidas . . . . . . . . . . 100
6.4. Problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
Hasta ahora hemos visto como las gramáticas regulares (tipo 3) son adecuadas
para representar las caracterı́sticas morfológicas de los elementos básicos de un lengua-
je de programación. Igualmente, las gramáticas independientes del contexto (tipo 2)
lo son para representar las caracterı́sticas sintácticas. Sin embargo, dichas gramáticas
no son lo suficientemente potentes como para representar los aspectos semánticos de
un lenguaje de programación. Veremos, a lo largo de este tema, cómo las gramáticas
atribuidas pueden ser útiles para realizar esta labor.
estático y dinámico.
La semántica estática se ocupa de las condiciones que deben cumplir las
construcciones de un programa para que su significado sea correcto.
97
97
ELENA JURADO MÁLAGA
G= {ΣT , ΣN , S, P }
98
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
Las funciones semánticas definen las relaciones que se cumplen entre los atributos
de los distintos sı́mbolos de la gramática. Estas relaciones permiten calcular los valores
de unos atributos en función de los valores de otros.
Cuando se desea describir las funciones semánticas asociadas a una producción,
éstas deben aparecen encerradas entre llaves al final o en algún punto intermedio
de la producción. Si un sı́mbolo aparece varias veces en la misma producción (por
ejemplo, en las producciones recursivas) se utilizan subı́ndices para distinguir unas
instancias de otras. El subı́ndice 0 se reserva para hacer referencia al sı́mbolo repetido
cuando éste aparece en la parte izquierda de la producción y los subı́ndices 1, 2, . . .
se utilizan en orden para las diferentes apariciones del sı́mbolo en la parte derecha
de la producción. Por ejemplo:
expr ::= expr + expr {expr0 .valor = expr1 .valor + expr2 .valor}
Esta producción indica que una expresión aritmética puede construirse como la
suma de otras dos expresiones más simples y, en este caso, la acción semántica indica
que el valor de la expresión resultante será la suma de las dos expresiones simples.
99
ELENA JURADO MÁLAGA
atributos heredados se calcula en función de los atributos de los nodos hermanos y/o
padre.
expr ::= expr ∗ expr {expr0 .valor = expr1 .valor ∗ expr2 .valor}
La figura 6.1 muestra el árbol de derivación de la expresión 9 + 7 * 5. Al mismo
tiempo que el árbol se construye de manera ascendente se calculan los atributos
100
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
expr.valor
44
expr
expr.valor
expr.valor 35
expr expr
9
expr.valor expr.valor
expr expr 5
7
num.valor num num num.valor num num.valor
9 7 5
9 + 7 * 5
A ::= x1 x2 . . . xn
Ejemplo 6.3 Veamos con un ejemplo abstracto cómo especificar claramente un frag-
mento de gramática L-atribuida. Supongamos que tenemos la producción
A ::= x y z
Manuales Uex
101
ELENA JURADO MÁLAGA
A ::= {x.x1 ↓ = f (A.a2 ↓)} x {y.y2 ↓= g(x.x1 ↓)} y z {A.a1 ↑= h(y.y2 ↓, z.z1 ↑)}
No podemos asociar a esta producción acciones semánticas que evalúen los atri-
butos a2 (por ser heredado se evaluará en una producción en la que el sı́mbolo A
esté ubicado en la parte derecha), y1 y z1 (por ser atributos sintetizados se deben
Manuales Uex
102
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
Los atributos de L y de ID son heredados, por eso los llamamos tipoh, el atributo
de T es sintetizado y se calcula en aquellas producciones que tienen a T en la parte
izquierda (la segunda y la tercera).
103
ELENA JURADO MÁLAGA
D
L.tipoh
T.tipo T L 0 2
1 0 L.tipoh id.tipoh
int L , id 0 9
3 0
c
L.tipoh id.tipoh
L , id 10 añadir_tabla(c,0)
4 0 7 0
id b
id.tipoh
8 añadir_tabla(b,0)
5 0 a
6 añadir_tabla (a,0)
6.4. Problemas
6.1 Dada la siguiente gramática atribuida:
ΣT = {id, cte, =, +} ΣN = {asig, expr} S = asig
1. asig ::= id = expr {id.valor = expr.valor}
2. expr ::= id {expr.valor = id.valor}
3. |cte {expr.valor = cte.valor}
4. |expr + expr {expr0 .valor = expr1 .valor + expr2 .valor}
¿Es esta gramática S-atribuida o L-atribuida?
Manuales Uex
104
Tema 7
Máquinas de Turing
Contenido
7.1. Introducción. Antecedentes históricos . . . . . . . . . . . 105
7.2. Definición y ejemplos de M.T.’s . . . . . . . . . . . . . . . 107
7.3. Restricciones a la M.T. . . . . . . . . . . . . . . . . . . . . 110
7.4. Modificaciones de la M.T. . . . . . . . . . . . . . . . . . . 113
7.5. Técnicas para la construcción de M.T. . . . . . . . . . . . 116
7.6. La M.T. Universal . . . . . . . . . . . . . . . . . . . . . . . 118
7.7. La M.T. como generadora de lenguajes . . . . . . . . . . 119
7.8. La tesis de Church-Turing . . . . . . . . . . . . . . . . . . 120
7.9. Problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
La máquina de Turing es un dispositivo teórico muy simple pero con una gran
capacidad computacional, es decir, permite resolver problemas de una gran compleji-
dad. Como veremos en los próximos temas, la máquina de Turing es una herramienta
formal muy útil para estudiar la teorı́a de la computabilidad.
A finales del siglo XIX, la recién nacida Teorı́a de Conjuntos habı́a causado un
gran impacto entre los matemáticos. Sin embargo, algunos pensadores como Bertrand
Russell opinaban que dicha teorı́a no estaba bien formalizada ya que permitı́a enun-
ciados tan paradójicos como éste:
105
105
ELENA JURADO MÁLAGA
106
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
1. Cambia de estado.
107
ELENA JURADO MÁLAGA
a
↑p
MT = {Q, Σ, Γ, f, q0 , b, F }
Γ es el alfabeto de la cinta
q0 ∈ Q es el estado inicial
f : Q × Γ −→ Q × Γ × {I, D}
108
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
L(MT ) = {w ∈ Σ∗ / q0 w −→
∗
α1 pα2 donde p ∈ F α1 , α2 ∈ Γ∗ }
0 1 b
q0 q0 1D q0 0D q1 bI
Ejemplo 7.2 (Paridad) Esta M.T. calcula la paridad del número de 1’s que hay en
la cadena binaria de entrada. Al final del proceso, se añade a la derecha de la cadena
un 0 para indicar que hay un número par de 1’s y un 1 para indicar que el número
de 1’s es impar.
Q = {q0 , q1 , q2 } F = {q2 } Σ = {0, 1} Γ = {0, 1, b}
La función de transición se define en la siguiente tabla:
0 1 b
q0 q0 0D q1 1D q2 0I
q1 q1 0D q0 1D q2 1I
Ejemplo 7.3 (Duplicar) Esta M.T. recibe una cadena formada por 1’s en la cinta
de entrada y duplica su tamaño. El proceso comienza en el extremo derecho de
la cadena. Para llevar a cabo este trabajo, cada vez que encuentra un 1 lo marca
sustituyéndolo por un 0 y se desplaza hasta el final de la cadena donde añade otro
Manuales Uex
109
ELENA JURADO MÁLAGA
1 0 b
q0 q1 0D q0 0I q2 bD
q1 q1 1D q1 0D q0 0I
q2 q2 1D q3 bI
Ejemplo 7.4 (Imagen especular) Esta M.T. construye la imagen especular de un
número binario. Es decir, si recibe la cadena de entrada 100 al acabar el proceso la
información que hay en la cinta es 100001. Esta máquina es similar a la anterior con
la diferencia de que, en este caso, hay que duplicar dos tipos de sı́mbolos (0 y 1) en
lugar de uno. También en este caso los dı́gitos se procesarán de derecha a izquierda.
Los 0’s y 1’s son reemplazados por A’s y B’s respectivamente cada vez que se procesan
(duplican). Al final del proceso, en el estado q3 se reconstruye la cadena cambiando
las A’s y B’s por 0’s y 1’s.
Q = {q0 , q1 , q2 , q3 , q4 } F = {q4 } Σ = {0, 1} Γ = {0, 1, A, B, b}
La función de transición se define en la siguiente tabla:
0 1 A B b
q0 q1 AD q2 BD q0 AI q0 BI q3 bD
q1 q1 AD q1 BD q0 AI
q2 q2 AD q2 BD q0 BI
q3 q3 0D q3 1D q4 bI
Ejemplo 7.5 (Paréntesis anidados) Esta M.T. reconoce cadenas de paréntesis
anidados. Las parejas de paréntesis que se van procesado se marcan convirtiéndolos
en *. En este caso se dispone de dos estado finales f1 y f2 que indican respectiva-
mente si la cadena inicial es o no correcta, además, a pesar de ser algo redundante se
escribe en la cinta la letra ’S’ o ’N’ (si o no). Al final del proceso no se reconstruye la
información inicial que, por tanto, se pierde. Esta máquina puede reconocer cadenas
como éstas: ((())) o (()()) pero no reconocerı́a (()))(.
Q = {q0 , q1 , q2 , q3 , f1 , f2 } F = {f1 , f2 } Σ = {(, )} Γ = {(, ), ∗, S, N, b}
La función de transición se define en la siguiente tabla:
( ) * b
q0 q0 (D q1 ∗ I q0 ∗ D q2 bI marca un ) y pasa a q1
q1 q0 ∗ D q1 ∗ I f2 ND marca un ( y pasa a q0
q2 q3 ∗ I q2 ∗ I f1 SD al final, comprueba que no quedan (
q3 q3 ∗ I q3 ∗ I f2 ND se llega a q3 si hay más ( que )
110
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
111
ELENA JURADO MÁLAGA
-2 -1 1 2
Es posible construir una M.T. equivalente Z � cuya cinta tendrá la siguiente es-
tructura:
∗
0 1 -1 2 -2
En Z � existe una nueva casilla, numerada con el 0, que contiene un sı́mbolo nuevo
(∗). Además de añadir esta nueva casilla, se ha redistribuido la información de Z,
de manera que cada casilla de Z � contiene la misma información que su correspon-
diente casilla de Z (la que tiene la misma numeración). Veamos con un ejemplo el
funcionamiento de Z � .
Supongamos que f (p, x) = (q, y, D) es una de las transiciones de Z y supongamos
que x está almacenado en la casilla n(n > 0), después de realizar el cambio de
sı́mbolo hay que desplazarse a la casilla n + 1 (que ahora está situada dos posiciones
a la derecha de n). En la máquina Z � está transición se desglosarı́a en las siguientes:
f � (p, x) = (pD , y, D)
f � (pD , ?) = (q, ?, D) ? es un comodı́n que representa a cualquier sı́mbolo
El comportamiento de Z � serı́a diferente si la casilla ocupada por x fuera la eti-
quetada con −n ya que un desplazamiento a la derecha en Z supone un doble de-
splazamiento hacia la izquierda en Z � . La transición anterior se desglosarı́a en:
f � (p, x) = (p�D , y, I)
f � (p�D , ?) = (q, ?, I)
Si la posición ocupada por x fuera la -1, habrı́a que añadir una transición al pasar
por la posición 0. f � (q, ∗) = (q, ∗, D)
En general, la nueva máquina tiene un número de estados 6 veces mayor que Z
ya que cada estado q de Z se multiplica por 3 (q, qI , qD ) en la parte positiva de la
cinta y otro tanto ocurre con la parte negativa de la cinta (q � , qI� , qD
�
).
112
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
0 1 b
[q0 , b] [q1 , 0]0D [q1 , 1]1D
[q1 , 0] [q1 , 0]1D [q1 , b]0P este estado indica que la cadena comienza por 0
Manuales Uex
[q1 , 1] [q1 , 1]0D [q1 , b]0P este estado indica que la cadena comienza por 1
Es evidente que no se aumenta la potencia computacional del modelo ya que
simplemente se ha utilizado una notación diferente para designar a los estados.
113
ELENA JURADO MÁLAGA
114
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
Bj
∗
Ck
∗
115
ELENA JURADO MÁLAGA
una celda que contiene al sı́mbolo a o al sı́mbolo b. En este segundo caso, habrı́a que
añadir las siguientes transiciones:
f (q1 , a) = (p2 , a, P )
f (q1 , b) = (p2 , b, P )
116
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
a� M2
El esquema M1 indica que si al acabar el proceso, M1 está señalando
b� M3
a una celda que contiene el sı́mbolo a, la máquina M2 debe continuar el proceso, pero
si la casilla contiene el sı́mbolo b, será M3 la máquina que continuará trabajando. En
otro caso el proceso finaliza. Para materializar esta situación habrı́a que añadir las
transiciones:
f (q1 , a) = (p2 , a, P )
f (q1 , b) = (p3 , b, P )
f (q1 , x) = (f, x, P ) ∀x ∈ Γ\{a, b} donde f es un nuevo estado final.
Ejemplo 7.7 (Multiplicar) Este ejemplo servirá para ilustrar la utilización de una
M.T. como subrutina de otra. Se construirá una M.T. que multiplique números en-
teros, que se representan como cadenas de 1’s. Por ejemplo, un 4 se representa como
1111. Se utiliza el 0 como separador entre los datos iniciales. La M.T. se diseñará de
manera que si la entrada es 1m 01n 0 la salida deberá ser 1n×m . Básicamente, la M.T.
copiará al final de la cadena el segundo bloque de 1’s (1n ) tantas veces como 1’s haya
en el primer bloque (1m ), los 1’s de este primer bloque se van borrando (es una forma
sencilla de marcarlos).
En primer lugar, se diseña una M.T., llamada COPIAR que copia al final de la
cadena de entrada n 1’s. Es decir, si la situación inicial de la M.T. se describe
ası́ 1m 0q1 1n 01i, la situación final será 1m 0q5 1n 01i+n . Los 1’s (del segundo bloque)
que se van copiando se marcan cambiándolos temporalmente por un 2, y además se
procesan de izquierda a derecha.
La función de transición de COPIAR se define en la siguiente tabla, además q1 y q5
son respectivamente los estados inicial y final:
0 1 2 b
q1 q4 0I q2 2D cambia un 1 por un 2 y pasa a q2
q2 q2 0D q2 1D q3 1I se desplaza al extr. derecho y añade un 1
q3 q3 0I q3 1I q1 2D se desplaza hacia la izq. buscando un 2
q4 q5 0D q4 1I cambia los 2’s por 1’s
Cuando se han borrado todos los 1’s del primer dato se borran también los del segundo
ası́ como los 0’s que actúan de separadores de manera que finalmente en la cinta sólo
queda el resultado de la operación (1n×m ). En este caso los estados inicial y final son
q0 y q12 .
117
ELENA JURADO MÁLAGA
0 1 b
q0 q6 bD elimina un 1 del primer dato
q5 q7 1I
q6 q1 0D q6 1D llama a COPIAR
q7 q8 0I
q8 q9 1I q10 bD
q9 q9 1I q0 bD retrocede al extr. izq. para volver a empezar
q10 q11 bD borra un 0
q11 q12 bD q11 bD borra el segundo dato y un 0
Los sı́mbolos < y > permiten delimitar los diferentes bloques que constituyen esta
cadena. El primer bloque(dd . . . ∗ . . . d) representa el contenido de la cinta de la M.T.
M, y el asterisco se coloca inmediatamente a la izquierda del sı́mbolo al que apunta
la cabeza de lectura/escritura. Esta información va cambiando a lo largo del proceso
Manuales Uex
118
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
Es evidente que este tipo de M.T.’s sólo para en el caso de que el lenguaje a
generar sea finito, por tanto, la máquina descrita en el ejemplo anterior no pararı́a
nunca.
Para los lenguajes de tipo 0, que se estudian con más detalle en el próximo tema,
siempre es posible construir una M.T. que los genere. Como veremos, dentro de este
Manuales Uex
119
ELENA JURADO MÁLAGA
generada en la posición n.
3. Se han propuesto otros modelos teóricos de cómputo, que siempre son equiva-
lentes al de las M.T.’s
7.9. Problemas
7.1 Construir una M.T. que reciba como entrada dos cadenas de 1’s separadas por
el sı́mbolo � y que compruebe si tienen la misma longitud.
Manuales Uex
7.2 Construir una M.T. con tres pistas que reciba dos números binarios y que in-
dique cuál de los dos es mayor. Consideraremos que los datos están almacenados en
las dos primeras pistas y alineados a la derecha, es decir, los bits menos significativos
de ambos están situados en la misma columna. En la tercera pista se escribirá una
120
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
7.3 Construir una M.T. con tres pistas que sume dos números binarios. Considera-
remos que los datos están almacenados en las dos primeras pistas y alineados a la
derecha. El resultado se escribirá en la tercera pista que inicialmente está vacı́a.
7.4 Construir una M.T. para reconocer cada uno de los siguientes lenguajes
L1 = {0n 1n , n ∈ N}
L3 = {wcw �/ w, w � ∈ (a + b)∗ w �= w � }
Manuales Uex
121
Tema 8
Gramáticas de tipo 0 y 1
Contenido
Este capı́tulo se dedica al estudio de las gramáticas menos restrictivas, las de tipo
0 y las de tipo 1. Los autómatas que reconocen estas gramáticas son las Máquinas de
Turing (estudiadas en el capı́tulo anterior) y los Autómatas Linealmente Acotados
respectivamente. La diferencia principal entre ambos autómatas está en el tamaño
de la cinta que utilizan. Mientras que la Máquina de Turing dispone de una cinta
teóricamente infinita, los Autómatas Linealmente Acotados utilizan una cinta finita,
aunque su longitud pueda ser tan grande como sea necesario en cada caso.
terminal.
Este conjunto de gramáticas es equivalente al de gramáticas con estructura de
frase, cuya definición es algo más restringida. Las producciones de las gramáticas con
estructura de frase son de la forma:
123
123
ELENA JURADO MÁLAGA
Este grupo de lenguajes incluye a algunos para los que no es posible saber si una
palabra no pertenece al lenguaje. Si L es uno de estos lenguajes, cualquier Máquina
de Turing que lo reconozca no parará cuando reciba como entrada algunas palabras
que no pertenecen a L. En este caso, si w ∈ L sabemos que la M.T. parará, pero si
124
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
Teorema 8.1
1. L es recusivo ⇐⇒ L y L son recursivamente enumerables
2. L es recursivo ⇐⇒ L es recursivo
125
ELENA JURADO MÁLAGA
una nueva máquina M que permita reconocer a las palabras de L1 ∪L2 . Además
esta máquina pararı́a siempre.
126
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
Manuales Uex
127
128 TEMA 8. GRAMÁTICAS DE TIPO 0 Y 1
Tema 9
Computabilidad y Máquinas de
Turing
Contenido
9.1. Funciones calculables . . . . . . . . . . . . . . . . . . . . . 129
9.2. Funciones recursivas . . . . . . . . . . . . . . . . . . . . . . 131
9.3. Problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
129
129
ELENA JURADO MÁLAGA
1. f1 (n1 , n2 ) = n1 + n2 es calculable
fL : Σ∗ −→ N �
1 si w ∈ L
w −→ fL (w) =
0 si w ∈
/L
La función caracterı́stica de un lenguaje determina si una palabra pertenece o no
pertenece a dicho lenguaje. También es posible definir una función que sólo indique
si una palabra pertenece a un lenguaje, dicha función no estarı́a definida en todo el
dominio y se comportarı́a de la siguiente forma:
fL� : Σ∗ −→ N
w −→ fL� (w) = 1 si w ∈ L
Considerando estas definiciones, podemos afirmar que:
Manuales Uex
130
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
MT = {p0 , p1 , . . . , pn , . . .}
A partir de dicha lista de máquinas, podrı́amos definir la siguiente función:
f : N −→ N �
0 si pn no para con el dato n
n −→ f (n) =
k + 1 si pn para con el dato n y devuelve el valor k
Si suponemos que f es calculable, existe una Máquina de Turing que realiza el
mismo trabajo que f . Consideremos que pr sea esta máquina.
Si f (r) = 0 ⇒ pr no para con la entrada r
Si f (r) �= 0 ⇒ f (r) = k + 1 donde k es el resultado que devuelve la máquina pr
En cualquiera de los dos casos, la situación que se produce es absurda ya que f y
pr no tienen el mismo comportamiento, por lo tanto, la suposición inicial es falsa y
f no es una función calculable.
El conjunto L1 = {n ∈ N/ pn no para si recibe como dato a n} no es recursi-
vamente enumerable y además, el conjunto L2 = L1 es recursivamente enumerable
pero no es recursivo. Veamos, a continuación, como justificar estas afirmaciones. En
la sección 8.3 quedó demostrado que L1 no es un lenguaje recursivamente enume-
rable, ya que es imposible construir una M.T. que lo reconozca. Por otra parte,
L2 = {n ∈ N/ pn para si recibe como dato a n} es un lenguaje recursivamente enu-
merable porque la Máquina de Turing Universal permite saber si un número pertenece
a L2 y, por tanto, puede reconocer los elementos de L2 , sin embargo no es recursivo
ya que su complementario L2 = L1 no es recursivamente enumerable (teorema 8.1).
131
ELENA JURADO MÁLAGA
132
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
A continuación veremos dos reglas que nos permitirán construir funciones más
complejas a partir de las básicas.
αi : Nn −→ N β : Nm −→ N
φ(0, x1 , . . . , xn ) = α(x1 , . . . , xn )
φ(0) = k
Definición 9.6
Decimos que una función es recursiva primitiva si se puede definir a partir de las
funciones básicas mediante cero o más aplicaciones de las reglas de composición y de
recursión primitiva.
Aunque el número de funciones recursivas primitivas es muy amplio, existen al-
gunas funciones recursivas que no son primitivas. Un ejemplo es la función de Acker-
mann, que se define de la siguiente forma:
A(0, x) = x + 1
A(n + 1, 0) = A(n, 1)
A(n + 1, x + 1) = A(n, A(n + 1, x))
Manuales Uex
Por este motivo debemos incluir otra regla para la generación de funciones recur-
sivas que nos permitirá ampliar su número, de esta manera llegamos a la definición
de función µ-recursiva.
133
ELENA JURADO MÁLAGA
En otras palabras, φ hace corresponder a cada entrada x el menor entero que cumple
que α(x, y) = 0.
9.3. Problemas
9.1 Define recursivamente las siguientes funciones:
2. L2 = {0n 1n /n ≥ 0}
134
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
2. La función predecesor,
�
x−1 x>1
P (x) =
0 x=0
3. La función suma
4. La función producto
8. La función signo,
�
1 x>0
sg(x) =
0 x=0
Manuales Uex
135
Tema 10
Introducción a la Complejidad
Computacional
Contenido
De entre todos los problemas que pueden plantearse, el conjunto de aquellos que
son computables, es decir, que pueden ser resueltos aplicando un algoritmo, es muy
pequeño. Sin embargo, no todos los problemas computables son factibles en la realidad
por requerir a veces demasiados recursos, ya sean de espacio de memoria o de tiempo.
La teorı́a de la complejidad algorı́tmica es la encargada de definir los criterios básicos
para saber si un problema computable es factible, dicho de otro modo, si existe un
algoritmo eficiente para su resolución y en este caso cuál es su grado de eficiencia.
considerar intratables debido a la gran cantidad de tiempo y memoria que son ne-
cesarios para resolverlos. En esta sección introduciremos una terminologı́a que nos
permitirá analizar preguntas como ¿cuánto tiempo tardaremos en resolver un proble-
ma?
137
137
ELENA JURADO MÁLAGA
138
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
aceptados por Máquinas de Turing no deterministas con esa misma complejidad es-
pacial se llama ESPACION(S(n)). Estas clases se conocen como clases de complejidad
espacial.
Teorema 10.2
Sean S1 , S2 y S funciones de N en N. Supongamos que S1 (n) ≤ S2 (n), para todo n ∈
N, y que c > 0. Entonces se cumple:
3. ESPACIOD(S(n)) ⊆ ESPACION(S(n))
4. ESPACIOD(S(n)) = ESPACIOD(cS(n))
5. ESPACION(S(n)) ⊆ ESPACIOD(S(n)2 )
Teorema 10.3
Sean T1 , T2 y T funciones de N en N. Supongamos que T1 (n) ≤ T2 (n), para todo n ∈
N . Entonces se cumple:
3. TIEMPOD(T(n)) ⊆ TIEMPON(T(n))
139
ELENA JURADO MÁLAGA
Teorema 10.4
Si L ∈ TIEMPOD(f(n)) entonces, L ∈ ESPACIOD(f(n))
Las funciones S(n) y T(n) que hemos utilizado no tienen porque ser una función
exacta, sino sólo un indicador de la forma de variación del espacio o del tiempo
ocupado, en función de la longitud de la entrada de datos. Habitualmente nos interesa
poder comparar estas funciones con otras (habitualmente más simples) de manera que
las tasas de crecimiento sean análogas.
Veamos a continuación la notación que se utiliza para comparar tasas de creci-
miento.
Definición 10.5
Sean dos funciones f, g : N → R. Se dice que:
140
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
141
ELENA JURADO MÁLAGA
los puntos?. Un algoritmo determinista para resolver el problema es muy costoso, sin
embargo dada una posible solución, resulta muy sencillo comprobar que es válida.
En este terreno el problema principal que podemos plantearnos es el siguiente: ¿es
el conjunto NP igual al conjunto P? Este es el llamado problema P-NP, y todavı́a
no tiene solución. Es evidente que P ⊂ NP, pero para poder demostrar que la igualdad
se cumple habrı́a que demostrar que todo problema NP es también P, es decir, habrı́a
que encontrar una forma de transformar una Máquina de Turing no determinista con
cota temporal polinómica en una Máquina de Turing determinista con cota temporal
también polinómica. Por otro lado, tampoco se ha podido demostrar la desigualdad
entre los dos conjuntos, para ello habrı́a que encontrar un lenguaje que pertenezca a
NP y que no pertenezca a P.
Dentro de la clase NP hay un cierto número de problemas que pueden catalogarse
entre los más duros, en el siguiente sentido: si se encontrase un algoritmo de tiempo
polinómico para cualquiera de ellos habrı́a un algoritmo de tiempo polinómico para
todo problema en NP. Se dice que cualquier problema de esta categorı́a es NP-
completo.
Definición 10.7
Se dice que un lenguaje L1 es reducible en tiempo polinómico a un lenguaje L2 si hay
una función f computable en tiempo polinómico para la cual f(u) ∈ L2 sii u ∈ L1 .
Se utiliza la notación <p para indicar que L1 es reducible en tiempo polinómico
a L2 . Observar que si L1 <p L2 entonces determinar si w ∈ L1 no es más difı́cil
que determinar si f(w) ∈ L2 . Basándonos en la misma idea podemos decir que un
problema es reducible en tiempo polinómico a otro.
Definición 10.8 (Problemas NP-completos)
Un problema P ∈ NP es NP-completo si todos los demás problemas de la clase NP
se pueden reducir a él en tiempo polinómico.
Esta clase de problemas es importante porque si pudiéramos encontrar una solu-
ción en tiempo polinómico en una máquina de Turing determinista para un solo
problema NP-completo habrı́amos demostrado que P=NP.
142
Apéndice A
Generadores automáticos de
analizadores léxicos y sintácticos
Contenido
143
143
ELENA JURADO MÁLAGA
nombre fichero es el nombre del fichero que contiene la especificación del anali-
zador léxico en Lex. Por claridad, se recomienda que el nombre de estos ficheros
tenga extensión .l. Por defecto se generará un fichero con el mismo nombre y con
extensión .c. Por ejemplo, si el fichero de entrada se llama ejemplo.l, el de salida se
llamará ejemplo.c.
Se pueden utilizar las siguientes opciones a la hora de ejecutar PCLEX:
-c el fichero de salida tiene el nombre yylex.c
-C<nom fichero> el fichero de salida tiene el nombre que indica
<nom fichero>
-h muestra una pantalla de ayuda
-i construye un analizador insensible a la diferencia
mayúsculas/minúsculas
-n suprime las directivas “#line” en el fichero de salida
-p<nom fichero> utiliza <nom fichero> como fichero esqueleto para cons-
truir el fichero de salida, en lugar de utilizar el fichero
por defecto
-s suprime la regla por defecto, es decir, las entradas que
no encajen con ninguna regla provocan la salida del pro-
grama con el mensaje : pclex scanner jammed
Los demás programas anteriormente mencionados se utilizan de forma similar
aunque el significado de las opciones puede variar.
144
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
zona de definiciones
%%
zona de reglas
%%
procedimientos del programador
Zona de reglas Cada regla está formada por una expresión regular seguida por
una serie de acciones (codificadas en C) que serán las que el analizador léxico ejecute
cuando encuentre una cadena de caracteres que encaje con la expresión regular. Por
ejemplo:
ab* {printf("hola");}
void main() {
Manuales Uex
yylex();
}
yylex es el procedimiento que actúa como analizador léxico y cuyo código C es
generado a partir de las especificaciones que aparecen en la zona de reglas. El
145
ELENA JURADO MÁLAGA
programa principal puede ser mucho más complejo e incluir todos los procedimientos
que se deseen.
Podemos utilizar los corchetes para representar la unión entre varios sı́mbolos
y el guión para representar un rango de valores:
[a-z] representa a cualquier letra minúscula
[Ff][Oo][Rr] representa a la palabra for escrita utilizando letras
mayúsculas o minúsculas (serı́a la manera de representar
palabras reservadas en un lenguaje como Pascal)
La barra vertical (|) representa la unión entre expresiones regulares. Por ejem-
plo:
ab|cd representa a la cadena ab o a la cadena cd
146
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
Prioridades Los operadores que hemos visto tienen diferentes prioridades. Apare-
cen listados a continuación, de mayor a menor prioridad:
() paréntesis
[] unión entre sı́mbolos
*+?{} repeticiones
ee concatenación
| unión de expr. regulares
ˆ$ indicadores de contexto
yytext es una variable de tipo cadena de caracteres y almacena la cadena que acaba
de ser analizada por el scanner.
yyin, yyout son los nombres de los ficheros de entrada y de salida del analizador
léxico.
REJECT hace que el scanner analice por segunda vez la misma cadena. En este
segundo análisis, la regla que contiene a REJECT no será tenida en cuenta.
147
ELENA JURADO MÁLAGA
%s nombre1 nombre2 . . .
Para activarlas se utilizará la acción BEGIN(nombre) y para desactivarlas BEGIN(0).
Se utilizan colocando su nombre, encerrado entre los sı́mbolos <>, delante de una
regla. Por ejemplo:
<nombre>ab* ECHO;
Esta regla sólo se tendrá en cuenta si la condición nombre está activa.
A.1.6. Acciones
Cuando el analizador léxico encuentra una cadena de caracteres que encaja con
alguna de las expresiones regulares definidas, ejecuta las acciones asociadas a esta
expresión. Estás acciones pueden ser las predefinidas ECHO o REJECT, o cualquier
Manuales Uex
148
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
ab acción1
ab+ acción2
Teniendo en cuenta el ejemplo anterior, si en el fichero de entrada está incluida
la cadena abb se ejecutará la acción2, ya que la primera regla solo validarı́a 2
caracteres y la segunda validarı́a 3.
En el caso de que dos reglas diferentes validen cadenas de la misma longitud, se
elegirá la que aparezca en primer lugar. Por ejemplo, si la cadena hola aparece
en el fichero de entrada y se han definido las dos reglas siguientes:
hola acción1
[a-z]+ acción2
Se ejecutará la acción1 simplemente porque está escrita en primer lugar.
hubiera.
La función yyparse(), llama repetidamente al analizador léxico yylex() que
convierte cadenas de caracteres del fichero de entrada en sı́mbolos terminales de la
gramática (llamados tokens). Utilizando una terminologı́a anglosajona, al analizador
149
ELENA JURADO MÁLAGA
150
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
151
ELENA JURADO MÁLAGA
En el caso de los sı́mbolos terminales, esto mismo se puede definir con %token.
Por ejemplo:
%token <num> NUMERO
%token <cadena> IDENTIFICADOR
152
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
Manuales Uex
153
154 APÉNDICE A. GENERACIÓN AUTOMÁTICA DE ANALIZADORES
Bibliografı́a
[9] Aho A.V. y Sethi R. y Ullman J.D. Compilers: Principles, Techniques and Tools.
Addison Wesley, 1986.
155
155
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
Índice alfabético
Cierre
de Kleene, 18 Gödel, 6, 106
positivo, 19 Gramática, 6, 22
Compilador, 10 bien formada, 29
156
157
ELENA JURADO MÁLAGA
Intérprete, 10 Sı́mbolo
Inversa de una palabra, 17 inaccesible, 27
no generativo, 27
Lenguaje, 6, 16 director
universal, 16 de una producción, 85
recursivamente enumerable, 124 del LR-item, 89
recursivo, 125 inicial
Lex, 143 de una cadena, 83
LR-item, 89 de una gramática, 22
seguidor, 84
Máquina de Turing, 107
Semántica, 97
universal, 118
Shannon, 7
Myhill-Nerode, teorema, 66
Sustitución, 94
Palabra, 16
Tabla
vacı́a, 16
de acciones, 88, 89
anulable, 83
de sı́mbolos, 13
Potencia
Turing, 6, 105
de un lenguaje, 18
Manuales Uex
158