• Author / Uploaded
• Diego Perez

• Categories
• Conjunto (Matemáticas)
• Infinito
• Cadena (Ciencias de la Computación)
• Función (Matemáticas)
• Lógica matemática

Citation preview

Elena Gaudioso Vázquez Tomás García Saiz

INTRODUCCION A LA TEORÍA DE AUTÓMATAS, GRAMÁTICAS T Y LENGUAJES

1

ELENA GAUDIOSO VÁZQUEZ TOMÁS GARCIA SAIZ

INTRODUCCIÓN A LA TEORÍA DE AUTÓMATAS, GRAMÁTICAS Y LENGUAJES

Editorial Universitaria Ramón Ateces

UnED

Las imágenes mostradas han sido tomadas y tratadas por los autores del presente libro. El icono de las cajas de trabajo, ha sido diseñada por Madebyoliver de Flaticon www.flaticon.com Reservados todos los derechos. Ni la totalidad ni parte de ese libro puede reproducirse o transmitirse por ningún procedimiento electrónico o mecánico, incluyendo fotocopia, grabación magnética o cualquier almacenamiento de información y sistema de recuperación, sin permiso escrito de Editorial Centro de Estudios Ramón Areces, S. A. Diríjase a CEDRO (Centro Español de Derechos Reprográficos, www.conlicencia. com) si necesita fotocopiar o escanear algún fragmento de esta obra.

© EDITORIAL CENTRO DE ESTUDIOS RAMÓN ARECES, S.A. Tomás Bretón, 21 - 28045 Madrid Teléfono: 915.061.190 Fax: 914.681.952 Correo: [email protected] Web: www.cerasa.es ISBN-13: 978-84-9961-285-0 Depósito legal: M-23463-2017 Impreso por: Campillo Nevado, S.A. Antonio González Porras, 35-37 28019 MADRID Impreso en España i Printed in Spain

Indice

1. Conceptos previos 1.1. Conceptos fundamentales de la teoría de c o n ju n to s.................................... 1.2. Conceptos fundamentales de la teoría de autóm atas.................................... 1.3. E jercicio s.......................................................................................................

1 1 4 9

2. Autómatas finitos 2.1. Autómatas fin ito s........................................................................................... 2.2. Elementos de un autómata f in ito ................................................................... 2.3. Definición formal de autómata finito determ inista....................................... 2.4. Representaciones de los autómatas finitos deterministas.............................. 2.4.1. Diagrama de transiciones................................................................... 2.4.2. Tabla de transiciones......................................................................... 2.5. El lenguaje de un autómata finito determinista............................................. 2.6. Ejemplos de lenguajes re g u la re s................................................................... 2.7. Autómatas finitos no deterministas................................................................ 2.8. Equivalencia entre autómatas finitos deterministasy no deterministas . . . . 2.9. E jercicios.......................................................................................................

11 11 12 14 16 16 17 18 19 21 23 26

3. Gramáticas regulares 3.1. Definición de gramática............................................................... 3.2. Tipos de gramáticas: gramáticas reg u lares................................................... 3.3. Ejemplos de gramáticas regulares ................................................ 3.4. Gramáticas regulares y autómatas finitos...................................................... 3.5. E jercicio s.......................................................................................................

31 31 34 36 38 42

VII

VIII

I ndice

4. Expresiones regulares 4.1. Introducción.................................................................................................... 4.2. Definición de las expresiones regulares.......................................................... 4.3. Lenguaje representado por una expresión r e g u la r ........................................ 4.4. Autómatas finitos y expresiones re g u la res.................................................... 4.5. Propiedades de las operaciones de las expresiones regulares........................ 4.6. E jercicio s.......................................................................................................

45 45 46 47 50 56 57

5. Propiedades de los lenguajes regulares y lenguajes no regulares 5.1. Propiedades de los lenguajes regulares.......................................................... 5.1.1. Unión de lenguajes regulares............................................................. 5.1.2. Complementario de un lenguaje re g u la r.......................................... 5.1.3. Intersección de dos lenguajes re g u la re s.......................................... 5.1.4. Concatenación de dos lenguajes regulares........................................ 5.1.5. Estrella de Kleene de un lenguaje re g u la r ....................................... 5.2. Introducción a los lenguajes no regulares....................................................... 5.3. Introducción a la jerarquía de C h o m sk y ....................................................... 5.4. E jercicios.......................................................................................................

59 59 60 63 64 67 70 72 76 76

6. Lenguajes y gramáticas independientes del contexto 6.1. Definición de las gramáticas independientes del co n tex to ........................... 6.2. Derivaciones en las gramáticas independientes del contexto........................ 6.3. Lenguaje de una gramática independiente del contexto .............................. 6.4. Introducción a los árboles de derivación....................................................... 6.5. Forma Normal de Chomsky............................................................................ 6.6. Transformación a Forma Normal de Chom sky.............................................. 6.7. E jercicios.......................................................................................................

81 81 85 87 88 90 92 99

7. Autómatas a pila 7.1. Introducción a los autómatas a p i l a ......................................................... 7.2. Definición formal de un autómata a p i l a ....................................................... 7.3. Lenguajes aceptados por los autómatas a p i l a ............................................. 7.4. Autómatas a pila y gramáticas independientes del co n tex to ........................ 7.5. Autómatas a pila deterministas...................................................................... 7.6. E jercicios.......................................................................................................

103 103 105 110 114 117 120

8. Propiedades de los lenguajes independientes del contexto 8.1. El lema de bombeo para lenguajes independientes del contexto.................. 8.2. Los lenguajes independientes del contexto en la jerarquía de Chomsky . . .

123 123 125

INDICE

8.3. Propiedades de los lenguajes independientes del contexto........................... 8.4. E jercicios.......................................................................................................

IX

127 129

9. Introducción a las máquinas de Hiring 9.1. Límites de la com putación........................................................................... 9.2. Definición de una máquina de Turing............................................................ 9.3. Descripciones instantáneas............................................................................ 9.4. Diagramas de transiciones para las máquinas de T u rin g .............................. 9.5. El lenguaje de una máquina de Turing: lenguajes recursivamente enumerables 9.6. Extensiones de la máquina de Turing b á s ic a ................................................ 9.7. Lenguajes recursivamente enumerables en la jerarquía de Chomsky . . . . 9.8. E jercicios.......................................................................................................

133 133 134 137 139 140 146 147 147

10. Ejercicios de autoevaluación

149

11. Solución a los ejercicios 11.1. Capítulo 1 ....................................................................................................... 11.2. Capítulo 2 ....................................................................................................... 11.3. Capítulo 3 ....................................................................................................... 11.4. Capítulo 4 ....................................................................................................... 11.5. Capítulo 5 ....................................................................................................... 11.6. Capítulo 6 ....................................................................................................... 11.7. Capítulo 7 ....................................................................................................... 11.8. Capítulo 8 ....................................................................................................... 11.9. Capítulo 9 .......................................................................................................

181 181 182 185 187 190 198 205 209 215

Prólogo

El objetivo del presente texto es proporcionar una introducción a la materia de las máquinas de estado o autómatas y los diferentes tipos de lenguajes formales que reconocen. La teoría de autómatas es un área fundamental en el campo de las Ciencias de la Computación. Se ocupa del estudio de las máquinas de estados finitos y permite establecer el límite computacional de los ordenadores esto es, qué es capaz de computar una máquina actual y con qué complejidad. Las máquinas vistas en este texto, sirven de base para la construcción de compiladores, en concreto de los módulos que se encargan de los análisis léxico y sintáctico. Esta materia se proporciona en la asignatura de primero de grado de Ingeniería Informática de la Universidad Nacional de Educación a Distancia. Es por ello, que este es un libro especialmente diseñado para la enseñanza a distancia. Por tanto, para cada capítulo, se incluyen recomendaciones al estudio y una serie de pequeños ejercicios a realizar para afianzar conocimientos. Con el objetivo de animar al lector a realizar estos ejercicios, la solución de los mismos se incluye al final del texto. Para poder dar una visión completa del temario adaptándolo a un alumno de primero de grado, se han evitado, en la manera de lo posible, las demostraciones formales. Aquel lector interesado en profundizar los contenidos presentados en el presente texto, puede utilizar las siguientes dos referencias que sirven como material complementario: [Hopcroft et al., 2008] y [Brookshear, 1993]. Así mismo, los capítulos se han organizado con la idea de seguir una planificación concreta durante un cuatrimestre. Así, cada capítulo se correspondería con una o a lo sumo dos semanas de estudio. Los autores

XI

Capítulo 1_____

Conceptos previos A lo largo del texto, se verán los lenguajes como conjuntos de cadenas que acepta una determinada máquina teórica. Por ello, se hará uso de conceptos básicos de teoría de conjuntos. Para ayudar al lector a recordar dichos conceptos, se ha introducido en este capítulo alguno de los conceptos más relevantes que se utilizarán a lo largo del texto. Así mismo, y a modo de glosario, se incluye una presentación de los conceptos fundamentales de la materia de autómatas, gramáticas y lenguajes.

1.1.

Conceptos fundamentales de la teoría de conjuntos

■ Conjunto Un conjunto es una colección de objetos que se denominan elementos o miembros. Normalmente, los elementos de un conjunto se representan separados por comas y encerrados entre corchetes ({ y }). Se dice que un conjunto es finito cuando contiene un número finito de elementos. Algunos ejemplos de conjuntos finitos son: • El conjunto de letras vocales del alfabeto: V = {n, e, i, o. • El conjunto de días de la semana: S = {lunes, martes, miércoles, jueves, viernes}. • El conjunto formado por los números menores de 100: N = { 1 ,2 ,3 ,..., 97,98,99,100}. Se dice que un conjunto es infinito cuando contiene un número infinito de elementos. Algunos ejemplos de conjuntos infinitos son: 1

2

Co n c e p t o s

fundamentales

de

la

teoría

de

conjuntos

• El conjunto de números naturales: ÍV = { 1 ,2 ,3 ,...} . P = {1,3 ,5 ,7

• El conjunto de números primos: • El conjunto formado por los números mayores de 100: M = 101 102 103 104

{ , , , ,...}.

La cardinalidad de un conjunto determina el tamaño de dicho conjunto, esto es, el número de elementos que contiene. Se representa mediante dos líneas verticales, así, si se considera el conjunto finito V = {a ,e ,i,o ,u }, entonces su cardinalidad se representa de la siguiente manera: |V| = 5. ■ Conjunto vacío El conjunto vacío es aquel que no contiene ningún elemento. El conjunto vacío se representa mediante el siguiente símbolo: 0. ■ Pertenencia

Se dice que un elemento pertenece a un conjunto cuando cumple las condiciones que lo definen. El operador de pertenencia se representa mediante el símbolo € y en el ejemplo del conjunto V = {a, e, i,o, u}, se cumple que a E ■ Subconjunto Se dice que A es un subconjunto áe, B (A C. B), si todos los elementos A pertenecen también al conjunto B. Esto es, para todo elemento se cumple que tu E B. El conjunto A es un subconjunto propio de Bs i C no pertenecen a A. En este caso se representa la relación entre los dos conjuntos de la siguiente forma: Ac .Por ejemplo, dados los conjuntos: B A = {a,b,c,d}

C = {c, d}D= { e ,/

B ={c, d}

B es un subconjunto propio de

A: B c A.

■ Igualdad y desigualdad entre conjuntos Dos conjuntos A y B son iguales (

A = B) si se cumple q

Dos conjuntos Ay B ,son diferentes ( pertenecen a B y viceversa. Esto es, existen tu E A tales que w ^ B y existen z 6 tales que z £ A. Así, siguiendo el ejemplo anterior, se cumple que:

=

y

CONC E P T O S

3

PREVIOS

■ Conjunto potencia Dado un conjunto A, el conjunto potencia P{A) es la colección de todos los subconjuntos que se pueden formar con los elementos de A. Por tanto, los elementos del conjunto potencia son a su vez conjuntos. Por ejemplo, considerando el conjunto A = {a, 6, c) entonces el conjunto potencia de A es: P{A) = {{a}, {6}, {c}, {a, 6}, {a, c}, {£>, c), {a, b, c}}. Dado un conjunto A, la cardinalidad de su conjunto potencia se define: P(A) = donde |^4| es la cardinalidad del conjunto A. El conjunto potencia de un conjunto infinito es un conjunto incontable. ■ Operaciones entre conjuntos Las principales operaciones entre conjuntos que se van a considerar son: - Unión La unión de dos conjuntos A y B, representada por todos los elementos que se encuentran en o en A U B = {x : x E A

o x e

U

es la colección de

B}

Por ejemplo, dados los conjuntos: A = {a,b,c,d} B = {c1d} entonces: A U B = {a,b, c,d} B U C = {c,d} = B = C

C = {D = {e

C 'J D —{ c ,d ,e,/} - Intersección La intersección de dos conjuntos A y B, representada por n es la colección de objetos que son elementos tanto de A como de B. Por consiguiente: AC\ B = {x \ x E A y x E B }

A = {a,

Por ejemplo, dados los conjuntos í 4 í1 B

= { íi , c }

- Diferencia La diferencia entre dos conjuntos Ay B se represe el conjunto que resulta de eliminar del conjunto A los elementos del conjunto B. Por ejemplo, dados los conjuntos A = {a, c} {d, e}, entonces:

4

Co n c e p t o s

fundamentales

de

la

teoría

de

a u t ó ma t a s

A - B = {6} C - D = {a,b}

El conjunto A — sBe denomina conjunto complemento de B con respecto En ocasiones, se da por sentado que los elementos de todos los conjuntos considerados, pertenecen a un conjunto universal de mayor tamaño. En estos casos, el complemento de un conjunto X con relación a este conjunto universal, recibe el nombre de complemento de X . Por ejemplo, si se considera el conjunto universal como el conjunto de números naturales, entonces el complemento del conjunto de números naturales pares, será el conjunto formado por todos los números naturales impares. — Producto cartesiano El producto cartesiano de dos conjuntos A y B, representado por conjunto de todos los pares ordenados de la forma (a, b), donde e A y Por lo general, A xB BxA. Por ejemplo, dados los conjuntos: A = {a,b,c} B ={ 1 ,2 } entonces:

es el

A x B = {(a. 1), (a ,2), (fe, 1), (6,2), (c, 1), (c, 2)} Es posible generalizar el concepto del producto de conjuntos para obtener el producto de más de dos conjuntos. Así, dados los conjuntos: A = {a, &}, S = { l , 2} y C = y}, entonces: A x B x C ={(a, 1, x), (fe, 2, x), (fe, 2, y)}

1.2.

(a, 1, y), (a, 2, x), (a, 2,

Conceptos fundamentales de la teoría de autómatas

A lo largo de este texto e independientemente del tipo de máquina que se considere, se van a utilizar una serie de conceptos comunes a todas las máquinas. Con el fin de servir de guía de consulta, se recogen en esta sección un listado de términos comunes y su definición.

Alfabeto Un alfabeto es un conjunto de símbolos finito no vacío. Normalmente se utiliza el símbolo £ para denotar un alfabeto. A continuación se muestran algunos ejemplos: ■ £ = {a, fe} un alfabeto compuesto por dos símbolos.

Co n c e p t o s

previos

5

■ £ = {0, 1, 2} un alfabeto compuesto por tres símbolos. ■ £ = {a, b, c, d} un alfabeto compuesto por cuatro símbolos.

Cadena de caracteres Una cadena de caracteres es una secuencia finita de símbolos de un alfabeto. Por ejemplo, aba es una cadena del alfabeto £ = {«., />, c}. Una cadena especial a considerar es la cadena vacía. La cadena vacía es aquella cadena que no contiene ningún símbolo. Esta cadena se representa con el símbolo e o con el símbolo A y se puede definir con cualquier alfabeto. La longitud de una cadena es igual al número de símbolos que contiene la cadena. Así, la cadena 001 tiene una longitud igual a 3. Para indicar la longitud de una cadena w se utiliza la notación |