lenguajes formales

“Teor´ de Aut´matas y Lenguajes
ıa
o
Formales”
(para Ingenieros Inform´ticos)
a

Domingo G´mez & Luis M. Pardo
o

January 19, 2012

2

3

Pr´logo
o
Lo que sigue son una evoluci´n de notas comenzadas a impartir en el curso 2007/08,
o
para la asignatura “Teor´ de Aut´matas y Lenguajes Formales”. La evoluci´n de
ıa
o
o
los contenidos ha sido siempre en funci´n de lasdiversas promociones, su formaci´n
o
o
previa y su capacidad de adquirir nuevos conocimientos. Estos apuntes representan
una versi´n definitiva de nuestra experiencia. Nuestro cuidado ha sido conseguir una
o
adquisici´n de conocimientos te´ricos, su aplicaci´n con una formaci´n de car´cter
o
o
o
o
a
matem´tico para que el alumno desarrolle una actitud rigurosa ante problemas de
a
´sta yotras materias.
e
Este aspecto es de gran importancia en una materia como los aut´matas y los
o
lenguajes formales, considerados como uno de los fundamentos de las ciencias de
computaci´n. Dada la escasa formaci´n previa en matem´ticas de los alumnos que
o
o
a
llegan a la Univerisdad espa˜ola, se ha pretendido mantener el m´ximo de formaln
a
ismo en definiciones y enunciados perorenunciando a las demostraciones en t´rminos
e
formales completos, y limitando ´stas a aquellos casos en los que la prueba se basa
e
en la existencia de un algoritmo. El objetivo del curso es que el alumno comprenda,
aplique y asimile una serie de herramientas matem´ticas que se han desarrollado
a
para la teor´ de aut´matas y lenguajes formales.
ıa
o
Estos apuntes est´n tambi´n pensados para“aprender a resolver problemas ala
e
gor´
ıtimicamente”. Seg´n nuestro punto de vista, la mejor forma para conseguir
u
este objetivo es a trav´s de adquirir experiencia en la resoluci´n de problemas a
e
o
trav´s de algoritmos definidos con precisi´n.
e
o
Nuestro planteamiento es constructivo. Estos apuntes est´n dirigidos a futuros ina
genieros, por lo que intentaremos que los algoritmospresentados sean eficientes y
adecuados para implementaci´n (al menos en los casos en que ´sto sea posible) en
o
e
un programa inform´tico.
a
La teor´ de la computaci´n es un ´rea abstracta de la ingenier´ inform´tica. Por
ıa
o
a
ıa
a
ello incluimos ejemplos, cuestiones y problemas que van de preguntas triviales hasta
retos que requerir´n utilizar lo aprendido con sencillos argumentossemi–formales.
a
Los autores han utilizado este libro para una asignatura cuatrimestral, y su objetivo
ha sido que los alumnos conocieran los lenguajes regulares y los libres de contexto.
A partir de ellos, pudieran generar aut´matas que reconocieran estos lenguajes y los
o
algoritmos que permiten pasar de aut´matas a gram´ticas y viceversa. La ultima
a
a
´
parte trata sobre dos clases delenguajes especiales “LL” y “LR”. Estos lenguajes
tienen una importancia especial en el An´lisis Sint´ctico, como parte preliminar del
a
a
poceso de compilaci´n.
o
Las referencias bibliogr´ficas tampoco pretenden ser exhaustivas, aunque s´ cona
ı
tienen lo esencial de la literatura en estos temas.

4

Contents
1 Jerarqu´ de Chomsky
ıa
1.1 Introducci´n . . . . . . . . . . . . . . . . . .. . . . . . . .
o
1.2 Lenguajes Formales y Monoides . . . . . . . . . . . . . . .
1.2.1 - . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.2 Operaciones Elementales con Lenguajes . . . . . .
1.2.3 Sistemas de Transici´n . . . . . . . . . . . . . . . .
o
1.3 Gram´ticas Formales . . . . . . . . . . . . . . . . . . . . .
a
1.3.1 Sistema de Transici´n Asociado a una Gram´tica.
oa
1.3.2 Otras Notaciones para las Producciones. . . . . . .
1.3.2.1 Notaci´n BNF. . . . . . . . . . . . . . . .
o
1.3.2.2 Notaci´n EBNF. . . . . . . . . . . . . . .
o
1.4 Jerarqu´ de Chomsky . . . . . . . . . . . . . . . . . . . .
ıa
1.5 Disgresi´n: Problemas de Palabra . . . . . . . . . . . . . .
o

.
.
.
.
.
.
.
.
.
.
.
.

9
9
13
14
15
16
16
17
18
18
18...