´ TEOR´IA DE AUTOMATAS Y LENGUAJES FORMALES Grado en Ingenier´ıa Inform´atica Online, Curso 2012-2013 Universidad Rey Juan Carlos ´ DE LA HOJA DE PROBLEMAS No 3 GU´IA PARA LA REALIZACION (Tema 3: Expresiones Regulares) EJERCICIOS 1 y 2 Se trata en ambos casos de describir mediante expresiones regulares lenguajes dados en notaci´on conjuntista. Estos ejercicios no tienen una soluci´on u ´ nica, puesto que pueden obtenerse como resultado expresiones regulares distintas entre s´ı pero equivalentes. En los apuntes del tema se han resuelto ejercicios similares. A continuaci´on se discuten algunos de los ejercicios de esta hoja m´as interesantes: Ejercicio 1 (c). El conjunto dado est´a formado por todas las palabras w ∈ {0, 1}∗ tales que n0 (w) MOD 2 6= 0, es decir, que contienen un n´ umero impar de ceros, o, lo que es lo mismo, verifican n0 (w) MOD 2 = 1. Estas palabras pueden verse como la concatenaci´on de una palabra que contiene exactamente un cero (1∗ 01∗ ), seguida de cero o m´as palabras conteniendo exactamente dos ceros (1∗ 01∗ 01∗ ): si no se pone ninguna de estas u ´ ltimas se obtiene una palabra final con 1 cero; si se pone una, se obtiene una palabra con 3 ceros; si se ponen dos, la palabra final tendr´a 5 ceros, etc. En definitiva, una soluci´on al problema puede ser la siguiente expresi´on regular: 1∗ 01∗ (1∗ 01∗ 01∗ )∗ Ejercicio 1 (e). Una opci´on para resolver este ejercicio es dividir el conjunto dado en la uni´on de cuatro conjuntos (uno para cada posible valor de m, m ∈ 0 . . . 3), encontrar una ER para cada uno de estos lenguajes y finalmente componer todas las ERs anteriores mediante el operador “+”. Ejercicio 1 (h). La condici´on na (w) MOD 5 6= 0 es equivalente a na (w) MOD 5 = i para alg´ un i ∈ {1, 2, 3, 4}, por lo que se tiene la siguiente igualdad: L = ∪4i=1 {w ∈ {a, b}∗ | na (w) MOD 5 = i}. Por ello, una posibilidad es encontrar ERs para cada uno de los cuatro lenguajes anteriores y posteriormente unirlas mediante “+”. Estos lenguajes son similares al discutido en el ejercicio 1(c): por ejemplo, si se denota r1 = b∗ ab∗ (palabras con exactamente una a) y r5 = b∗ ab∗ ab∗ ab∗ ab∗ ab∗ (palabras con exactamente cinco a’s), resulta que la ER r1 r5∗ describe el lenguaje {w ∈ {a, b}∗ | na (w) MOD 5 = 1}. Ejercicio 2 (b). El conjunto de cadenas que no contienen m´as de tres a’s se puede dividir en cuatro subconjuntos, formados por las palabras que contienen exactamente cero, una, dos o tres a’s. Ejercicio 2 (c). Si se denota r = (a + b + c)∗ , la ER rarbrcr describe todas las cadenas que contienen al menos una ocurrencia de cada s´ımbolo, pero obliga a que detr´as del 1

u ´ ltimo s´ımbolo a haya al menos un s´ımbolo b, y detr´as de este al menos una c. Es decir, faltar´ıan palabras como por ejemplo acb, bac, etc. El problema es que el orden en el que aparecen los s´ımbolos, a → b → c, no es m´as que una de las 3! = 6 posibles permutaciones de los tres s´ımbolos, por lo que habr´ıa que a˜ nadir ERs para los otros cinco casos. Ejercicio 2 (d). Una opci´on es dividir el conjunto de palabras que no terminan en abab en varios subconjuntos: el formado por la palabra vac´ıa, el formado por todas las palabras que terminan en a, el formado por todas las palabras que terminan en c, el formado por todas las palabras que terminan en bb, el formado por todas las palabras que terminan en cb, lo mismo para la terminaci´on aab, etc. No olvide que las palabras b, ab y bab tambi´en pertenecen al lenguaje. EJERCICIOS 3 y 4 Estos ejercicios tratan el problema inverso: dada una ER, encontrar el lenguaje que describe. La soluci´on en este caso es u ´ nica. EJERCICIOS 5 - 13 Se trata en todos los casos de aplicar el algoritmo [AFND ⇒ ER] de los apuntes, basado en el m´etodo de las ecuaciones caracter´ısticas. EJERCICIO 14 y 15 Para resolver estos problemas hay que realizar los siguientes pasos: 1. Obtener un AFND equivalente a la ER dada aplicando el algoritmo [ER ⇒ AFND]. 2. Obtener un AFD equivalente al AFND obtenido en el paso anterior aplicando el algoritmo [AFND ⇒ AFD] (tema 2.3). 3. Como el algoritmo [AFND ⇒ AFD] no garantiza que el AFD obtenido sea m´ınimo, a continuaci´on habr´a que aplicar el algoritmo de minimizaci´on (tema 2.1.) al AFD obtenido en el paso anterior. Como ya se ha explicado en el tema anterior, por comodidad en la aplicaci´on del algoritmo de minimizaci´on, se podr´a hacer un renombramiento de estados tras el algoritmo [AFND ⇒ AFD]. EJERCICIOS 16-19 Para resolver estos ejercicios hay que realizar los siguientes pasos: 1. Transformar los elementos dados en sus AFDs m´ınimos equivalentes, para lo cual habr´a que: a) Aplicar los algoritmos adecuados a cada uno de los elementos de partida para obtener un AFD equivalente: Algoritmo [AFND ⇒ AFD] en el caso de los AFNDs. Algoritmos ([GLD ⇒ AFND] + [AFND ⇒ AFD]) en el caso de las GLDs. Algoritmos ([ER ⇒ AFND] + [AFND ⇒ AFD]) en el caso de las ERs. 2

b) Minimizar el AFD obtenido en el paso anterior (previo renombramiento de sus estados) aplicando el algoritmo de minimizaci´on de AFDs del tema 2.1. 2. Los AFNDs/GLDs/ERs de partida son equivalentes (es decir, describen el mismo lenguaje) si y s´olo si los AFDs m´ınimos obtenidos en el paso anterior son isomorfos (es decir, iguales salvo en el nombre de los estados). A continuaci´on se detalla la resoluci´on del ejercicio 17: Obtenci´on del AFD m´ınimo equivalente al AFND A dado en el enunciado. Como podemos observar, el aut´omata proporcionado es un aut´omata finito no determinista, por lo tanto, para minimizarlo, en primer lugar deberemos hallar un aut´omata finito determinista equivalente. Para ello, se aplica el algoritmo [AFND ⇒ AFD], partiendo de f ∗ (p, λ) = {p, v, w}, que ser´a el estado inicial de nuestro nuevo aut´omata. Despu´es, procederemos con el algoritmo, descubriendo los estados a los que vamos transitando con cada uno de los s´ımbolos del alfabeto de entrada, obteniendo finalmente el siguiente AFD: fF D →{p,v,w} *{p,r,t,v,w} {q,u} {q} *{p,s,v,w}

0 {p,r,t,v,w} {p,r,t,v,w} {q} {q} {p,r,t,v,w}

1 {q,u} {q,u} {p,s,v,w} {p,s,v,w} {q,u}

Despu´es, renombraremos los estados para trabajar m´as c´omodamente con ellos, de forma que obtenemos el siguiente aut´omata finito determinista equivalente: AF D = ({A, B, C, D, E}, {0, 1}, fF D, A, {B, E}) fF D 0 1 →A B C *B B C C D E D D E *E B C Posteriormente, minimizaremos el aut´omata para obtener el finito determinista m´ınimo (y u ´ nico) que reconoce ese lenguaje. En primer lugar, eliminaremos los estados inaccesibles que tenga (ninguno en este caso). En segundo lugar, hallaremos el conjunto de clases de equivalencia de estados. Q/E0 = {{B, E}, {A, C, D}} Q/E1 = {{B, E}, {A}, {C, D}} 3

Q/E2 = {{B, E}, {A} , {C, D}} = Q/E1 = Q/E | {z } |{z} | {z } B

A

C

Los estados B, E resultan ser equivalentes, al igual que los estados C, D. Por lo tanto, de cada uno de los conjuntos de estados equivalentes tomamos un representante: tomaremos B como representante de la clase de equivalencia {B, E}, tomaremos A como representante de la clase de equivalencia {A} y tomaremos C como representante de la clase de equivalencia {C, D}. De esta manera, reescribiendo la tabla de transiciones en funci´on de los representantes elegidos, obtenemos el aut´omata finito determinista m´ınimo equivalente al aut´omata no determinista que nos se˜ nalan en el enunciado:

AF Dmin = ({A, B, C}, {0, 1}, fF Dmin, A, {B}) fF Dmin 0 1 →A B C *B B C C C B Obtenci´on del AFD m´ınimo equivalente a la ER E dada en el enunciado. Como podemos observar al analizar la expresi´on regular, las palabras definidas por (1(00)∗01) (palabras que empiezan y terminan con un uno y tienen entre medias un n´ umero impar de ceros) son un subconjunto de las definidas por (0 + 10∗ 1)∗ (0 + ∗ 10 1), ya que la expresi´on anterior incluye, en particular, a las palabras 10∗ 1, es decir, palabra que empiezan y terminan con un uno y tienen entre medias cualquier n´ umero de ceros. Por ello, la segunda parte de la expresi´on no aporta nada, es decir, la expresi´on dada es equivalente a ((0 + 10∗ 1)∗ (0 + 10∗ 1)). Para obtener un AFND equivalente a la expresi´on anterior se debe aplicar el algoritmo [ER ⇒ AFND]. Teniendo en cuenta que muchas de las transiciones λ impuestas por el algoritmo son en este caso concreto innecesarias, el AFND obtenido tras aplicar el algoritmo resulta equivalente al siguiente: λ 0

p 1

q 1

r 0

Aer = ({p, q, r}, {0, 1}, fer , p, {q}) 0 fer →p {q} *q r {r} 4

1 {r}

λ {p}

{q}

El siguiente paso es hallar un aut´omata finito determinista equivalente para poder minimizarlo. Por lo tanto, aplicaremos el mismo algoritmo que hemos visto anteriormente, [AFND ⇒ AFD], esta vez partiendo de f ∗ (p, λ) = {p}. El AFD resultante es el siguiente: ferf d 0 →{p} {p,q} *{p,q} {p,q} {r} {r}

1 {r} {r} {p,q}

Lo renombraremos para trabajar m´as c´omodamente: Aerf d = ({P, Q, R}, {0, 1}, ferf d, P, {Q}) ferf d 0 →P Q *Q Q R R

1 R R Q

Ahora, intentaremos minimizar el aut´omata. Primero, eliminaremos los estados inaccesibles que tenga (ninguno en este caso). Despu´es, hallaremos el conjunto de clases de equivalencia de estados: Q/E0 = {{Q}, {P, R}} Q/E1 = {{Q}, {P }, {R}} Q/E2 = {{Q}, {P }, {R}} = Q/E1 = Q/E Visto el resultado, determinamos que el aut´omata analizado ya era m´ınimo. Por lo tanto, procederemos a comparar ambos aut´omatas finitos m´ınimos. fF Dmin 0 1 →A B C *B B C C C B

ferf d 0 1 →P Q R *Q Q R R R Q

Comparaci´on de los AFDs m´ınimos obtenidos en los pasos anteriores. Como podemos comprobar, los aut´omatas AF Dmin y Aerf d son isomorfos (iguales salvo en lo que respecta al nombre de los estados), por lo tanto, queda demostrado que ambos elementos generan el mismo lenguaje.

5