Procesadores De Lenguajes 1

Procesadores del Lenguaje I
Antonio Falc´o
2
´Indice general
I Preliminares 5
1. Alfabetos y Lenguajes 7
1.1. Cadenas y Lenguajes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2. Operaciones con lenguajes . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
II Aut ´omatas y Lenguajes 17
2. Lenguajes Regulares 19
2.1. Aut ´omatas Finitos . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . 20
2.1.1. Definici ´on formal de un aut ´omata finito . . . . . . . . . . . . . . . 21
2.1.2. Definici ´on formal de computaci ´on . . . . . . . . . . . . . . . . . . 23
2.1.3. Las operaciones regulares . . . . . . . . . . . . . . . . . . . . . . . 23
2.2. Aut ´omatas no deterministas . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2.1. Definici´on formal del un Aut ´omata Finito no Determinista . . . . 26
2.2.2. Equivalencia entre AFNs y AFDs . . . . . . . . . . . . . . . . . . . 28
2.2.3. La propiedad de clausura bajo operaciones regulares . . . . . . . 30
2.3. Expresiones Regulares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.3.1. Definici ´on formal de una expresi ´on regular . . . . . . . . . . . . . 34
2.3.2. Laequivalencia con los Aut ´omatas Finitos . . . . . . . . . . . . . 34
2.4. Lenguajes no regulares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.4.1. El Lema del Bombeo para Lenguajes Regulares . . . . . . . . . . . 41
3. Lenguajes Libres del Contexto 47
3.1. Gram´aticas Libres del Contexto . . . . . . . . . . . . . . . . . . . . . . . . 47
3.1.1. Definicici ´on formal de unaGram´atica Libre del Contexto . . . . . 48
3.1.2. Gram´aticas sin s´ımbolos in´utiles . . . . . . . . . . . . . . . . . . . 49
3.1.3. Dise ˜no de Gram´aticas Libres del Contexto . . . . . . . . . . . . . 50
3.1.4. Ambiguedad en las Gram´aticas . . . . . . . . . . . . . . . . . . . . 51
3.1.5. La Forma Normal de Chomsky . . . . . . . . . . . . . . . . . . . . 51
3.2. Aut ´omatas a Pila . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.2.1. Definici ´on formal de un Aut ´omata a Pila . . . . . . . . . . . . . . 53
3.2.2. Equivalencia con las Gram´aticas Libres del Contexto . . . . . . . 54
3
´INDICE GENERAL
3.3. Lenguajes No Libres del Contexto . . . . . . . . . . . . . . . . . . . . . . 59
3.3.1. El Lema del bombeo para Lenguajes Libres del Contexto . . . . .59
4
Parte I
Preliminares
5

Cap´ıtulo 1
Alfabetos y Lenguajes
El objetivo de esta primera parte es el introducir la notaci ´on formal b´asica absolutamente
necesaria para la compresi ´on del resto de temas.
1.1. Cadenas y Lenguajes
Las cadenas de caracteres, tambi´en llamadas palabras, son la piedra angular en la
Ciencia de la Computaci ´on. El alfabeto sobre el cual las cadenas opalabras se definen
puede variar con respecto a la aplicaci ´on que se est´e tratando. Para nuestros prop´ositos
definiremos un alfabeto como un conjunto finito de s´ımbolos que denotaremos
usualmente por letras griegas may´usculas como  o .
Ejemplo 1. 1 = {0, 1}.
2 = {a, b, c, d, e, f, g, h, i, j, k, l,m, n, o, p, q, r, s, t, u, v,w, x, y, z}.
= {0, 1, x, y, z}.
N´otese que, puesto que unalfabeto es simplemente un conjunto finito no vac´ıo,
dados dos alfabetos 1 y 2 se tiene:
1. 1 ∪ 2 = {a|a ∈ 1 o a ∈ 2} es un alfabeto.
2. 1 ∩ 2 = {a|a ∈ 1 y a ∈ 2} es un alfabeto si es distinto del conjunto vac´ıo.
3. 1 \ 2 = {a|a ∈ 1 y a /∈ 2} es un alfabeto si es distinto del conjunto vac´ıo.
4. 2 \ 1 = {a|a ∈ 2 y a /∈ 1} es un alfabeto si es distinto del conjunto vac´ıo.Una cadena o palabra sobre un alfabeto es una sucesi ´on finita de s´ımbolos sobre
ese alfabeto, usualmente escritos uno al lado de otros sin ning´un tipo de separaci ´on.
Si consideramos 01001 esta es una cadena para los alfabetos 1 y . Del mismo modo
abracadabra es una cadena del alfabeto 2.
7
CAP´ITULO 1. ALFABETOS Y LENGUAJES
Si w es una cadena en el alfabeto,  la longitud de w...