Teoría de la Computación. Apuntes y Ejercicios


Save this PDF as:
 WORD  PNG  TXT  JPG

Tamaño: px
Comenzar la demostración a partir de la página:

Download "Teoría de la Computación. Apuntes y Ejercicios"

Transcripción

1 Teoría de la Computación (Lenguajes Formales, Computabilidad y Complejidad) Apuntes y Ejercicios Gonzalo Navarro Departamento de Ciencias de la Computación Universidad de Chile 17 de noviembre de 2009

2 2 Licencia de uso: Esta obra está bajo una licencia de Creative Commons (ver Esencialmente, usted puede distribuir y comunicar públicamente la obra, siempre que (1) dé crédito al autor de la obra, (2) no la use para fines comerciales, (3) no la altere, transforme, o genere una obra derivada de ella. Al reutilizar o distribuir la obra, debe dejar bien claro los términos de la licencia de esta obra. Estas condiciones pueden modificarse con permiso escrito del autor. Asimismo, agradeceré enviar un al autor, si utiliza esta obra fuera del Departamento de Ciencias de la Computación de la Universidad de Chile, para mis registros. Finalmente, toda sugerencia sobre el contenido, errores, omisiones, etc. es bienvenida al mismo .

3 Índice General 1 Conceptos Básicos Inducción Estructural Conjuntos, Relaciones y Funciones Cardinalidad Alfabetos, Cadenas y Lenguajes Especificación Finita de Lenguajes Lenguajes Regulares Expresiones Regulares (ERs) Autómatas Finitos Determinísticos (AFDs) Autómatas Finitos No Determinísticos (AFNDs) Conversión de ER a AFND Conversión de AFND a AFD Conversión de AFD a ER Propiedades de Clausura Lema de Bombeo Propiedades Algorítmicas de Lenguajes Regulares Ejercicios Preguntas de Controles Proyectos Lenguajes Libres del Contexto Gramáticas Libres del Contexto (GLCs) Todo Lenguaje Regular es Libre del Contexto Autómatas de Pila (AP) Conversión de GLC a AP Conversión a AP a GLC Teorema de Bombeo Propiedades de Clausura Propiedades Algorítmicas Determinismo y Parsing

4 4 ÍNDICE GENERAL 3.10 Ejercicios Preguntas de Controles Proyectos Máquinas de Turing y la Tesis de Church La Máquina de Turing (MT) Protocolos para Usar MTs Notación Modular MTs de k Cintas y Otras Extensiones MTs no Determinísticas (MTNDs) La Máquina Universal de Turing (MUT) La Tesis de Church Gramáticas Dependientes del Contexto (GDC) Ejercicios Preguntas de Controles Proyectos Computabilidad El Problema de la Detención Decidir, Aceptar, Enumerar Demostrando Indecidibilidad por Reducción Otros Problemas Indecidibles Ejercicios Preguntas de Controles Proyectos Complejidad Computacional Tiempo de Computación Modelos de Computación y Tiempos Las Clases P y N P SAT es NP-completo Otros Problemas NP-Completos La Jerarquía de Complejidad Ejercicios Preguntas de Controles Proyectos

5 Capítulo 1 Conceptos Básicos [LP81, cap 1] En este capítulo repasaremos brevemente conceptos elementales que el lector ya debiera conocer, y luego introduciremos elementos más relacionados con la materia. La mayoría de las definiciones, lemas, etc. de este capítulo no están indexados en el Índice de Materias al final del apunte, pues son demasiado básicos. Indexamos sólo lo que se refiere al tema específico de lenguajes formales, complejidad, y computabilidad. No repasaremos el lenguaje de la lógica de predicados de primer orden, que usaremos directamente, ni nada sobre números. 1.1 Inducción Estructural En muchas demostraciones del curso haremos inducción sobre estructuras definidas recursivamente. La inducción natural que se supone que el lector ya conoce, (P(0) (P(n) P(n + 1)) n 0, P(n)), puede extenderse a estas estructuras recursivas. Esencialmente lo que se hace es aplicar inducción natural sobre alguna propiedad de la estructura (como su tamaño), de modo que pueda suponerse que la propiedad vale para todas sus subestructuras. Veamos un ejemplo. Un árbol binario es o bien un nodo hoja o bien un nodo interno del que cuelgan dos árboles binarios. Llamemos i(a) y h(a) a la cantidad de nodos internos y nodos hojas, respectivamente, de un árbol binario A. Demostremos por inducción estructural que, para todo árbol binario A, i(a) = h(a) 1. Caso base: Si el árbol A es un nodo hoja, entonces tiene cero nodos internos y una hoja, y la proposición vale pues i(a) = 0 y h(a) = 1. Caso inductivo: Si el árbol A es un nodo interno del que cuelgan subárboles A 1 y A 2, tenemos por hipótesis inductiva que i(a 1 ) = h(a 1 ) 1 y i(a 2 ) = h(a 2 ) 1. Ahora bien, los nodos de A son los de A 1, los de A 2, y un nuevo nodo interno. De modo que i(a) = i(a 1 ) + i(a 2 ) + 1 y h(a) = h(a 1 ) + h(a 2 ). De aquí que i(a) = h(a 1 ) 1 + h(a 2 ) = h(a 1 ) + h(a 2 ) 1 = h(a) 1 y hemos terminado. 5

6 6 CAPÍTULO 1. CONCEPTOS BÁSICOS 1.2 Conjuntos, Relaciones y Funciones Definición 1.1 Un conjunto A es una colección finita o infinita de objetos. Se dice que esos objetos pertenecen al conjunto, x A. Una condición lógica equivalente a x A define el conjunto A. Definición 1.2 El conjunto vacío, denotado, es un conjunto sin elementos. Definición 1.3 Un conjunto B es subconjunto de un conjunto A, B A, si x B x A. Si además B A, se puede decir B A. Definición 1.4 Algunas operaciones posibles sobre dos conjuntos A y B son: 1. Unión: x A B sii x A x B. 2. Intersección: x A B sii x A x B. 3. Diferencia: x A B sii x A x B. 4. Producto: (x, y) A B sii x A y B. Definición 1.5 Una partición de un conjunto A es un conjunto de conjuntos B 1,...B n tal que A = 1 i n B i y B i B j = para todo i j. Definición 1.6 Una relación R entre dos conjuntos A y B, es un subconjunto de A B. Si (a, b) R se dice también arb. Definición 1.7 Algunas propiedades que puede tener una relación R A A son: Reflexividad: a A, ara. Simetría: a, b A, arb bra. Transitividad: a, b, c A, arb brc arc. Antisimetría: a b A, arb bra. Definición 1.8 Algunos tipos de relaciones, según las propiedades que cumplen, son: de Equivalencia: Reflexiva, simétrica y transitiva. de Preorden: Reflexiva y transitiva. de Orden: Reflexiva, antisimétrica y transitiva.

7 1.3. CARDINALIDAD 7 Definición 1.9 Una relación de equivalencia en A (o sea A A) particiona A en clases de equivalencia, de modo que a, a A están en la misma clase sii a a. Al conjunto de las clases de equivalencia, A/, se lo llama conjunto cuociente. Definición 1.10 Clausurar una relación R A A es agregarle la mínima cantidad de elementos necesaria para que cumpla una cierta propiedad. Clausura reflexiva: es la menor relación reflexiva que contiene R ( menor en sentido de que no contiene otra, vista como conjunto). Para obtenerla basta incluir todos los pares (a, a), a A, en R. Clausura transitiva: es la menor relación transitiva que contiene R. Para obtenerla deben incluirse todos los pares (a, c) tales que (a, b) R y (b, c) R. Deben considerarse también los nuevos pares que se van agregando! Definición 1.11 Una función f : A B es una relación en A B que cumple que a A,! b B, afb. A ese único b se lo llama f(a). A se llama el dominio y {f(a), a A} B la imagen de f. Definición 1.12 Una función f : A B es: inyectiva si a a f(a) f(a ). sobreyectiva si b B, a A, f(a) = b. biyectiva si es inyectiva y sobreyectiva. 1.3 Cardinalidad La cardinalidad de un conjunto finito es simplemente la cantidad de elementos que tiene. Esto es más complejo para conjuntos infinitos. Deben darse nombres especiales a estas cardinalidades, y no todas las cardinalidades infinitas son iguales. Definición 1.13 La cardinalidad de un conjunto A se escribe A. Si A es finito, entonces A es un número natural igual a la cantidad de elementos que pertenecen a A. Definición 1.14 Se dice que A B si existe una función f : A B inyectiva. Se dice que A B si existe una función f : A B sobreyectiva. Se dice que A = B si existe una función f : A B biyectiva. Se dice A < B si A B y no vale A = B ; similarmente con A > B.

8 8 CAPÍTULO 1. CONCEPTOS BÁSICOS Definición 1.15 A la cardinalidad de N se la llama N = ℵ 0 (alef sub cero). A todo conjunto de cardinal ℵ 0 se le dice numerable. Observación 1.1 Un conjunto numerable A, por definición, admite una sobreyección f : N A, o lo que es lo mismo, es posible listar los elementos de A en orden f(0), f(1), f(2),... de manera que todo elemento de A se mencione alguna vez. De modo que para demostrar que A es numerable basta exhibir una forma de listar sus elementos y mostrar que todo elemento será listado en algún momento. Teorema 1.1 ℵ 0 es el menor cardinal infinito. Más precisamente, todo A tal que A ℵ 0 cumple que A es finito o A = ℵ 0. Prueba: Si A es infinito, entonces A > n para cualquier n 0. Es decir, podemos definir subconjuntos A n A, A n = n, para cada n 0, de modo que A n 1 A n. Sea a n el único elemento de A n A n 1. Entonces todos los a n son distintos y podemos hacer una sobreyección de {a 1, a 2,...} en N. Observación 1.2 El que A B no implica que A < B en conjuntos infinitos. Por ejemplo el conjunto de los pares es del mismo cardinal que el de los naturales, mediante la biyección f(n) = 2n. Teorema 1.2 El cardinal de (N) es estrictamente mayor que el de N. Prueba: Es fácil ver, mediante biyecciones, que los siguientes conjuntos tienen el mismo cardinal que (N): 1. Las secuencias infinitas de bits, haciendo la biyección con (N) dada por: el i-ésimo bit es 1 sii i 1 pertenece al subconjunto. 2. Las funciones f : N {0,1}, haciendo la biyección con el punto 1; F(f) = f(0)f(1)f(2)... es una secuencia infinita de bits que describe unívocamente a f. 3. Los números reales 0 x < 1: basta escribirlos en binario de la forma , para tener la biyección con las secuencias infinitas de bits. Hay algunas sutilezas debido a que = , pero pueden remediarse. 4. Los reales mismos, R, mediante alguna función biyectiva con [0, 1) (punto 3). Hay varias funciones trigonométricas, como la tangente, que sirven fácilmente a este propósito. Utilizaremos el método de diagonalización de Cantor para demostrar que las secuencias infinitas de bits no son numerables. Supondremos, por contradicción, que podemos hacer una lista de todas las secuencias de bits, B 1, B 2, B 3,..., donde B i es la i-ésima secuencia y B i (j) es el j-ésimo bit de B i. Definamos ahora la secuencia de bits X = B 1 (1) B 2 (2)..., donde 0 = 1 y 1 = 0. Como X(i) = B i (i) B i (i), se deduce que X B i para todo B i. Entonces X es una secuencia de bits que no aparece en la lista. Para cualquier listado, podemos generar un elemento que no aparece, por lo cual no puede existir un listado exhaustivo de todas las secuencias infinitas de bits.

9 1.3. CARDINALIDAD 9 Observación 1.3 La hipótesis del continuo establece que no existe ningún conjunto X tal que N < X < R. Se ha probado que esta hipótesis no se puede probar ni refutar con los axiomas usuales de la teoría de conjuntos, sino que es necesario introducirla (o a su negación) como un axioma adicional. Lema 1.1 Sean A y B numerables. Los siguientes conjuntos son numerables: 1. A B. 2. A B. 3. A k, donde A 1 = A y A k = A A k A i, donde todos los A i son numerables. 5. A + = A 1 A 2 A 3... Prueba: Sean a 1, a 2,... y b 1, b 2,... listados que mencionan todos los elementos de A y B, respectivamente. 1. a 1, b 1, a 2, b 2,... lista A B y todo elemento aparece en la lista alguna vez. Si A B esta lista puede tener repeticiones, pero eso está permitido. 2. No podemos listar (a 1,b 1 ), (a 1,b 2 ), (a 1,b 3 ),... porque por ejemplo nunca llegaríamos a listar (a 2,b 1 ). Debemos aplicar un recorrido sobre la matriz de índices de modo que a toda celda (a i,b j ) le llegue su turno. Por ejemplo, por diagonales (i + j creciente): (a 1,b 1 ), luego (a 2,b 1 ), (a 1,b 2 ), luego (a 3,b 1 ), (a 2,b 2 ), (a 1,b 3 ), y así sucesivamente. 3. Por inducción sobre k y usando el punto Sea a i (j) el j-ésimo elemento de lista que numera A i. Nuevamente se trata de recorrer una matriz para que le llegue el turno a todo a i (j), y se resuelve como el punto Es una unión de una cantidad numerable de conjuntos, donde cada uno de ellos es numerable por el punto 3, de modo que se puede aplicar el punto 4. Si esto parece demasiado esotérico, podemos expresar la solución concretamente: listemos el elemento 1 de A 1 ; luego el 2 de A 1 y el 1 de A 2 ; luego el 3 de A 1, el 2 de A 2 y el 1 de A 3 ; etc. Está claro que a cada elemento de cada conjunto le llegará su turno. Observación 1.4 El último punto del Lema 1.1 se refiere al conjunto de todas las secuencias finitas donde los elementos pertenecen a un conjunto numerable. Si esto es numerable, está claro que las secuencias finitas de elementos de un conjunto finito también lo son. Curiosamente, las secuencias infinitas no son numerables, ni siquiera sobre conjuntos finitos, como se vió para el caso de bits en el Teo. 1.2.

10 10 CAPÍTULO 1. CONCEPTOS BÁSICOS Notablemente, aún sin haber visto casi nada de computabilidad, podemos establecer un resultado que nos plantea un desafío para el resto del curso: Teorema 1.3 Dado cualquier lenguaje de programación, existen funciones de los enteros que no se pueden calcular con ningún programa escrito en ese lenguaje. Prueba: Incluso restringiéndonos a las funciones que dado un entero deben responder sí o no (por ejemplo, es n primo?), hay una cantidad no numerable de funciones f : N {0,1}. Todos los programas que se pueden escribir en su lenguaje de programación favorito, en cambio, son secuencias finitas de símbolos (ASCII, por ejemplo). Por lo tanto hay sólo una cantidad numerable de programas posibles. Mucho más difícil será exhibir una función que no se pueda calcular, pero es interesante que la inmensa mayoría efectivamente no se puede calcular. En realidad esto es un hecho más básico aún, por ejemplo la inmensa mayoría de los números reales no puede escribirse en ningún formalismo que consista de secuencias de símbolos sobre un alfabeto numerable. 1.4 Alfabetos, Cadenas y Lenguajes En esta sección introducimos notación más específica del curso. Comezaremos por definir lo que es un alfabeto. Definición 1.16 Llamaremos alfabeto a cualquier conjunto finito no vacío. Usualmente lo denotaremos como Σ. Los elementos de Σ se llamarán símbolos o caracteres. Si bien normalmente usaremos alfabetos intuitivos como {0, 1}, {a, b}, {a...z}, {0...9}, etc., algunas veces usaremos conjuntos más sofisticados como alfabetos. Definición 1.17 Llamaremos cadena a una secuencia finita de símbolos de un alfabeto Σ, es decir, a un elemento de Σ = Σ 0 Σ 1 Σ 2... donde Σ 1 = Σ y Σ k = Σ Σ k 1. Σ denota, entonces, el conjunto de todas las secuencias finitas de símbolos de Σ. El conjunto Σ 0 es especial, tiene un sólo elemento llamado ε, que corresponde a la cadena vacía. Si una cadena x Σ k entonces decimos que su largo es x = k (por ello ε = 0). Otro conjunto que usaremos es Σ + = Σ {ε}. Observación 1.5 Es fácil confundir entre una cadena de largo 1, x = (a), y un carácter a. Normalmente nos permitiremos identificar ambas cosas.

11 1.5. ESPECIFICACIÓN FINITA DE LENGUAJES 11 Definición 1.18 Una cadena x sobre Σ se escribirá juxtaponiendo sus caracteres uno luego del otro, es decir (a 1, a 2,...,a x ), a i Σ, se escribirá como x = a 1 a 2...a x. La concatenación de dos cadenas x = a 1 a 2...a n e y = b 1 b 2...b m, se escribe xy = a 1 a 2...a n b 1 b 2...b m, xy = x + y. Finalmente usaremos x k para denotar k concatenaciones sucesivas de x, es decir x 0 = ε y x k = xx k 1. Definición 1.19 Dadas cadenas x, y, z, diremos que x es un prefijo de xy, un sufijo de yx, y una subcadena o substring de yxz. Definición 1.20 Un lenguaje sobre un alfabeto Σ es cualquier subconjunto de Σ. Observación 1.6 El conjunto de todas las cadenas sobre cualquier alfabeto es numerable, Σ = ℵ 0, y por lo tanto todo lenguaje sobre un alfabeto finito (e incluso numerable) Σ es numerable. Sin embargo, la cantidad de lenguajes distintos es no numerable, pues es (Σ ) > ℵ 0. Cualquier operación sobre conjuntos puede realizarse sobre lenguajes también. Definamos ahora algunas operaciones específicas sobre lenguajes. Definición 1.21 Algunas operaciones aplicables a lenguajes sobre un alfabeto Σ son: 1. Concatenación: L 1 L 2 = {xy, x L 1, y L 2 }. 2. Potencia: L 0 = {ε}, L k = L L k Clausura de Kleene: L = k 0 Lk. 4. Complemento: L c = Σ L. 1.5 Especificación Finita de Lenguajes Si un lenguaje L es finito, se puede especificar por extensión, como L 1 = {aba, bbbbb, aa}. Si es infinito, se puede especificar mediante predicados, por ejemplo L 2 = {a p, p es primo}. Este mecanismo es poderoso, pero no permite tener una idea de la complejidad del lenguaje, en el sentido de cuán difícil es determinar si una cadena pertenece o no a L, o de enumerar las cadenas de L. Con L 1 esto es trivial, y con L 2 perfectamente factible. Pero ahora consideremos L 3 = {a n, n 0, x, y, z N {0}, x n + y n = z n }. L 3 está correctamente especificado, pero aaa L 3? Recién con la demostración del último Teorema de Fermat en 1995 (luego de más de 3 siglos de esfuerzos), se puede establecer que L 3 = {a, aa}. Similarmente, se puede especificar L 4 = {w, w es un teorema de la teoría de números}, y responder si w L 4 equivale a demostrar un teorema. El tema central de este curso se puede ver como la búsqueda de descripciones finitas para lenguajes infinitos, de modo que sea posible determinar mecánicamente si una cadena

12 12 CAPÍTULO 1. CONCEPTOS BÁSICOS está en el lenguaje. Qué interés tiene esto? No es difícil identificar lenguajes con problemas de decisión. Por ejemplo, la pregunta el grafo G es bipartito? se puede traducir a una pregunta de tipo w L?, donde L es el conjunto de cadenas que representan los grafos bipartitos (representados como una secuencia de alguna manera, finalmente todo son secuencias de bits en el computador!), y w es la representación de G. Determinar que ciertos lenguajes no pueden decidirse mecánicamente equivale a determinar que ciertos problemas no pueden resolverse por computador. El siguiente teorema, nuevamente, nos dice que la mayoría de los lenguajes no puede decidirse, en el sentido de poder decir si una cadena dada le pertenece o no. Nuevamente, es un desafío encontrar un ejemplo. Teorema 1.4 Dado cualquier lenguaje de programación, existen lenguajes que no pueden decidirse con ningún programa. Prueba: Nuevamente, la cantidad de lenguajes es no numerable y la de programas que se pueden escribir es numerable. En el curso veremos mecanismos progresivamente más potentes para describir lenguajes cada vez más sofisticados y encontraremos los límites de lo que puede resolverse por computador. Varias de las cosas que veremos en el camino tienen además muchas aplicaciones prácticas.

13 Capítulo 2 Lenguajes Regulares [LP81, sec 1.9 y cap 2] En este capítulo estudiaremos una forma particularmente popular de representación finita de lenguajes. Los lenguajes regulares son interesantes por su simplicidad, la que permite manipularlos fácilmente, y a la vez porque incluyen muchos lenguajes relevantes en la práctica. Los mecanismos de búsqueda provistos por varios editores de texto (vi, emacs), así como por el shell de Unix y todas las herramientas asociadas para procesamiento de texto (sed, awk, perl), se basan en lenguajes regulares. Los lenguajes regulares también se usan en biología computacional para búsqueda en secuencias de ADN o proteínas (por ejemplo patrones PROSITE). Los lenguajes regulares se pueden describir usando tres mecanismos distintos: expresiones regulares (ERs), autómatas finitos determinísticos (AFDs) y no determinísticos (AFNDs). Algunos de los mecanismos son buenos para describir lenguajes, y otros para implementar reconocedores eficientes. 2.1 Expresiones Regulares (ERs) [LP81, sec 1.9] Definición 2.1 Una expresión regular (ER) sobre un alfabeto finito Σ se define recursivamente como sigue: 1. Para todo c Σ, c es una ER. 2. Φ es una ER. 3. Si E 1 y E 2 son ERs, E 1 E 2 es una ER. 4. Si E 1 y E 2 son ERs, E 1 E 2 es una ER. 5. Si E 1 es una ER, E 1 es una ER. 6. Si E 1 es una ER, (E 1 ) es una ER. 13

14 14 CAPÍTULO 2. LENGUAJES REGULARES Cuando se lee una expresión regular, hay que saber qué operador debe leerse primero. Esto se llama precedencia. Por ejemplo, la expresión a b c, debe entenderse como (1) la aplicada al resto? (2) la aplicada al resto? (3) la aplicada al resto? La respuesta es que, primero que nada se aplican los, segundo los, y finalmente los. Esto se expresa diciendo que el orden de precedencia es,,. Los paréntesis sirven para alterar la precedencia. Por ejemplo, la expresión anterior, dado el orden de precedencia que establecimos, es equivalente a a (b (c )). Se puede forzar otro orden de lectura de la ER cambiando los paréntesis, por ejemplo (a b) c. Asimismo, debe aclararse cómo se lee algo como a b c, es decir cuál de los dos se lee primero? Convengamos que en ambos operadores binarios se lee primero el de más a la izquierda (se dice que el operador asocia a la izquierda ), pero realmente no es importante, por razones que veremos enseguida. Observar que aún no hemos dicho qué significa una ER, sólo hemos dado su sintaxis pero no su semántica. De esto nos encargamos a continuación. Definición 2.2 El lenguaje descrito por una ER E, L(E), se define recursivamente como sigue: 1. Si c Σ, L(c) = {c}. Esto es un conjunto de una sola cadena de una sola letra. 2. L(Φ) =. 3. L(E 1 E 2 ) = L(E 1 ) L(E 2 ). 4. L(E 1 E 2 ) = L(E 1 ) L(E 2 ). 5. L(E 1 ) = L(E 1 ). 6. L((E 1 )) = L(E 1 ). Notar que L(a b c d) = {abcd}, por lo cual es común ignorar el símbolo y simplemente yuxtaponer los símbolos uno después del otro. Notar también que, dado que y se mapean a operadores asociativos, no es relevante si asocian a izquierda o a derecha. Observación 2.1 Por definición de clausura de Kleene, L(Φ ) = {ε}. Por ello, a pesar de no estar formalmente en la definición, permitiremos escribir ε como una expresión regular. Definición 2.3 Un lenguaje L es regular si existe una ER E tal que L = L(E). Ejemplo 2.1 Cómo se podría escribir una ER para las cadenas de a s y b s que contuvieran una cantidad impar de b s? Una solución es a (ba ba ) ba, donde lo más importante es la clausura de Kleene mayor, que encierra secuencias donde nos aseguramos que las b s vienen de a pares, separadas por cuantas a s se quieran. La primera clausura (a ) permite que la secuencia empiece con a s y la última agrega la b que hace que el total sea impar y además permite que haya a s al final. Es un buen ejercicio jugar con otras soluciones y comentarlas, por ejemplo (a ba ba ) ba. Es fácil ver cómo generalizar este ejemplo para que la cantidad de b s módulo k sea r.

15 2.2. AUTÓMATAS FINITOS DETERMINÍSTICOS (AFDS) 15 Algo importante en el Ej. 2.1 es cómo asegurarnos de que la ER realmente representa el lenguaje L que creemos. La técnica para esto tiene dos partes: (i) ver que toda cadena generada está en L; (ii) ver que toda cadena de L se puede generar con la ER. En el Ej. 2.1 eso podría hacerse de la siguiente manera: Para (i) basta ver que la clausura de Kleene introduce las b s de a dos, de modo que toda cadena generada por la ER tendrá una cantidad impar de b s. Para (ii), se debe tomar una cadena cualquiera x con una cantidad impar de b s y ver que la ER puede generarla. Esto no es difícil si consideramos las subcadenas de x que van desde una b impar (1era, 3era,...) hasta la siguiente, y mostramos que cada una de esas subcadenas se pueden generar con ba ba. El resto es sencillo. Un ejemplo un poco más complicado es el siguiente. Ejemplo 2.2 Cómo se podría escribir una ER para las cadenas de a s y b s que nunca contuvieran tres b s seguidas? Una solución parece ser (a ba bba), pero está correcta? Si se analiza rigurosamente, se notará que esta ER no permite que las cadenas terminen con b, por lo cual deberemos corregirla a (a ba bba) (ε b bb). Ejemplo 2.3 Cómo se describiría el lenguaje denotado por la expresión regular (ab aba)? Son las cadenas que se pueden descomponer en secuencias ab o aba. Describir con palabras el lenguaje denotado por una ER es un arte. En el Ej. 2.1, que empieza con una bonita descripción concisa, uno podría caer en una descripción larga y mecánica de lo que significa la ER, como primero viene una secuencia de a s; después, varias veces, viene una b y una secuencia de a s, dos veces; después.... En general una descripción más concisa es mejor. Ejemplo 2.4 Se podría escribir una ER que denotara los números decimales que son múltiplos de 7? (es decir 7, 14, 21,...) Sí, pero intentarlo directamente es una empresa temeraria. Veremos más adelante cómo lograrlo. Observación 2.2 Debería ser evidente que no todos los lenguajes que se me ocurran pueden ser descritos con ERs, pues la cantidad de lenguajes distintos sobre un alfabeto finito es no numerable, mientras que la cantidad de ERs es numerable. Otra cosa es encontrar lenguajes concretos no expresables con ERs y poder demostrar que no lo son. Ejemplo 2.5 Se podría escribir una ER que denotara las cadenas de a s cuyo largo es un número primo? No, no se puede. Veremos más adelante cómo demostrar que no se puede. Ejemplo 2.6 Algunas aplicaciones prácticas donde se usan ERs es en la especificación de fechas, direcciones IP, tags XML, nombres de variables en Java, números en notación flotante, direcciones de , etc. Son ejercicios interesantes, aunque algunos son algo tediosos. 2.2 Autómatas Finitos Determinísticos (AFDs) [LP81, sec 2.1] Un AFD es otro mecanismo para describir lenguajes. En vez de pensar en generar las cadenas (como las ERs), un AFD describe un lenguaje mediante reconocer las cadenas del lenguaje, y ninguna otra. El siguiente ejemplo ilustra un AFD.

16 16 CAPÍTULO 2. LENGUAJES REGULARES Ejemplo 2.7 El AFD que reconoce el mismo lenguaje del Ej. 2.1 se puede graficar de la siguiente forma. a 0 b b a 1 El AFD que hemos dibujado se interpreta de la siguiente manera. Los nodos del grafo son estados. El apuntado con un ángulo es el estado inicial, en el que empieza la computación. Estando en un estado, el AFD lee una letra de la entrada y, según indique la flecha (llamada transición), pasa a otro estado (siempre debe haber exactamente una flecha saliendo de cada estado por cada letra). Cuando se lee toda la cadena, el AFD la acepta o no según el estado al que haya llegado sea final o no. Los estados finales se dibujan con doble círculo. En este AFD pasa algo que, más o menos explícitamente, siempre ocurre. Cada estado se puede asociar a un invariante, es decir, una afirmación sobre la cadena leída hasta ese momento. En nuestro caso el estado inicial corresponde al invariante se ha visto una cantidad par de b s hasta ahora, mientras que el estado final corresponde a se ha visto una cantidad impar de b s hasta ahora. El siguiente ejemplo muestra la utilidad de esta visión. La correctitud de un AFD con respecto a un cierto lenguaje L que se pretende representar se puede demostrar a partir de establecer los invariantes, ver que los estados finales, unidos (pues puede haber más de uno), describen L, y que las flechas pasan correctamente de un invariante a otro. Ejemplo 2.8 El AFD que reconoce el mismo lenguaje del Ej. 2.2 se puede graficar de la siguiente forma. Es un buen ejercicio describir el invariante que le corresponde a cada estado. Se ve además que puede haber varios estados finales. El estado 3 se llama sumidero, porque una vez caído en él, el AFD no puede salir y no puede aceptar la cadena. a 0 b a a b 1 2 a,b b 3 Es hora de definir formalmente lo que es un AFD.

17 2.2. AUTÓMATAS FINITOS DETERMINÍSTICOS (AFDS) 17 Definición 2.4 Un autómata finito determinístico (AFD) es una tupla M = (K, Σ, δ, s, F), tal que K es un conjunto finito de estados. Σ es un alfabeto finito. s K es el estado inicial. F K son los estados finales. δ : K Σ K es la función de transición. Ejemplo 2.9 El AFD del Ej. 2.7 se describe formalmente como M = (K, Σ, δ, s, F), donde K = {0,1}, Σ = {a,b}, s = 0, F = {1}, y la función δ como sigue: δ 0 1 a 0 1 b 1 0 No hemos descrito aún formalmente cómo funciona un AFD. Para ello necesitamos la noción de configuración, que contiene la información necesaria para completar el cómputo de un AFD. Definición 2.5 Una configuración de un AFD M = (K, Σ, δ, s, F) es un elemento de C M = K Σ. La idea es que la configuración (q, x) indica que M está en el estado q y le falta leer la cadena x de la entrada. Esta es información suficiente para predecir lo que ocurrirá en el futuro. Lo siguiente es describir cómo el AFD nos lleva de una configuración a la siguiente. Definición 2.6 La relación lleva en un paso, M C M C M se define de la siguiente manera: (q, ax) M (q, x), donde a Σ, sii δ(q, a) = q. Escribiremos simplemente en vez de M cuando quede claro de qué M estamos hablando. Definición 2.7 La relación lleva en cero o más pasos M de M. es la clausura reflexiva y transitiva Ya estamos en condiciones de definir el lenguaje aceptado por un AFD. La idea es que si el AFD es llevado del estado inicial a uno final por la cadena x, entonces la reconoce.

18 18 CAPÍTULO 2. LENGUAJES REGULARES Definición 2.8 El lenguaje aceptado por un AFD M = (K, Σ, δ, s, F) se define como L(M) = {x Σ, f F, (s, x) M (f, ε)}. Ejemplo 2.10 Tomemos el AFD del Ej. 2.8, el que se describe formalmente como M = (K,Σ,δ,s,F), donde K = {0,1,2,3}, Σ = {a,b}, s = 0, F = {0,1,2}, y la función δ como sigue: δ a b Ahora consideremos la cadena de entrada x = abbababb y escribamos las configuraciones por las que pasa M al recibir x como entrada: (0, abbababb) (0, bbababb) (1, bababb) (2, ababb) (0,babb) (1,abb) (0,bb) (1,b) (2,ε). Por lo tanto (s,x) (2,ε), y como 2 F, tenemos que x L(M). Vamos al desafío del Ej. 2.4, el cual resolveremos con un AFD. La visión de invariantes es especialmente útil en este caso. Ejemplo 2.11 El AFD que reconoce el mismo lenguaje del Ej. 2.4 se puede graficar de la siguiente forma. Para no enredar el gráfico de más, sólo se incluyen las flechas que salen de los estados 0, 1 y 2.

19 2.2. AUTÓMATAS FINITOS DETERMINÍSTICOS (AFDS) ,7 1,8 2,9 2,9 1,8 0, ,7 1,8 2, El razonamiento es el siguiente. Cada estado representa el resto del número leído hasta ahora, módulo 7. El estado inicial (y final) representa el cero. Si estoy en el estado 2 y viene un 4, significa que el número que leí hasta ahora era n 2 (mod 7) y ahora el nuevo número leído es 10 n (mod 7). Por ello se pasa al estado 3. El lector puede completar las flechas que faltan en el diagrama. Hemos resuelto usando AFDs un problema que es bastante más complicado usando ERs. El siguiente ejemplo ilustra el caso contrario: el Ej. 2.3, sumamente fácil con ERs, es relativamente complejo con AFDs, y de hecho no es fácil convencerse de su correctitud. El principal problema es, cuando se ha leído ab, determinar si una a que sigue inicia una nueva cadena (pues hemos leído la cadena ab) o es el último carácter de aba. Ejemplo 2.12 El lenguaje descrito en el Ej. 2.3 se puede reconocer con el siguiente AFD. a 0 b a b 1 2 a b a b 3 4 a,b

20 20 CAPÍTULO 2. LENGUAJES REGULARES 2.3 Autómatas Finitos No Determinísticos (AFNDs) [LP81, sec 2.2] Dado el estado actual y el siguiente carácter, el AFD pasa exactamente a un siguiente estado. Por eso se lo llama determinístico. Una versión en principio más potente es un AFND, donde frente a un estado actual y un siguiente carácter, es posible tener cero, uno o más estados siguientes. Hay dos formas posibles de entender cómo funciona un AFND. La primera es pensar que, cuando hay varias alternativas, el AFND elige alguna de ellas. Si existe una forma de elegir el siguiente estado que me lleve finalmente a aceptar la cadena, entonces el AFND la aceptará. La segunda forma es imaginarse que el AFND está en varios estados a la vez (en todos en los que puede estar de acuerdo a la primera visión). Si luego de leer la cadena puede estar en un estado final, acepta la cadena. En cualquier caso, es bueno por un rato no pensar en cómo implementar un AFND. Una libertad adicional que permitiremos en los AFNDs es la de rotular las transiciones con cadenas, no sólo con caracteres. Tal transición se puede seguir cuando los caracteres de la entrada calzan con la cadena que rotula la transición, consumiendo los caracteres de la entrada. Un caso particularmente relevante es el de las llamadas transiciones-ε, rotuladas por la cadena vacía. Una transición-ε de un estado p a uno q permite activar q siempre que se active p, sin necesidad de leer ningún carácter de la entrada. Ejemplo 2.13 Según la descripción, es muy fácil definir un AFND que acepte el lenguaje del Ej Se presentan varias alternativas, donde en la (2) y la (3) se hace uso de cadenas rotulando transiciones. a 1 (1) 0 b a a b 2 3 ab a (3) 0 (2) 0 a b 1 2 ε aba El Ej ilustra en el AFND (3) un punto interesante. Este AFND tiene sólo un estado y éste es final. Cómo puede no aceptar una cadena? Supongamos que recibe como entrada

21 2.3. AUTÓMATAS FINITOS NO DETERMINÍSTICOS (AFNDS) 21 bb. Parte del estado inicial (y final), y no tiene transiciones para moverse. Queda, pues, en ese estado. Acepta la cadena? No, pues no ha logrado consumirla. Un AFND acepta una cadena cuando tiene una forma de consumirla y llegar a un estado final. Es hora de formalizar. Definición 2.9 Un autómata finito no determinístico (AFND) es una tupla M = (K, Σ,, s, F), tal que K es un conjunto finito de estados. Σ es un alfabeto finito. s K es el estado inicial. F K son los estados finales. F K Σ K es la relación de transición, finita. Ejemplo 2.14 El AFND (2) del Ej se describe formalmente como M = (K,Σ,,s,F), donde K = {0, 1, 2}, Σ = {a, b}, s = 0, F = {0}, y la relación = {(0,a,1), (1,b,2), (2,a,0), (2,ε,0)}. Para describir la semántica de un AFND reutilizaremos la noción de configuración (Def. 2.5). Redefiniremos la relación M para el caso de AFNDs. Definición 2.10 La relación lleva en un paso, M C M C M, donde M = (K, Σ,, s, F) es un AFND, se define de la siguiente manera: (q, zx) M (q, x), donde z Σ, sii (q, z, q ). Nótese que ahora, a partir de una cierta configuración, la relación M nos puede llevar a varias configuraciones distintas, o incluso a ninguna. La clausura reflexiva y transitiva de M se llama, nuevamente, lleva en cero o más pasos, M. Finalmente, definimos casi idénticamente al caso de AFDs el lenguaje aceptado por un AFND. Definición 2.11 El lenguaje aceptado por un AFND M = (K, Σ,, s, F) se define como L(M) = {x Σ, f F, (s, x) M (f, ε)}. A diferencia del caso de AFDs, dada una cadena x, es posible llegar a varios estados distintos (o a ninguno) luego de haberla consumido. La cadena se declara aceptada si alguno de los estados a los que se llega es final.

22 22 CAPÍTULO 2. LENGUAJES REGULARES Ejemplo 2.15 Consideremos la cadena de entrada x = ababaababa y escribamos las configuraciones por las que pasa el AFND (3) del Ej al recibir x como entrada. En un primer intento: (0, ababaababa) (0, abaababa) (0, aababa) no logramos consumir la cadena (por haber tomado las transiciones incorrectas ). Pero si elegimos otras transiciones: (0, ababaababa) (0, abaababa) (0, ababa) (0, ba) (0, ε). Por lo tanto (s,x) (0,ε), y como 0 F, tenemos que x L(M). Esto es válido a pesar de que existe otro camino por el que (s,x) (0,aababa), de donde no es posible seguir avanzando. Terminaremos con una nota acerca de cómo simular un AFND. En las siguientes secciones veremos que de hecho los AFNDs pueden convertirse a AFDs, donde es evidente cómo simularlos eficientemente. Observación 2.3 Un AFND con n estados y m transiciones puede simularse en un computador en tiempo O(n + m) por cada símbolo de la cadena de entrada. Es un buen ejercicio pensar cómo (tiene que ver con recorrido de grafos, especialmente por las transiciones-ε). 2.4 Conversión de ER a AFND [LP81, sec 2.5] Como adelantamos, ERs, AFDs y AFNDs son mecanismos equivalentes para denotar los lenguajes regulares. En estas tres secciones demostraremos esto mediante convertir ER AFND AFD ER. Las dos primeras conversiones son muy relevantes en la práctica, pues permiten construir verificadores o buscadores eficientes a partir de ERs. Hay distintas formas de convertir una ER E a un AFND M, de modo que L(E) = L(M). Veremos el método de Thompson, que es de los más sencillos. Definición 2.12 La función Th convierte ERs en AFNDs según las siguientes reglas. 1. Para c Σ, Th(c) = c 2. Th(Φ) = Sí, el grafo puede no ser conexo!

23 2.4. CONVERSIÓN DE ER A AFND Th(E 1 E 2 ) = ε Th(E ) 1 ε ε Th(E ) 2 ε 4. Th(E 1 E 2 ) = Th(E ) 1 Th(E ) 2 5. Th(E 1 ) = ε ε Th(E ) 1 ε ε 6. Th((E 1 )) = Th(E 1 ). Observación 2.4 Es fácil, y un buen ejercicio, demostrar varias propiedades de T h(e) por inducción estructural: (i) T h(e) tiene un sólo estado final, distinto del inicial; (ii) T h(e) tiene a lo sumo 2e estados y 4e aristas, donde e es el número de caracteres en E; (iii) La cantidad de transiciones que llegan y salen de cualquier nodo en T h(e) no supera 2 en cada caso; (iv) al estado inicial de Th(E) no llegan transiciones, y del final no salen transiciones. Por simplicidad nos hemos conformado con definir T h usando dibujos esquemáticos. Realmente T h debe definirse formalmente, lo cual el lector puede hacer como ejercicio. Por ejemplo, si Th(E 1 ) = (K 1, Σ, 1, s 1, {f 1 }) y Th(E 2 ) = (K 2, Σ, 2, s 2, {f 2 }), entonces Th(E 1 E 2 ) = (K 1 K 2 {s, f}, Σ, 1 2 {(s, ε, s 1 ), (s, ε, s 2 ), (f 1, ε, f), (f 2, ε, f)}, s, {f}). El siguiente teorema indica que T h convierte correctamente ERs en AFNDs, de modo que el AFND reconoce las mismas cadenas que la ER genera. Teorema 2.1 Sea E una ER, entonces L(Th(E)) = L(E).

24 24 CAPÍTULO 2. LENGUAJES REGULARES Prueba: Es fácil verificarlo por inspección y aplicando inducción estructural. La única parte que puede causar problemas es la clausura de Kleene, donde otros esquemas alternativos que podrían sugerirse (por ejemplo M = (K 1,Σ, 1 {(f 1,ε,s 1 ),(s 1,ε,f 1 )},s 1, {f 1 }) tienen el problema de permitir terminar un recorrido de Th(E 1 ) antes de tiempo. Por ejemplo el ejemplo que acabamos de dar, aplicado sobre E 1 = a b, reconocería la cadena x = aa. Ejemplo 2.16 Si aplicamos el método de Thompson para convertir la ER del Ej. 2.3 a AFND, el resultado es distinto de las tres variantes dadas en el Ej ε ε a b ε ε 1 ε ε a b a ε 0 ε Conversión de AFND a AFD [LP81, sec 2.3] Si bien los AFNDs tienen en principio más flexibilidad que los AFDs, es posible construir siempre un AFD equivalente a un AFND dado. La razón fundamental, y la idea de la conversión, es que el conjunto de estados del AFND que pueden estar activos después de haber leído una cadena x es una función únicamente de x. Por ello, puede diseñarse un AFD basado en los conjuntos de estados del AFND. Lo primero que necesitamos es describir, a partir de un estado q del AFND, a qué estados q podemos llegar sin consumir caracteres de la entrada. Definición 2.13 Dado un AFND M = (K, Σ,, s, F), la clausura-ε de un estado q K se define como E(q) = {q K, (q, ε) M (q, ε)}. Ya estamos en condiciones de definir la conversión de un AFND a un AFD. Para ello supondremos que las transiciones del AFND están rotuladas o bien por ε o bien por una sola letra. Es muy fácil adaptar cualquier AFND para que cumpla esto. Definición 2.14 Dado un AFND M = (K, Σ,, s, F) que cumple (q, x, q ) x 1, se define un AFD det(m) = (K, Σ, δ, s, F ) de la siguiente manera:

25 2.5. CONVERSIÓN DE AFND A AFD K = (K). Es decir los subconjuntos de K, o conjuntos de estados de M. 2. s = E(s). Es decir la clausura-ε del estado inicial de M. 3. F = K (K F). Es decir todos los conjuntos de estados de M que contengan algún estado de F. 4. Para todo Q K (o sea Q K) y c Σ, δ(q, c) = q Q,(q,c,q ) E(q ). Esta última ecuación es la que preserva la semántica que buscamos para el AFD. Ejemplo 2.17 Si calculamos det sobre el AFND del Ej obtenemos el siguiente resultado. Observar que se trata del mismo AFD que presentamos en el Ej Lo que era un desafío hacer directamente, ahora lo podemos hacer mecánicamente mediante convertir ER AFND AFD. a 0,1,2,5,10 b a 3,6 a b b 4,7,9,1,2,5,10 a b 8,3,6,9,1,2,5,10 a,b En el Ej sólo hemos graficado algunos de los estados de K, más precisamente aquellos alcanzables desde el estado inicial. Los demás son irrelevantes. La forma de determinizar un AFND en la práctica es calcular s = E(s), luego calcular δ(s, c) para cada c Σ, y recursivamente calcular las transiciones que salen de estos nuevos estados, hasta que todos los estados nuevos producidos sean ya conocidos. De este modo se calculan solamente los estados necesarios de K. Observación 2.5 No hay garantía de que el método visto genere el menor AFD que reconoce el mismo lenguaje que el AFND. Existen, sin embargo, técnicas para minimizar AFDs, que no veremos aquí. El siguiente teorema establece la equivalencia entre un AFND y el AFD que se obtiene con la técnica expuesta.

26 26 CAPÍTULO 2. LENGUAJES REGULARES Teorema 2.2 Sea M un AFND, entonces L(det(M)) = L(M). Prueba: Demostraremos que toda cadena reconocida por el AFD M = det(m) también es reconocida por el AFND M, y viceversa. En cada caso, se procede por inducción sobre la longitud de la cadena. Lo que se demuestra es algo un poco más fuerte, para que la inducción funcione: (i) si x lleva de s a q en el AFND, entonces lleva de s = E(s) a algún Q tal que q Q en el AFD; (ii) si x lleva de E(s) a Q en el AFD, entonces lleva de s a cualquier q Q en el AFND. De esto se deduce inmediatamente que x L(M) x L(M ). Primero demostremos (i) y (ii) para el caso base x = ε. Es fácil ver que (ε,s) M (ε,q) sii q E(s). Por otro lado (ε,e(s)) M (ε,q) sii Q = E(s) pues M es determinístico. Se deducen (i) y (ii) inmediatamente. Veamos ahora el caso inductivo x = ya, a Σ, para (i). Si (s,ya) M (q,ε), como M consume las letras de a una, existe un camino de la forma (s,ya) M (q,a) M (q,ε) M (q,ε). Notar que esto implica que (q,a,q ) y q E(q ). Por hipótesis inductiva, además, tenemos (E(s),ya) M (Q,a) para algún Q que contiene q. Ahora bien, (Q,a) M (Q,ε), donde Q = δ(q,a) incluye, por la Def. 2.14, a E(q ), pues q Q y (q,a,q ). Finalmente, como q E(q ), tenemos q Q y terminamos. Veamos ahora el caso inductivo x = ya, a Σ, para (ii). Si (E(s),ya) M (Q,ε) debemos tener un camino de la forma (E(s),ya) M (Q,a) M (Q,ε), donde Q = δ(q,a). Por hipótesis inductiva, esto implica (s,ya) M (q,a) para todo q Q. Asimismo, (q,a) M (q,ε) M (q,ε), para todo (q,a,q ), y q E(q ). De la Def se deduce que cualquier q Q pertenece a algún E(q ) donde (q,a,q ) y q Q. Hemos visto que M puede llevar a cualquiera de esos estados. La siguiente observación indica cómo buscar las ocurrencias de una ER en un texto. Observación 2.6 Supongamos que queremos buscar las ocurrencias en un texto T de una ER E. Si calculamos det(th(σ E)), obtenemos un AFD que reconoce cadenas terminadas en E. Si alimentamos este AFD con el texto T, llegará al estado final en todas las posiciones de T que terminan una ocurrencia de una cadena de E. El algoritmo resultante es muy eficiente en términos del largo de T, si bien la conversión de AFND a AFD puede tomar tiempo exponencial en el largo de E. 2.6 Conversión de AFD a ER [LP81, sec 2.5] Finalmente, cerraremos el triángulo mostrando que los AFDs se pueden convertir a ERs que generen el mismo lenguaje. Esta conversión tiene poco interés práctico, pero es esencial para mostrar que los tres mecanismos de especificar lenguajes son equivalentes. La idea es numerar los estados de K de cero en adelante, y definir ERs de la forma R(i, j, k), que denotarán las cadenas que llevan al AFD del estado i al estado j utilizando en el camino solamente estados numerados < k. Notar que los caminos pueden ser arbitrariamente largos, pues la limitación está dada por los estados intermedios que se pueden usar. Asimismo la limitación no vale (obviamente) para los extremos i y j.

27 2.6. CONVERSIÓN DE AFD A ER 27 Definición 2.15 Dado un AFD M = (K, Σ, δ, s, F) con K = {0, 1,..., n 1} definimos expresiones regulares R(i, j, k) para todo 0 i, j < n, 0 k n, inductivamente sobre k como sigue. { Φ c1 c 1. R(i, j, 0) = 2... c l si {c 1, c 2,...,c l } = {c Σ, δ(i, c) = j} e i j ε c 1 c 2... c l si {c 1, c 2,...,c l } = {c Σ, δ(i, c) = j} e i = j 2. R(i, j, k + 1) = R(i, j, k) R(i, k, k) R(k, k, k) R(k, j, k). Notar que el Φ se usa para el caso en que l = 0. En el siguiente lema establecemos que la definición de las R hace lo que esperamos de ellas. Lema 2.1 R(i, j, k) es el conjunto de cadenas que reconoce M al pasar del estado i al estado j usando como nodos intermedios solamente nodos numerados < k. Prueba: Para el caso base, la única forma de ir de i a j es mediante transiciones directas entre los nodos, pues no está permitido usar ningún nodo intermedio. Por lo tanto sólamente podemos reconocer cadenas de un carácter. Si i = j entonces también la cadena vacía nos lleva de i a i. Para el caso inductivo, tenemos que ir de i a j pasando por nodos numerados hasta k. Una posibilidad es sólo usar nodos < k en el camino, y las cadenas resultantes son R(i,j,k). La otra es usar el nodo k una ó más veces. Entre dos pasadas consecutivas por el nodo k, no se pasa por el nodo k. De modo que partimos el camino entre: lo que se reconoce antes de llegar a k por primera vez (R(i,k,k)), lo que se reconoce al ir (dando cero ó más vueltas) de k a k (R(k,k,k) ), y lo que se reconoce al partir de k por última vez y llegar a j (R(k,j,k)). Del Lema 2.1 es bastante evidente lo apropiado de la siguiente definición. Indica que el lenguaje reconocido por el AFD es la unión de las R desde el estado inicial hasta los distintos estados finales, usando cualquier nodo posible en el camino intermedio. Definición 2.16 Sea M = (K, Σ, δ, s, F) con K = {0, 1,..., n 1} un AFD, y F = {f 1, f 2,..., f m }. Entonces definimos la ER er(m) = R(s, f 1, n) R(s, f 2, n)... R(s, f m, n). De lo anterior se deduce que es posible generar una ER para cualquier AFD, manteniendo el mismo lenguaje. Teorema 2.3 Sea M un AFD, entonces L(er(M)) = L(M). Prueba: Es evidente a partir del Lema 2.1 y del hecho de que las cadenas que acepta un AFD son aquellas que lo llevan del estado inicial a algún estado final, pasando por cualquier estado intermedio.

28 28 CAPÍTULO 2. LENGUAJES REGULARES Ejemplo 2.18 Consideremos el AFD del Ej. 2.7 y generemos er(m). er(m) = R(0,1,2) R(0,1,2) = R(0,1,1) R(0,1,1) R(1,1,1) R(1,1,1) R(0,1,1) = R(0,1,0) R(0,0,0) R(0,0,0) R(0,1,0) R(1,1,1) = R(1,1,0) R(1,0,0) R(0,0,0) R(0,1,0) R(0,1,0) = b R(0,0,0) = a ε R(1,1,0) = a ε R(1,0,0) = b R(1,1,1) = a ε b (a ε) b = a ε ba b R(0,1,1) = b (a ε) (a ε) b = a b R(0,1,2) = a b a b (a ε ba b) (a ε ba b) er(m) = a b(a ba b) Notar que nos hemos permitido algunas simplificaciones en las ERs antes de utilizarlas para R s superiores. El resultado no es el mismo que el que obtuvimos a mano en el Ej. 2.1, y de hecho toma algo de tiempo convencerse de que es correcto. Como puede verse, no es necesario en la práctica calcular todas las R(i, j, k), sino que basta partir de las que solicita er(m) e ir produciendo recursivamente las que se van necesitando. Por último, habiendo cerrado el triángulo, podemos establecer el siguiente teorema fundamental de los lenguajes regulares. Teorema 2.4 Todo lenguaje regular puede ser especificado con una ER, o bien con un AFND, o bien con un AFD. Prueba: Inmediato a partir de los Teos. 2.1, 2.2 y 2.3. De ahora en adelante, cada vez que se hable de un lenguaje regular, se puede suponer que se lo tiene descrito con una ER, AFND o AFD, según resulte más conveniente. Ejemplo 2.19 El desafío del Ej. 2.4 ahora es viable en forma mecánica, aplicando er al AFD del Ej Toma trabajo pero puede hacerse automáticamente. 2.7 Propiedades de Clausura [LP81, sec 2.4 y 2.6] Las propiedades de clausura se refieren a qué operaciones podemos hacer sobre lenguajes regulares de modo que el resultado siga siendo un lenguaje regular. Primero demostraremos algunas propiedades sencillas de clausura.

29 2.8. LEMA DE BOMBEO 29 Lema 2.2 La unión, concatenación y clausura de lenguajes regulares es regular. Prueba: Basta considerar ERs E 1 y E 2, de modo que los lenguajes L 1 = L(E 1 ) y L 2 = L(E 2 ). Entonces L 1 L 2 = L(E 1 E 2 ), L 1 L 2 = L(E 1 E 2 ) y L1 = L(E 1 ) son regulares. Una pregunta un poco menos evidente se refiere a la complementación e intersección de lenguajes regulares. Lema 2.3 El complemento de un lenguaje regular es regular, y la intersección y diferencia de dos lenguajes regulares es regular. Prueba: Para el complemento basta considerar el AFD M = (K,Σ,δ,s,F) que reconoce L, y ver que M = (K,Σ,δ,s,K F) reconoce L c = Σ L. La intersección es inmediata a partir de la unión y el complemento, L 1 L 2 = (L c 1 Lc 2 )c. La diferencia es L 1 L 2 = L 1 L c 2. Observación 2.7 Es posible obtener la intersección en forma más directa, considerando un AFD con estados K = K 1 K 2. Es un ejercicio interesante imaginar cómo opera este AFD y definirlo formalmente. Ejemplo 2.20 Es un desafío obtener directamente la ER de la diferencia de dos ERs. Ahora tenemos que esto puede hacerse mecánicamente. Es un ejercicio interesante, para apreciar la sofisticación obtenida, indicar paso a paso cómo se haría para obtener la ER de L 1 L 2 a partir de las ERs de L 1 y L 2. Ejemplo 2.21 Las operaciones sobre lenguajes regulares permiten demostrar que ciertos lenguajes son regulares con más herramientas que las provistas por ERs o autómatas. Por ejemplo, se puede demostrar que los números decimales correctamente escritos (sin ceros delante) que son múltiplos de 7 pero no múltiplos de 11, y que además tienen una cantidad impar de dígitos 4, forman un lenguaje regular. Llamando D = , M 7 al AFD del Ej. 2.11, M 11 a uno similar para los múltiplos de 11, y E 4 a una ER similar a la del Ej. 2.1 pero que cuenta 4 s, el lenguaje que queremos es ((L(M 7 ) L(M 11 )) L(E 4 )) L(0 D ). Se atreve a dar una ER o AFND para el resultado? (no es en serio, puede llevarle mucho tiempo). 2.8 Lema de Bombeo [LP81, sec 2.6] Hasta ahora hemos visto diversas formas de mostrar que un lenguaje es regular, pero ninguna (aparte de que no nos funcione nada de lo que sabemos hacer) para mostrar que no lo es. Veremos ahora una herramienta para demostrar que un cierto L no es regular. Observación 2.8 Pregunta capciosa: Esta herramienta que veremos, funciona para todos los lenguajes no regulares? Imposible, pues hay más lenguajes no regulares que demostraciones!

Sitemap