teoria de automatas y lenguajes formales

Teora de Autmatas y Lenguajes FormalesVersion 2

Dr. Arno FormellaUniversidad de Vigo

Departamento de Informticarea de Lenguajes y Sistemas Informticos

E-32004 Ourense

http://www.ei.uvigo.es/[email protected]

11 de junio de 2006

Dr. Arno Formella 2

ndice1. Curso 4

2. Sobre este documento 42.1. Versiones y lista de correcciones . . . . . . . . . . . . . . . . . . . . . . . . . . 5

3. Introduccin 5

4. Conceptos bsicos 84.1. Alfabetos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94.2. Palabras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94.3. Lenguajes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124.4. Producciones y Derivaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144.5. Relaciones de equivalencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154.6. Relacin de equivalencia de lenguajes . . . . . . . . . . . . . . . . . . . . . . . 17

5. Gramticas generativas 175.1. Ejemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185.2. Abreviacin de Backus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215.3. rbol de derivacin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225.4. Jerarquia de Chomsky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225.5. Equivalencia y ambigedad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

6. Autmatas finitos 256.1. Autmatas finitos deterministas (AFD) . . . . . . . . . . . . . . . . . . . . . . . 256.2. Autmatas finitos nodeterministas (AFND) . . . . . . . . . . . . . . . . . . . . 286.3. Equivalencia entre AFD y AFND . . . . . . . . . . . . . . . . . . . . . . . . . . 296.4. Autmatas finitos nodeterministas con transiciones (AFND) . . . . . . . . . 346.5. Equivalencia entre AFND y AFND . . . . . . . . . . . . . . . . . . . . . . . 376.6. Existencia de autmatas finitos mnimos . . . . . . . . . . . . . . . . . . . . . . 396.7. Ejemplos de uso del teorema de Myhill y Nerode . . . . . . . . . . . . . . . . . 416.8. Algoritmo de minimizacin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

7. Expresiones regulares 447.1. Sntaxis y semntica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457.2. Equivalencia entre autmatas finitos y expresiones regulares . . . . . . . . . . . 467.3. Abreviaciones para el uso de expresiones regulares . . . . . . . . . . . . . . . . 507.4. Smbolos y metasmbolos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

8. Lenguajes regulares 518.1. Equivalencia entre gramticas lineales por la derecha y autmatas finitos . . . . . 518.2. Equivalencia entre gramticas lineales por la derecha y lineales por la izquierda . 53

Dr. Arno Formella 3

8.3. Lema de bombeo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

9. Propiedades, algoritmos de decisin,y aplicaciones para lenguajes regulares 609.1. Propiedades de lenguajes regulares . . . . . . . . . . . . . . . . . . . . . . . . . 609.2. Algoritmos de decisin de lenguages regulares . . . . . . . . . . . . . . . . . . . 629.3. Aplicaciones para lenguajes regulares . . . . . . . . . . . . . . . . . . . . . . . 63

10. Lenguajes libres de contexto 6310.1. Forma Normal de Chomsky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6410.2. Forma Normal de Greibach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7210.3. Lema de bombeo para lenguajes libres de contexto . . . . . . . . . . . . . . . . 74

11. Autmatas finitos con pila (AFP) 7611.1. Motivacin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7611.2. Autmatas finitos con pila nodeterministas (AFPND) . . . . . . . . . . . . . . 7711.3. Equivalencia entre AFPNDs aceptando con pila vaca y aceptando en estado final 8111.4. Equivalencia entre AFPNDs y gramticas libres de contexto . . . . . . . . . . . 8311.5. Autmatas finitos con pila deterministas (AFPD) . . . . . . . . . . . . . . . . . 86

12. Propiedades, algoritmos de decisin,y aplicaciones para lenguajes libres de contexto 8712.1. Propiedades de lenguajes libre de contexto . . . . . . . . . . . . . . . . . . . . . 8712.2. Algoritmos de decisin de lenguages libres de contexto . . . . . . . . . . . . . . 8812.3. Aplicaciones para lenguajes libres de contexto . . . . . . . . . . . . . . . . . . . 89

13. Mquinas de Turing (MT) 89

14. Resumen 89

15. Bibliografa 9015.1. Bibliografa bsica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9015.2. Bibliografa usada para la preparacin . . . . . . . . . . . . . . . . . . . . . . . 90

Dr. Arno Formella 4

1. Curso

Asignaturas vecinas: todo sobre Programacin, lgebraPrerrequisitos: ningunos, excepto conceptos matemticos bsicosEvaluacin: 70 % con un examen escrito al final del curso, teora y 30 %

de las prcticasCrditos: 6 (4.5 teora, 1.5 prcticas)Bibliografa: mira Bibliografa

2. Sobre este documento

Este documento es un servicio adicional del profesor para los estudiantes. Se recuerda que laasignatura es presencial. Observa los siguientes comentarios importantes:

Los apuntes

no necesariamente estn completos. El contenido de la asignatura se define por lo que seexpone durante las clases presenciales.

no necesariamente son correctos. Intento lo mejor. Sobre todo siempre existe la posibili-dad que haya fallos ortogrficos o de redaccin. Adems, como en todos los campos de lainformtica, lo correcto no es lo que diga el profesor, lo correcto es, lo que es correcto.

no necesariamente siguen el orden de las clases presenciales. Es posible que el ordende los apartados no es exactamente igual que el orden presentado en clases.

contienen apartados que no se han dado en todos los cursos. Siendo clases presenciales,los estudiantes ya sabrn distinguir.

todava estn sin grficos.

Los apuntes se han escrito sin el uso de una enumeracin explcita de las definiciones, lemas, yteoremas, como se suele usar en tal contexto. Se anima al lector que estructure su novela indi-vidual con notas en los mrgenes para enumerar las definiciones, lemas, y teoremas y relacionaras de mejor manera las diferentes partes.

Dr. Arno Formella 5

2.1. Versiones y lista de correcciones

A parte de algunas correcciones de ortografa se ha realizado las siguientes cambios de versinen versin:

Version 2

(Seccin 4.6) mejorado la precisin de la observacin (Seccin 8) Si (q, ) = p es una transicin del AFD, con q Q, p F y ,

entonces aadimos a P la produccin q . (Seccin 8) Entonces el sistema de producciones P de la gramtica ser:

P = {q0 aq0|a|bq1|b|cq2|c|, q1 bq1|b|cq2|c, q2 cq2|c}

(Seccin 10.1) Si el lenguaje de partida L contiene la palabra vaca ( L) entoncesse detecta en el pasa 4 que el smbolo inicial pertenece a E (o incluso a E), en estecaso eliminamos con un nuevo smbolo, por ejemplo $, la aparencia de $ en los ladosderechos y aadimos la regla $ . Tal gramtica sigue estando en forma normalde Chomsky y genera L.

(Seccin 10.2) Obviamente cualquier gramtica en forma normal de Greibach es unagramtica libre de contexto que se verifica directamente analizando la forma de pro-ducciones permitidas.

3. Introduccin

Porqu es importante la teora de lenguajes formales y autmatas?Bueno, aclaramos primero un poco las palabras usadas...

Qu es un lenguaje formal?Conocemos lenguajes naturales...

espaol, alemn, ingls, chino, rabe...

cuando nacemos no sabemos ninguno

se puede aprender cualquier lenguaje (por lo menos si se ha nacido en un entorno adecua-do)

Dr. Arno Formella 6

el lenguaje es una secuencia de fonemas o smbolos que forman slabas, palabras, frases, prrafos, captulos, novelas, libros, bibliotecas... que tiene una sntaxis (fontica o ortografa) que tiene una gramtica (reglas de concatenacin y construccin de palabras para

formar frases) (que tiene un estilo (forma de unir frases para generar textos))

Lenguajes formales sern meramente smbolos con una gramtica formal para agruparlos.Qu es un autmata?

dispositivos mecnicos o electrnicos o biolgicos

que en un punto de tiempo estn en un estado que dado una razn (por ejemplo una seal de entrada) cambian de estado

ejemplos son: reloj mecnico o electrnico, mquina para lavar, todo un ordenador, elcerebro?

ya se han construido relojes biolgicos con trozos de DNA artificial y sntesis de protenasque visualizan su cambio de estado con luz fluorescente

En el contexto de esta asignatura autmatas sern mquinas matemticas con estados y funcionesde transicin (donde se puede aadir entrada, salida, memoria interna modificable, etc.).En los aos 60 se descubri:

Los conceptos de gramticas (formales) y de los autmatas describen el mismo fenmenoy estn muy relacionados con los algoritmos

y de esta manera surgi la Teora de Computabilidad y la Teora de Complejidad, es de-cir, la bsqueda de respuestas a las preguntas: Qu es computable? y Cuntos recursos(memoria, espacio, tiempo, transiciones) se necesitan?

Es decir, la Teora de los Lenguajes Formales (y de los Autmatas) permite responder a preguntasescenciales de la Informtica, por ejemplo:

Tesis de Church: Todo lo que es computable se puede calcular con una Mquina de Turing.

Existen problemas que no son computables.

Dr. Arno Formella 7

Sin TALF: no hay lenguajes, no hay compiladores, no hay programas, no hay nada.Unos ejemplos:favoritas

Con este diagrama podemos formar unas reglas para sustituir smbolos:

$ AB A esos A B CDC son D EF E GH G misG H IJ I clases J favoritasJ F en informatica F

donde usamos para decir que no escribimos nada.

Con dichas reglas podemos derivar diferentes frases, por ejemplo:$ AB esosB esosCD esos sonD esos sonEF esos sonGHF esos sonHF esos sonH esos sonIJ esos son clasesJ esos son clases

donde siempre hemos usado una regla adecuada para sustituir smbolos hasta llegar a tal puntoque ya no se puede aplicar ninguna regla ms.

Y con pequeos arreglos podemos traducirlo al alemn:

$ AB A dies B CDC sind D EF E GH G meineG H JI I Vorlesungen J liebstenJ F in Informatik F

es decir, hemos quitado la regla A y hemos cambiado la regla de H IJ a H JI .Otro ejemplo mas sencillo.Usamos las reglas $ ab$ y $ ab para generar palabras del tipo ab, abab, ababab ...Podemos derivar una palabra:

Dr. Arno Formella 8

$ ab$ abab$ ababab$ ababab

siempre aplicando alguna de las reglas hasta tal punto que ya no se puede aplicar ninguna regla.

Construimos un autmata que acepta una palabra del tipo mencionado. Entendemos por aceptarque el autmata llega a su estado final. Consumimos para cada transicin de estado una letra dela palabra. Podemos dibujar un autmata:automata

donde el estado inicial (o de comienzo) est marcado con una flecha, el estado final est marcadocon un doble crculo. Las transiciones estn visualizadas con arcos entre los estados que a suvez estn marcados con sus smbolos correspondientes. Si empezamos en el estado inicial, y sileemos la palabra por aceptar desde la izquierda hacia la derecha, podemos saltar de estado aestado siguiendo los arcos adecuados.

Observamos que llegamos solamente al estado final si la palabra por aceptar es una palabra vlidadel lenguaje.Vemos y veremos

que las gramticas sirven para generar palabras (y con eso lenguajes) yque los autmatas sirven para aceptar palabras (y con eso lenguajes).

Hacia el final del curso tendremos conocimientos sobre una jerarqua de lenguajes y las equiva-lencias entre:

Lenguajes Tipo 3, Gramticas Regulares y Autmatas Finitos,Lenguajes Tipo 2, Gramticas Libres de Contexto y Autmatas Finitos con Pila,(Lenguajes Tipo 1, Gramticas Sensitivos al Contexto y Autmatas Linealmente Acota-dos),Lenguajes Tipo 0, Gramticas Generales y Mquinas de Turing.

4. Conceptos bsicos

Dr. Arno Formella 9

4.1. Alfabetos

Un alfabeto es un conjunto finito no vaco de smbolos.

1 = {0, 1}2 = {a, b}3 = {na, pa, bra, la}4 = {,,,, . . .}5 = {|}6 = {a, ab, aab}

Usamos metasmbolos (tal como {, }, =, y la coma) para escribir sobre lo que hablamos.Desde el contexto siempre ser claro, si se trata de un smbolo del alfabeto o si se trata deun metasmbolo.

Usamos subndices para distinguir diferentes alfabetos.

Usamos normalmente las minsculas como alfabeto = {a, . . . , z}, en los ejemplos nor-malmente letras desde el principio del alfabeto.

Cardinalidad del alfabeto (nmero de elementos del alfabeto): || > 0, ||

Dr. Arno Formella 10

La longitud de una palabra sobre un alfabeto es el nmero de smbolos que contiene.

1 : w = 0 = |w| = 1, w = 1001101 = |w| = 72 : w = a = |w| = 1, w = ababa = |w| = 53 : w = napa = |w| = 2, w = palabra = |w| = 36 : w = ab = |w| = 2, w = aab = |w| = 1 o |w| = 2 ??

Dependiendo del alfabeto puede resultar difcil dividir una palabra en sus smbolos.

Si se puede dividir todas las palabras sobre un alfabeto solamente de una manera en sussmbolos, se llama tal alfabeto libre.

Solemos usar solamente alfabetos libres.

|| = 0

El conjunto de todas las palabras que se pueden formar sobre un alfabeto ms la palabra vacase llama el universo del alfabeto W ().

W () = {} {w | w es palabra sobre } W () es palabra de cualquier universo, W ().La cardinalidad del universo es infinito (pero contable o enumerable, vemos ms adelantelo que significa).Si el alfabeto es libre (o mejor decir, un generador libre), escribimos por W ().

Podemos concatenar palabras, entonces sean w, v y u palabras en .

w.v = wv, es decir, usamos el . como smbolo de concatenacin, pero muchas vecesobviamos de l (igual como se suele hacer con el de la multiplicacin).w = w = w, es decir, se comporta como el elemento neutro (o elemento de intentidad)respecto a la concatenacin.

|w.v| = |w|+ |v|


w.v 6= v.w para cualquier w y v, por ejemplo:w = abc v = dec wv = abcdec 6= decabc = vw

es decir, la concatenacin no es conmutativa.

(w.v).u = w.(v.u) para cualquier palabras w, v y u, por ejemplo:w = abc v = dec u = fad

(wv)u = (abcdec)fad = abcdecfad = abc(decfad) = w(vu)

es decir, la concatenacin es asociativa (usamos arriba las parntesis como metasmbolos).Con dichas propiedades la estructura algebraica (, . ) forma un monoide libre (es decir,un semigrupo con elemento de intentidad).

Si xy = w, llamamos x prefijo de w e y sufijo de w.

Por w = w y w = w, es por lo tanto prefijo y sufijo (trivial) de cualquier palabra, y w esprefijo y sufijo trivial de si mismo. (Normalmente no consideramos estos casos triviales.)Si x es prefijo de w entonces |x| |w|.Si y es sufijo de w entonces |y| |w|.Si x es prefijo de w, e y es sufijo de w y x = y, entonces x = y = w, es verdad?

Si concatenamos siempre la misma palabra w, obtenemos potencias de w.

ww = w2, www = w3, w . . . w i-veces

= wi, i IN = {0, 1, 2, }

w1 = w, w0 =

|wi| = i |w||w0| = || = 0 = 0 |w| = |w0|wm+n = wm.wn

|wm+n| = (m+ n) |w| = m |w|+ n |w| = |wm|+ |wn|

La reflexin de una palabra w (o la palabra reversa) anotamos como wR.

|w| = |wR| = R


4.3. LenguajesUn lenguaje es cualquier subconjunto del universo sobre algn alfabeto, es decir, L W (), otambin L .Ejemplo:

Lenguajes triviales L = es el lenguaje vacio (que no contiene ninguna palabra), |L| = 0 L = {} es el lenguaje que solamente contiene la palabra vacio, |L| = 1

son independientes del alfabeto y por eso son lenguajes sobre cualquier alfabeto.sea = {a, b} L1 = {, a, b} Lab = {anbn | n IN} es decir, el lenguaje que contiene todas las palabras con un

nmero de as seguidos por el mismo nmero de bs. Lpal = {wwR | w } es decir, palndromos Lquad = {an2 | n IN>0}

Si |L|


Complemento:

L = {w | w y w / L}Propiedades (unos ejemplos):Regla de DeMorgan: L1 L2 = L1 L2

L1 L2 = L1 L2Con estas tres operaciones la estructura (,,, ) forma una lgebra booleana.

Diferencia:

L1 L2 = {w | w L1 pero w / L2}Propiedades (unos ejemplos):

L1 = L1

L1 L2 = L1 L2)Concatenacin:

L1.L2 = {w | w = w1.w2 y w1 L1 y w2 L2}Propiedades (unos ejemplos):NoConmutatividad: L1.L2 6= L2.L1 (en general)Operacin con : L1. = L1 = .L1Operacin con {}: L1.{} = L1 = {}.L1

Potencia:

Li = L . . . L i-veces

i IN

Propiedades (unos ejemplos):CeroPotencia: L0 = {}Induccin: Li.L = Li+1 = L.Li

Clausura positiva:

L+ =i=1

Li = L1 L2 L3 . . .

Clausura (de Kleene):

L =i=0

Li = L0 L1 L2 . . .

Propiedades (unos ejemplos):L+ = L {} =

i=0

i


Reflexin (o inverso):

L = {w | wR L}

Homomorfismo: Sean , dos alfabetos. Sea : una funcin que asigna a cadasmbolo de una palabra sobre . Podemos ampliar la funcin a un homomorfismo : , es decir, una funcin que asigna a cada palabra sobre una palabra sobre, con

() =

(w) = (w)()

Ejemplo: = {a, b, c, d} = {0, 1}

(a) = 00 (b) = 1 (c) = (d) = 0110

(abcd) = 0010110

Entonces si L es un lenguaje sobre (L) = {(w) | w L}

es un lenguaje sobre y si L es un lenguaje sobre , entonces1(L) = {w | 1(w) L}

es un lenguaje sobre .

Cul es el orden de prioridad de estos operadores?

4.4. Producciones y Derivaciones

Definimos algunas notaciones para describir reglas de sustitucin, es decir, como derivar unapalabra con las producciones de la gramtica:

Una produccin p es una tupla de un conjunto cartesiano sobre dos universos (que pueden ser elmismo), es decir, p = (A,B) 1 2.Sea (A,B) una produccin, en vez de tuplas tambin escribimos: A B.Un conjunto de producciones se llama sistema de producciones (o sistema de reglas). A estenivel todava no decimos mucho sobre los alfabetos involucrados, ms adelante concretaremos.


Una derivacin directa v w es una conversin de una palabra en otra aplicando una produc-cin, es decir, sea por ejemplo v = aAb una palabra, y sea A B una produccin, entoncesse puede derivar la palabra w = aBb directamente desde v sustituyendo la subpalabra A por lapalabra B como indica la produccin.

Ejemplo: Sean 000 010 y 10 01 dos producciones. Desde v = 1000 se puede derivarw1 = 1010 aplicando la primera produccin, y w2 = 0100 aplicando la segunda.

Una derivacin v w es una secuencia de derivaciones directa aplicando sucesivamenteproducciones de un sistema. La longitud de una derivacin es el nmero de producciones apli-cadas.

Ejemplo: Sean 000 010 y 10 01 dos producciones. Desde v = 1000 se puede derivarw1 = 0011, es decir, v w1 aplicando v = 1000 1010 0110 0101 0011 =w1, o tambin w2 = 0001 aplicando v = 1000 0100 0010 0001 = w2. En el primercaso la longitud de la derivacin es 4, en el segundo caso 3.

Comentario importante: muchas de las comprobaciones en el mbito de la teora de los lengua-jes formales se realiza mediante induccin sobre: longitud de la palabra, longitud de la derivacin,(o luego tambin longitud del clculo).Dado un sistema de producciones, si sustituimos siempre la primera posibilidad a la izquierda dela palabra de partida, se llama una derivacin ms a la izquierda, e igual, si sustituimos siemprela primera posibilidad a la derecha de la palabra de partida, se llama una derivacin ms a laderecha.

4.5. Relaciones de equivalencia

Un conjunto R es una relacin (binaria sobre ).Escribimos los pares siendo elementos de R como (x, y), o como x y, o como xRy.Sean R y S dos relaciones. Definimos

RS = {(x, y) | z : xRz y zSy}R0 = {(x, x) | x }

Rn+1 = RRn

es decir, R0 es la relacin de identidad, y la operacin nos permite crear nuevas relaciones apartir de dos relaciones dadas, y Rn+1 es una relacin construida de tal manera recursivamente.Con eso definimos:

R =n0

Rn

R+ =n1

Rn


es decir, xRy (o en otra notacin x y) si x = y o existe una secuencia z1, z2, . . . , zn conn 1 y xRz1, z1Rz2, . . . , znRy.Una relacin R es

reflexiva, si x : xRx, es decir, la relacin de identidad R0 es subrelacin de R,transitiva, si xRy, yRz = xRz, es decir, si los pares (x, y) y (y, z) son elementos de Rentonces (x, z) tambin lo es,

simtrica, si x, y : xRy yRx, es decir, con (x, y) tambin (y, x) es elemento de larelacin.

Observamos que para R

R es una relacin reflexiva y transitiva, llamada la clausura reflexiva y transitiva de R(porque es la relacin ms pequea con tal propiedad).R+ es una relacin transitiva, llamada la clausura transitiva de R (porque es la relacinms pequea con tal propiedad).R+ es tambin reflexiva si R ya lo es.

R y R+ son simtricas si R ya lo es.

Una relacion R es una relacin de equivalencia si R es reflexiva, simtrica, y transitiva.

Sea R una relacin de equivalencia. A cada elemento de podemos asignar el conjunto delos elementos que son equivalentes a l. Basta con anotar un representente de dicho conjunto yescribimos

[x]R = {y | yRx} = {y | xRy}(si desde el contexto ya conocemos R, obviamos del subindice R).Si xRy entonces [x] = [y] porque ambos caen en la misma clase de equivalencia. Se suele usarcomo representante una de las palabras ms cortas de la clase.

Si x, y [z] escribimos tambin x y que significa que xRy e yRx.Una relacin de equivalencia divide en clases, es decir,

= [x1] [x2] . . . [xk] . . .

cuyo nmero es finito o infinito. La interseccin de dos clases es vaca, es decir, [xi] [xj] = si i 6= j porque si tuviesen un elemento en comn, ambas clases seran iguales.Ejemplo: Sea = {1, . . . , k} un alfabeto (por ejemplo el alfabeto de toda la vida).


La relacinR = {(x, y) | x comienza con el mismo smbolo que y}

es una relacin de equivalencia y nos divide en

= [1] [2] . . . [k] []

es decir, en todas las clases de palabras que empiezan con la misma letra ms la clase para lapalabra vaca (que no empieza con ninguna letra).Entonces hay tantas clases como smbolos en ms una clase.

Llamamos el nmero de clases que produce una relacin de equivalencia el ndice de la relacinIndice(R).

En el ejemplo tenemos Indice(R) = k + 1 = ||+ 1, es decir, un ndice finito.

4.6. Relacin de equivalencia de lenguajesPara cada lenguaje L podemos construir una relacin de equivalencia sobre :

xRLy (z : xz L yz L)

es decir, x es equivalente a y, si, aadiendo cualquier sufijo, ambas palabras resultantes o bienestn en L o bien no estn en L.

Observa: z = : x L y L, es decir, o bien todas las palabras de una clase estn en Lo bien ninguna palabra de una clase est en L.

Ejercicio:Verifica que RL es una relacin de equivalencia!

5. Gramticas generativas

Una gramtica es una cudrupla

G = (N ,T , P, $)

donde


N es un alfabeto de smbolos noterminales.

T es un alfabeto de smbolos terminales.

Se exige N T = y se suele usar = N T .P es un sistema de producciones finitos, donde se distingue varios casos, ejemplos son: P (N T ) (N T )

caso muy general, (as no hara falta distinguir los dos alfabetos a la primera vista, esdecir, P )

P .+N . es decir, a la derecha existe por lo menos un smbolo noterminal

P N es decir, se sustitue solamente smbolos (palabras) noterminales

P N (N T )es decir, se sustitue solamente smbolos (palabras) noterminales, pero por smbolos(palabras) o bien terminales o bien noterminales

Repetimos: se exige que |P |


L1 = {, a, b}G1 = ({$}, {a, b}, {$ , $ a, $ b}, $)

obviamente L(G1) = L1

para lenguajes finitos es fcil generar una gramtica, basta con derivar directamente cadapalabra desde el smbolo inicial (aunque se puede usar un sistema de producciones mssofisticado)

Una gramtica recursiva sobre la palabra v es una gramtica donde se puede derivardesde v una palabra que contiene v de nuevo, es decir, existe la posibilidad de una derivacin:v uvw (con |v| < |uvw|).El lenguaje generado por una gramtica es infinito, si la gramtica es recursiva sobre una palabrav y que a su vez es derivable desde el smbolo inicial.

Lab = {anbn | n IN}Gab = ({a, b}, {$}, {$ a$b, $ }, $)

Labc = {anbncn | n IN}, abc, aabbcc, aaabbbccc, . . . Labc

Gabc = ({$, . . .}, {a, b, c}, P, $)

Cules son las producciones necesarias?

Una vez sabiendo eso, podemos completar el alfabeto noterminal N

Una primera idea:

P = {$ , $ ABC,A , A aA,B , B bB,C , C cC}

N = {$, A,B,C}

Obviamente podemos derivar cualquier elemento de Labc con esa gramtica, por ejemplo:$ ABC aABC aaABC aaBC aabBC aabbBC aabbC aabbcC aabbccC aabbcc


Pero tambin podemos derivar palabras como aaabcccc, es decir, el lenguaje esL(GTest) = {aibjck | i, j, k IN} Labc

Parece que la gramtica GTest es demasiado amplia. De alguna manera deberamos con-struir un sistema de producciones que permite mantener un nmero igual de letras a, b y c(o en otras palabras, necesitamos contar)...Idea 1: Si somos capaz de derivar desde akXbkck la secuencia ak+1Xbk+1ck+1, hemosganado.Idea 2: Tenemos que pasar la informacin que hemos aadido por ejemplo un ab en unlado hacia el otro lado donde tenemos que aadir entonces una c (o en un lado la a y en elotro lado un bc).El truco consiste en usar unos smbolos noterminales cuales se van a sustituir dependiendodel contexto en el cual se encuentran.Entonces, construimos P y N :

P = {$ , para obtener la palabra vaca$ aXbc, para iniciar la construccinXb bY, para empezar ir hacia las csY b bY, para ir hacia las csY c Zcc, para aadir una c y empezar volverbZ Zb, para volver hacia las asaZ aaXb, para aadir una a y una bX para terminar}

N = {$, X, Y, Z}

Se puede comprobar formalmente con induccin sobre k que la gramtica dada generaexactamente el lenguaje deseado, es decir L(Gabc) = Labc.La comprobacin sigue la construccin y se observa que no hay ambigedad en el momen-to de elegir una produccin.

Existe tambin una gramtica que usa un smbolo noterminal menos y tambin una pro-duccin menos:

P = {


$ , para obtener la palabra vaca$ aXbc, para iniciar la construccinXb bX, para ir hacia las csXc Y bcc, para aadir una b y una cbY Y b, para volver hacia las asaY aaX, para aadir una aaY aa para terminar}

N = {$, X, Y }

Se observa:

tenemos ambigedad en elegir producciones para sustituir y dnde aplicarlas aqu hemos decidido aadir a la derecha una b y una c generalmente se nota que hay muchas gramticas que generan el mismo lenguaje

5.2. Abreviacin de Backus

Para abreviar la notacin de las producciones usamos la forma normal de Backus (BNF). Agru-pamos las producciones cuyas partes izquierdas coincidan, escribiendo las partes derechas sepa-radas por |, por ejemplo:

P = {$ | aXbc,Xb bX,Xc Y bcc,bY Y b,aY aaX | aa,}

Definimos una gramtica que genere lo que se usa en programas, por ejemplo:

((a+ b) (c+ d)) (e+ f)

Lexpr = {w | w es expresin algebraica}


donde nos limitamos a variables que consisten de una sola letra. Entonces

T = {(, ),+, , a, . . . , z}P = $ E,E E E | (E E) | (E + E) | a | . . . | z

Gexpr = ({$, E},T , P, $)

se puede ampliar la gramtica que incluye tambin y /se puede ampliar la gramtica que genere tambin expresiones con variables de ms de unaletra, por ejemplo: ancho alturams tarde veremos como se define las expresiones de tal estilo un poco ms completo

5.3. rbol de derivacinPara las gramticas podemos visualizar la aplicacin de las producciones que derivan desde elsmbolo inicial una palabra como un rbol, el rbol de derivacin:

arbol

El lugar con el smbolo inicial se llama raz del rbol (aunque se suele dibujarlo arriba de todo).Como se ve, cada smbolo es la raz de un subrbol.

La palabra que se puede leer desde la izquierda hacia la derecha en las hojas del rbol y solamenteconsiste de smbolos terminales ser una sentencia.

5.4. Jerarquia de Chomsky

Segn Chomsky se clasifica las gramticas en cuatro tipos (cuales son, como vemos ms adelante,entre si verdaderamente diferentes).Entonces sea G = (N ,T , P, $) una gramtica (y = N T ). Las gramticas se destinguensolamente en el sistema de producciones que siempre ser un conjunto finito y que se clasificaen los siguientes tipos:

Tipo 0: gramticas generales sin restricciones

P .N .

es decir, se sustituye por lo menos un smbolo noterminal.


Tipo 1: gramticas sensibles al contexto

P {xAy xvy | x, y , A N , v +} {$ }

es decir, se sustituye un smbolo noterminal por algo manteniendo el contexto; entoncesuna derivacin siempre produce palabras ms largas o iguales (u v = |u| |v|)

Tipo 2: gramticas libres de contexto

P N + {$ }

es decir, se sustituye solo smbolos noterminales por palabras no vacas

Tipo 3: gramticas regulares (o lineales)

P N (N .T T ) {$ }

es decir, lineales a la izquierda (porque los smbolos noterminales aparecen en una derivacinsiempre a la izquierda de la palabra)

P N (T .N T ) {$ }

es decir, lineales a la derecha (porque los smbolos noterminales aparecen en una derivacinsiempre a la derecha de la palabra)

Se ha introducido explcitamente la regla $ en las gramticas de tipos 1, 2, y 3para permitir que el lenguaje {} puede ser generado dado que las regls solo permiten uncrecimiento de la longitud de las palabras a lo largo de las derivaciones.

Retomamos la clasificacin de las gramticas hacia final del curso (por ejemplo, respon-demos a la pregunta si son de verdad clases separadas).

Observacin: si permitimos para las gramticas de libre contexto reglas del tipo N ,es decir, permitimos reglas como A , podemos sustituir todas las reglas que tengan una Aa la derecha, por ejemplo B xAy por B xy, y conseguir as una eliminacin de lasproducciones compresoras.

5.5. Equivalencia y ambigedad

Dos gramticas son equivalentes si generan el mismo lenguaje, es decir, G1 G2 si L(G1) =L(G2).

(Adelanto: averiguar en general si dos gramticas son equivalentes es un problema no com-putable.)


Sea G = ({$, A}, {1}, {$ 1A, $ 11, A 1}, $) una gramtica. Tanto $ 11 como$ 1A 11 es una derivacin para la palabra 11.Una sentencia es ambigua si existen ms de una derivacin para ella en una gramtica.

Una gramtica es ambigua si su lenguaje contiene una sentencia ambigua, es decir, se puedederivar la misma sentencia con dos (o ms) derivaciones distintas.Un lenguaje es ambiguo (o incluso se dice inherentemente ambiguo) si todas las gramticas quegeneran el lenguaje son ambiguas.Ejemplo: G = ({$}, {1}, {$ 11}, $) no es ambigua, entonces L(G) no es ambiguo.Si una sentencia es ambigua (en el caso de las gramticas libres de contexto) tenemos dos rbolesde derivacin para la misma sentencia.

Ejemplo:E E + E | E E | (E) | a | . . . | z, $ E

ambitree

La ambigedad introduce cierto grado de indeterminismo para derivar palabras, por eso, en laprctica se intenta evitar gramticas ambiguas.

(Pero: el problema de decisin, si existe para una gramtica ambigua una gramtica equivalentenoambigua es un problema nocomputable.)Investigamos de nuevo las expresiones aritmticas:

sabemos que tanto la adicin como la multuplicacin son asociativas, entonces podemosacordar generar siempre con derivaciones ms a la izquierda

sabemos que hay prioridades (acordadas) entre las operaciones: () antes que antes que+, entonces podemos acordar generar primero las operaciones con menos prioridad

podemos introducir varables adicionales que nos garantizan una derivacin nica

Usamos E para expresiones (va a ser tambin el smbolo inicial), T para termios (con prioridadasociado a +), F para factores (con prioridad asociado a , y V para variables (que ya no tendrnoperaciones):

E E + T | TT T F | FF (E) | VV a | b | . . . | z

La gramtica con este sistema de producciones no es ambigua.

exprnoamb


6. Autmatas finitos

Describimos autmatas finitos con unas definiciones matemticas. Nos limitamos al principio aautmatas solamente con entrada.

6.1. Autmatas finitos deterministas (AFD)Un autmata finito determinista (AFD) es una quntupla

M = (, Q, , q0, F )

donde

es un alfabeto (sabemos / )Q es un conjunto finito no vaco de estados, es decir, 0 < |Q|


entoncesM = ({0, 1}, {q0, q1, q2, q3}, , q0, {q0})

Cmo describimos cmodamente ?

Observamos: |Q|


En el grafo podemos observar: si w L(M) entonces existe un camino en el grafo desde elestado inicial q0 hasta algn estado final de tal manera que podemos leer la palabra w a lo largode las aristas visitadas.

Ejemplo: Un autmata que acepta nmeros reales (en Pascal):afdreal

Curiosidades de C/C++:

Comprueba con un compilador de C/C++ (o de Java) si a=000; o a=0011.0; sonsentencias correctas, sino no lo son, modifica el autmata adecuadamente (Qu pasa cona=009?).Comprueba con un compilador de C/C++ (o de Java) si a=3E000; es una sentencia cor-recta, sino no lo es, modifica el autmata adecuadamente.

a=.1+ +1.; es una sentencia correcta en C/C++ (se asigna a a el valor 1.1 siendo lasuma de dos constantes flotantes), pero importante es el espacio entre los dos +

Vemos que estmos confrontados con diferentes problemas:

deberamos saber antemano: Qu es una constante flotante?deberamos traducir dicho conocimiento en un autmata

deberamos comprobar si dicho autmata de verdad acepta lo que debe aceptar

si implementsemos tal autmata de forma real, deberamos comprobar adicionalmente sila implementacin refleja la descripcin matemtica

Observamos, cada AFD se puede completar:

aadimos un estado e a Q (pero e / F )aadimos las transiciones que faltan, es decir, (q, ) = e para todos los q Q (incluyendoe) y con eso se convierte en una funcin total

Observamos:

si q0 F entonces L(M) y al revs, si L(M) entonces q0 F .puede ocurrir que hay estados no acesibles desde q0, incluso pueden ser aislados, es decir,no existe un camino desde q0 hacia tal estado.


Dos autmatas M1 y M2 son equivalentes si aceptan el mismo lenguaje, M1 M2 si L(M1) =L(M2).

Si eliminamos todos los estados no acesibles (o aislados) de un autmata, obtenemos unautmata equivalente al autmata original.

Obviamente tal autmata se representa con un grafo conexo.

Dos estados q1 y q2 de dos autmatas M1 y M2 son equivalentes, es decir, q1 q2, si paraq1 Q1 y q2 Q2 (q1, w) F1 (q2, w) F2.Entonces dos autmatas son equivalentes si sus estados iniciales son equivalentes.

6.2. Autmatas finitos nodeterministas (AFND)Ampliamos un poco las posibilidades de las transiciones de un autmata finito, es decir, cambi-amos la funcin .

Un autmata finito nodeterminista (AFND) es una quntupla

M = (, Q, , q0, F )

donde

es un alfabeto.

Q es un conjunto finito no vaco de estados, es decir, 0 < |Q|


0 1= q0 {q0, q3} {q0, q1}

q1 {q2}q2 {q2} {q2}q3 {q4} q4 {q4} {q4}

Ampliamos de nuevo para definir el lenguaje aceptado por un AFND : Q P(Q)

(q, ) = q

(q, w) = {p | p Q,r (q, ) : p (r, w)} , w

es decir, coincide con para smbolos del alfabeto y en general enumera los estados alcanz-ables con tal palabra.

Un autmata finito nodeterministaM = (, Q, , q0, F ) acepta una palabraw si (q0, w)F 6= donde es la ampliacin de la relacin de transicin .O en otras palabras, M acepta w, si (q0, w) contiene un estado final del autmata.

El lenguaje aceptado por un autmata finito nodeterminista M es el conjunto de palabrasaceptadas por M :

L(M) = {w | w ,M acepta w}

6.3. Equivalencia entre AFD y AFND

Est claro que cualquier AFD tambin es un AFND, es decir, si L es un lenguaje aceptado por unAFD, tambin est aceptado por un AFND. Simplemente existe como mucho una sola transicinpara cada smbolo del alfabeta y para cada estado.

Pero tambin podemos construir para cada AFND un AFD equivalente, es decir, un autmatadeterminsta que acepta el mismo lenguaje.Ejemplo: convertimos el AFND que acepta Ldos en un AFD equivalente:afndafd

Para el caso general tenemos:

Sea M = (, Q, , q0, F ) un AFND, construimos un AFD M = (, Q, , q0, F ) con

Q P(Q), es decir, escomo muchoel conjunto de todos los subconjuntos de Q.


q0 = {q0}, es decir, es el conjunto que contiene el estado inicial del AFND.(Qi, ) = Pj q Qi, p Pj con (q, ) = p, es decir, existe una transicin conel smbolo en el AFD, si existe alguna transicin con tal smbolo entre cualquier parejade estados correspondientes en el AFND.

F P(Q) con si f F entonces existe un q f con q F , es decir, el conjunto deestados finales son todos aquellos estados del AFD que contienen por lo menos un estadofinal del AFND.

Se suele construir los estados necesarios del AFD a lo largo de la construccin en vez de cogerpor defecto todos los posibles subconjuntos, para evitaren caso que sea posibleconstruirmuchos estados que finalmente no se alcanza desde el estado inicial.

Porqu es correcta la construccin?

Tenemos que comprobar formalmente que si M (siendo un AFND) acepta w, entonces M (sien-do el AFD construido) tambin lo acepta; y si M acepta w, entonces M tambin lo hace, esdecir, que L(M) = L(M ).

Pues, sea M un AFND y M el AFD correspondiente.

Sea w = x0x1x2 . . . xn L(M) cualquier palabra aceptada por M .Comprobamos que w L(M ), es decir, L(M) L(M ):Definimos los siguientes diagramas

pxi q

Pxi Q

es decir, si hacemos la transicin en M desde p a q leyendo xi, en otras palabras, usamos(p, xi) = q, entonces existe (segn construccin) una transicin en M de P (con p P ) aQ (con q Q) leyendo xi, en otras palabras, existe (P, xi) = Q.Para la palabra w obtenemos:

q0x0 q1 x1 q2 x2 xn1 qn xn qn+1 F

Q0x0 Q1 x1 Q2 x2 xn1 Qn xn Qn+1 F

donde la construccin va desde la izquierda, es decir, del estado inicial, hacia la derecha, es decir,a un estado final. Dado que M acepta w, qn+1 es un estado final y siendo miembro de un conjuntoQn+1, este ser un estado final de M .


Entonces hemos comprobado que M acepta w, y por eso L(M) L(M ).Ahora, sea w = x0x1x2 . . . xn L(M ) cualquier palabra aceptada por M .Comprobamos que w L(M), es decir, L(M) L(M ):Definimos los siguientes diagramas

Pxi Q

3 3p

xi q

es decir, si hacemos la transicin en M desde P leyendo xi a Q, en otras palabras, usamos(P, xi) = Q, entonces existe (segn construccin) una transicin en M de algn p (con p P )leyendo xi a algn q (con q Q), en otras palabras, existe (p, xi) = q.Para la palabra w obtenemos:

Q0x0 Q1 x1 Q2 x2 xn1 Qn xn Qn+1 F

3 3 3 3 3

q0x0 q1 x1 q2 x2 xn1 qn xn qn+1 F

donde la construccin va ahora desde la derecha, es decir, un estado final, hacia la izquierda,es decir, al estado inicial. Dado que M acepta w, Qn+1 es un estado final y un conjunto novaco, entonces existe un miembro qn+1 que tambin es elemento de F y por consecuencia un qnaplicando el diagrama y asi succesivamente hasta llegar a q0.

Entonces hemos comprobado que M acepta w, y por eso L(M) L(M ).Finalmente tenemos L(M) L(M ) y L(M) L(M ) y por eso L(M) = L(M ).Como se observa en la construccin puede ser que se usa 2|Q| estados en el autmata deterministasi el autmata no-determinista tena |Q| estados, es decir, el crecimiento del nmero de estadospuede ser exponencial.

Surgen dos preguntas:

Existen AFNDs que producen un AFD de tal tamao grande?

Son necesarios tantos estados (o existe una mejor forma de realizar la conversin)?Un ejemplo para una respuesta a la segunda:Usamos = {a, b} como alfabeto. Definimos los siguientes lenguajes (que dependen del nmeron IN):


Ln = {w | w , w = w1w2, w1 6= w2, |w1| = |w2| = n, n IN}

es decir, todas las palabras con 2n letras donde la primera mitad se distingue de la segunda.

Es bastante claro que para cualquier n existe un autmata que acepta Ln porque el lenguaje esfinito (|Ln| = 22n 2n).En un libro (HotzEstenfeld) se encuentra el siguiente AFND que acepta L3 (dejan la compro-bacin al lector)afndln

Bueno, con un poco de trabajo se puede comprobar (enumerando todos los caminos desde elestado inicial hasta el estado final) que en cada uno de los caminos siempre existe en la primeraparte una arista con una a (o una b) donde en la misma posicin de la segunda parte hay una b (ouna a).El AFND dado tiene 22 estados que (sin que ellos lo dicen) est en el orden de n2 (si inspec-cionamos la construccin vemos la suma de 1 hasta 2n).Tambin construeron un AFD para L3:

afdln

Manifestan que dicho autmata es mnimo, y teniendo ms de 2n estados concluyen que la con-struccin de un AFND a un AFD puede incrementar el nmero de estados exponencialmente.

Veremos: Ambas construcciones tienen sus deficiencias, aunque el hecho en si es correcto!

Primero, no dan un esquema cmo construir un autmata que reconozca Ln para cualquier n(puede ser que hay buena suerte en el caso de L3).Segundo, el AFD dado no es mnimo, una simplificacin sera:

afdlns

Pero, el nuevo autmata sigue necesitando un nmero exponencial de estados, porque se tieneque construir en el lado izquierdo todas las posibles palabras w1.

Entonces: Creemos o sabemos?, si no lo hemos comprobado o si no hemos entendido una com-probacin presentada, entonces solamente creemos. El saber va ms all. Hay que mantenersecrtico, siempre.

Construimos un AFND para Ln sistemticamente.

Idea: En cada uno de los caminos reconociendo w1 siempre tiene que existir una arista con unaa (o una b) donde en la misma posicin para reconocer w2 hay una b (o una a).Este principio nos lleva a una construccin inductiva:


afdln1

afdln2

afdln3

afdlnn

El nmero de estados entonces es:

|Q| = 1 + 2 + 4 + 6 + . . .+ 2n+ (2n 2) + . . .+ 4 + 2 + 1

= 1 + 2ni=1

i+ 1 + 2n1i=1

i

= 1 + n(n+ 1) + 1 + (n 1)n= 2(n2 + 1)

Como vemos, incluso hemos reducido el nmero de estados: el AFND para aceptar L3 tienesolamente 20 estados.

La construccin de un AFD sigue el mismo argumento dado arriba: se necesita construir todaslas posibles palabras w1 en el lado izquierdo y por eso el AFD tiene por lo menos 2n estados(los 2n 1 para enumerar los w1 y por lo menos un estado final en el lado derecho.Otro ejemplo para mostrar las capacidades de un AFND (y el crecemiento exponencial necesariodel AFD equivalente):Usamos = {0, 1} como alfabeto. Definimos los siguientes lenguajes (que dependen del nmeron IN):

Ln = {w | w , w contiene un 1 en la n-nsima posicin desde la derecha}

Es bastante fcil construir un AFND que acepte Ln:

afndlr

No es tan obvio como construir directamente un AFD. Pero es posible con la construccin (Ha-zlo!).Observamos en la construccin:

Sea w = xnxn1 . . . x2x1 {0, 1}.


Para todos los i {1, . . . , n} tenemos:qi (q0, w) = xi = 1

es decir:

Si xi = 1 (el i-simo smbolo desde la derecha es un 1), entonces existe un caminodesde q0 a qi (es decir, qi (q0, w)) porque podemos usar dicho xi para pasar elpuente y

si existe un camino desde q0 a qi leyendo w (qi (q0, w)), entonces w tiene un 1como i-simo smbolo desde la derecha (es decir, xi = 1) porque hemos pasado elpuente.

Entonces, existe en la construccin para cada subconjunto P P(Q) con q0 P unapalabra w tal que tenemos que construir un camino desde Q0 = {q0} hacia P .Entones el AFD contiene por lo menos 2|Q|1 = 2n estados (todos aquellos que codificansubconjuntos conteniendo q0).

Construimos un AFD directamente:

afdlr

Este autmata (y siguiendo el esquema de la construccin) contiene 2n estados.En ambos ejemplos parece que el nmero de estados necesarios en un AFD tenga algo que vercon la capacidad de contar o enumerar hasta cierto nmero.

6.4. Autmatas finitos nodeterministas con transiciones (AFND)

Queremos construir un autmata que acepta el lenguajeL = {aibjck | i, j, k IN}

Si fuesemos capaz de saltar mgicamente, es decir, sin consumir una letra de la entrada, de unestado a otro, sera fcil la construccin:

AUTaibjckepsEs decir, hemos introducido aristas marcados con la palabra vaca .

Un autmata finito nodeterminista con transiciones (AFND) es una quntupla

M = (, Q, , q0, F )

donde


Q, , q0, y F estn definidos igual como en el caso de un AFND

es

una relacin, es decir (Q ( {}))Q o una funcin, es decir, : Q ( {}) P(Q) siendo P(Q) el conjunto de

las partes de Q

Observamos que aadir ms aristas con obviamente no cambia el comportamiento del autmata:

AUTaibjckepstransPodemos tratar las transiciones con como una relacin T sobre el conjunto de estados, es decir

T = T1 = {(q, p) | (q, ) = p} QQEn el ejemplo tenemos

T1 = {(q0, q1), (q1, q2)}

Esta relacin podemos ampliar para que sea reflexiva, es decir, que todas las parejas (q, q) conq Q formen parte de la relacin, es decir, formamos

T0 = {(q, q) | q Q}y con eso

T = T0 T1entonces T por construccin es una relacin reflexiva. En el ejemplo tenemos

T0 = {(q0, q0), (q1, q1), (q2, q2)}y con eso

T = {(q0, q0), (q0, q1), (q1, q1), (q1, q2), (q2, q2)}

Podemos ampliar la relacin aun ms considerando el efecto transitivo de las transiciones , esdecir, formamos en un primer paso

T2 = {(q, p) | r Q : (q, r), (r, p) T0 T1 y (q, p) / T0 T1}y con eso

T = T0 T1 T2en el ejemplo tenemos

T2 = {(q0, q2)}y as sucesivamente

Ti = {(q, p) | r Q : (q, r), (r, p) i1j=0

Tj y (q, p) /i1j=0

Tj}


Finalmente definimosT = T0 T1 T2 . . . =

i=0

Ti

como clausura (o ciero, o cerradura) transitiva de la relacin de las transiciones o msbreve clausura.

El proceso termina en nuestro caso de autmatas finitos, es decir, la unin va solamente sobre unnmero finito de is, porque T sigue siendo un subconjunto del conjunto finito QQ (T QQ).Con la clausura podemos definir la clausura de un estado, como todos aquellos estados quese puede alcanzar con caminos de transisiones , es decir

cl(q) = {p | (q, p) T }

En el ejemplo:

cl(q0) = {q0, q1, q2}cl(q1) = {q1, q2}cl(q2) = {q2}

AUTaibjckafnd

hemos aadido q0 a los estados finales F porque existe un estado final que pertenece a laclausura de q0, es decir, Lhemos marcado las aristas de la clausura con smbolos del alfabeto

Entonces podemos formalizar el lenguaje aceptado por un AFND (parecido a lo que hicimospara un AFND).Primero definimos la ampliacin de para autmatas con transiciones . (q, w) va a ser elconjunto de estados (igual como en el caso de para AFNDs) que podemos alcanzar desde qleyendo la palabra. Entonces:

: Q P(Q)

1.

(q, ) = cl(q)

es decir, nos quedamos en la clausura si hemos alcanzado el final de la palabra


2.

(q, w) = {p | p Q y r (q, w) tal que p cl((r, ))}=

r(q,w)

cl((r, ))

es decir, (q, w) es el conjunto de estados alcanzables desde un estado r siendo miembrode la clausura de un estado alcanzable desde q sin haber ledo el ltimo smbolo .

(q0, w) enumera entonces todos los estados alcanzables desde q0 leyendo la palabra w.

Observa: Hemos dado una definicin recursiva desde la izquierda, es decir, aadimos un smboloa la derecha. Hubiese sido posible definir para un AFND de la misma manera.

Un autmata nodeterminista con transiciones M acepta una palabra w sobre el alfabeto (w ) si

(q0, w) F 6= donde sea la ampliacin de la funcin dada arriba.

El lenguaje aceptado por M es (como siempre)L(M) = {w |M acepta w}

6.5. Equivalencia entre AFND y AFND

Primero observamos que cualquier AFND es obviamente tambin un AFND (pues uno que,por casualidad, no tenga transiciones ).Luego podemos construir a partir de un AFND un AFND equivalente.

Entonces, sea M = (, Q, , q0, F ) un AFND.

Un AFND equivalente es el autmata M = (, Q, , q0, F ) donde

Q = Q

(q, ) =

rcl(q) cl((r, )) (podemos escribir solo q porque Q = Q)q0 = q0

F ={

F si F cl(q0) = F q0 si F cl(q0) 6=

es decir, aadimos q0 como estado final, si algn estado final del AFND pertenece a laclausura del estado inicial.


Convertimos el ejemplo:La tabla de transiciones para M con las transiciones de la clausura es:

a b c clq0 {q0} {q1} {q0, q1, q2}q1 {q1} {q2} {q1, q2}q2 {q2} {q2}

entonces la tabla con transiciones desde la claurura es

a b c clcl(q0) {q0} {q1} {q2} {q0, q1, q2}cl(q1) {q1} {q2} {q1, q2}cl(q2) {q2} {q2}

y con eso la tabla final del AFND es

a b cq0 {q0, q1, q2} {q1, q2} {q2}q1 {q1, q2} {q2}q2 {q2}

Adems tenemos F cl(q0) 6= y por eso F = F {q0} = {q0, q2}.Finalmente resulta el siguiente grafo:

afnde

Por qu es correcto la construccin?

Pues los argumentos (y la comprobacin) siguen los mismos pasos como lo vimos en el caso deAFND y AFD. Siempre cuando hay una transicin en el AFND leyendo un smbolo encon-tramos (segn construccin) una transicin en el AFND correspondiente porque consideramostoda la clausura, y vice versa, si hay una transicin en el AFND, tiene que haber existido unatransicin en el AFND o bien con o bien sin una secuencia de transiciones .

Cunto ha crecido esta vez el autmata?

El nmero de estados queda igual, solo se amplia (si hace falta) F por un estado. Pero ha creci-do el nmero de aristas (es decir, transisiones). Dicho crecimiento puede llegar como mucho a|||Q|2 porque como mucho tantas aristas se pueden incorporar entre los nodos del grafo.Finalmente hemos comprobado la equivalencia entre autmatas nodeterministas y autmatasnodeterministas con transiciones .


6.6. Existencia de autmatas finitos mnimos

Ya vimos que hay varias posibilidades para construir un autmata finito determinista que acepteun lenguaje (regular), por ejemplo, por construccin directa, o por el paso de un AFND a unAFD.

Surge la pregunta: existe un autmata finito determinista (AFD) mnimo que acepta tal lenguaje?Nos referimos al nmero de estados que tiene el AFD, es decir |Q|, dado que el nmero detransiciones por estado est determinado por el nmero de smbolos en multiplicado por |Q| siel AFD es completo.

La respuesta es: por supuesto que s!

Con el siguiente argumento: cada subconjunto de los nmeros enteros IN tiene un mnimo, y losnmeros de estados de todos los posibles AFDs que aceptan L forman tal subconjunto.Para la construccin del autmata mnimo necesitamos el formalismo de las relaciones de equiv-alencia.

Ya vimos que para cada lenguaje L podemos construir una relacin de equivalencia sobre:

xRLy (z : xz L yz L)

es decir, x es equivalente a y, si, aadiendo cualquier sufijo, ambas palabras resultantes o bienestn en L o bien no estn en L.

Un lenguajeL es regular, si y solo si el ndice de la relacinRL es finito, es decir, la relacintiene solamente un nmero finito de clases de equivalencia (Teorema de Myhill y Nerode).Comprobamos primero la direccin =, es decir, si el lenguaje es regular, entonces el ndicede la relacin es finito:

L es regular, entonces existe un AFD que acepta L.

Sea M = (, Q, , q0, F ) un AFD con L(M) = L.

Definimos una relacin de equivalencia sobre M :

xRMy si (q0, x) = (q0, y)

es decir, llegamos al mismo estado leyendo x o y empezando en el estado inicial.

Veremos a continuacin que RM RL, es decir, que RM es un refinamiento de RL, o en otraspalabras, si dos elementos caen en una misma clase de equivalencia respecto a la relacin RM ,tambin caen en una misma clase respecto a RL.

Entonces, sea xRMy, es decir (q0, x) = (q0, y).


Sea z cualquier palabra. Miramos:xz L (q0, xz) F

((q0, x), z) F ((q0, y), z) F (q0, yz) F yz L

es decir, si xRMy entonces tambin xRLy, y por eso:

Indice(RL) Indice(RM)= nmero de estados acesibles desde q0 |Q|<

Comprobamos ahora la direccin =, es decir, si el ndice de la relacin es finito, entonces ellanguaje es regular. Dicha comprobacin va a ser una comprobacin constructiva muy til:Sea RL la relacin de equivalencia de L con Indice(RL)


6.7. Ejemplos de uso del teorema de Myhill y NerodeInvestigamos de nuevo el lenguaje

L = {anbn | n IN, n > 0}anotamos unas clases de equivalencia de L:

[ab] = L

[a2b] = {a2b, a3b2, a4b3, . . .}. . .

[akb] = {ak+i1bi | i 1}verificamos que son clases de equivalencia, porque si ak+j1bj [akb] y ak+l1bl [akb] en-tonces o bien ak+j1bjz, ak+l1blz L (si z = bk1) o bien ak+j1bjz, ak+l1blz / L (siz 6= bk1).Por eso el nmero de clases de RL es infinito, es decir, Indice(RL) =.Observa que no hemos clasificado todas las palabras de , sino solamente algunas palabrasposibles:

= L [a2b] . . . [akb] . . . ya son un nmero infinito

. . . las dems claseses decir, para comprobar que un lenguaje no es regular basta con encontrar un nmero infinito declases de equivalencia (respecto a la relacin RL).Investigamos el lenguaje

L = {w | w {0, 1} y w termina con 00}

Pensamos en las posibles clases de equivalencia. Obviamente hay tres, o bien una palabra notermina en 0, o bien termina en un 0, o bien termina por lo menos en dos 0, es decir:

[] = {w | w no termina en 0}[0] = {w | w termina en un solo 0}[00] = {w | w termina en 00}

Con = [] [0] [00] seguimos la construccin de arriba y obtenemos la tabla de transicionespara el autmata:

0 1= [] [0] []

[0] [00] []?[00] [00] []

o como diagrama:

equiafd


6.8. Algoritmo de minimizacin

La comprobacin del teorema de Myhill y Nerode nos proporciona un hecho muy importante:el autmata basado en las clases de equivalencia es el autmata mnimo dentro de todos losposibles autmatas finitos deterministas y completos que aceptan el mismo lenguaje, porque untal autmata M definira un refinamiento de RM RL, es decir, Indice(RM ) Indice(RL)y el AFD de las clases de equivalencia M representa las mismas clases RL = RM , entoncesIndice(RM ) Indice(RL) = Indice(RM).Una pregunta surge: Cmo sabemos si un AFD M ya es mnimo?

Pues, M no es mnimo, si

w p, q Q, p 6= q : (p, w) F (q, w) Fes decir, llegamos con alguna palabra w desde ambos estados siempre o bien a un estado final, obien a un estado nofinal.

En tal caso, podemos unir los dos estados en un nico estado.

Basta con realizar las pruebas con todas las palabras w con |w| < |Q| porque no hace faltavisitar un estado dos veces.

Con dicho argumento describimos el algoritmo de minimizacin (sin comprobacin) a contin-uacin.

Decimos que dos estados p y q son distinguibles (o noequivalentes) si existe una palabra w quenos lleva desde p a un estado final pero no desde q, o al revs, es decir:

p 6 q ((p, w) F y (q, w) / F ) o ((p, w) / F y (q, w) F )

El algoritmo calcular la relacin de distinguibilidad (o noequivalencia) entre los estados ycontiene 5 pasos.

1. Se elimina todos los estados no acesibles desde el estado inicial.

2. Se forma una tabla de todas las parejas de estados (p, q) con p 6= q.3. Se marca en la tabla todas las parejas (p, q) con p F, q / F o p / F, q F (porque

dichos estados seguro son distinguibles).4. Mientras haya cambio en la tabla:

para cada pareja (p, q) no marcada y para cada smbolo si ((p, ), (q, )) est marcada, tambin se marca (p, q).

5. Las parejas (tuplas) no marcadas se une en un slo estado.


Ejemplo: partimos del siguiente AFD completo:afdc

1. Todos los estados son acesibles desde a, por eso, no hay que eliminar nada.

2. La tabla es:

a b c d ea -b - -c - - -d - - - -e - - - - -

3. Las marcas iniciales son (en vez de simple marcas, usamos nmeros para visualizar en elsiguiente apartado los cambios en la tabla en cada paso):

a b c d ea - 1b - - 1c - - - 1d - - - - 1e - - - - -

4.

a b c d ea - 2 3 1b - - 4 1c - - - 5 1d - - - - 1e - - - - -

5. El autmata mnimo es:afdcmin

Observa que en la construccn del autmata podemos comprobar de cierta manera la cor-reccin de la tabla: cuando recorremos todas las aristas del autmata original, tenemos queo bien aadir o bien encontrar su homloga en el autmata en construccin.

El paso 4 se puede implementar ms eficiente. En vez de mirar tantas veces las parejas no mar-cados, se mantiene listas de espera que se marcan recursivamente. Observamos:

Si tenemos que marcar (p, q), es porque (r, s) = ((p, ), (q, )) ya est marcado.


Entonces de alguna manera la pareja (p, q) depende de la pareja (r, s).Es decir, si en un futuro marcamos en algun momento (r, s), directamente podemos marcar(p, q) tambin.

Para llevar eso a cabo, aadimos a cada celda una lista de parejas que dependen de la la parejaen cuestin. Si se marca una pareja, recursivamente se marcan tambin todas las entradas en laslistas.

Con est mejora el algoritmo tiene complejidad O(|Q|2||).

7. Expresiones regulares

Hasta ahora era difcil describir lenguajes aceptados por autmatas. Siempre tenamos que aprovecharde una notacin como

L(M) = {w | alguna propiedad de w}

Por ejemplo, si queramos desarrollar un autmata que comprobase que una cadena codificaseuna direccin de correo electrnico vlida tendramos como propiedades:

1. los smbolos permitidos son: a-z, A-Z, 0-9, @ . - _

2. debe contener exactamente una @

3. por lo menos un . detrs de la @

4. detrs del ltimo . deben venir entre 2 y 4 letras

5. detrs de cada . y de la @ debe venir por lo menos una letra

6. delante de la @ por lo menos una palabra que empieza con una letra,

es decir, L(M) = {w | w cumple las condiciones de arriba }.Ejercicio: Intenta construir un autmata!Sera conveniente tener un metalenguaje que nos permitiese describir fcilmente lenguajes (porlo menos de cierto tipo).


7.1. Sntaxis y semntica

Sea un alfabeto. Una expresin regular sobre se define con las siguientes reglas (induc-tivas):

1. a) es una expresin regularb) es una expresin regularc) si , entonces es una expresin regular

2. si y son expresiones regulares, entonces tambin

a) . es una expresin regular (obviamos del punto muchas veces)b) (+ ) es una expresin regular

3. si es una expresin regular, entonces tambin

a) () es una expresin regularb) () es una expresin regular

Como observamos: hemos introducido metasmbolos ((,),,+,.,). Si alguno de ellosaparece en tenemos un problema (Houston) que resolveremos al final de esta seccin.Ejemplos:Sea = {a, b, c}. Posibles expresiones regulares son:

((a.b) + b.c.(a)) ((a.a.a+ b.c) + (c.b).(b))

Con eso hemos definido una sntaxis de expresiones regulares, pero cul ser su semntica?

Para cada expresin regular definimos un lenguaje correspondiente (basado en las reglas).El lenguaje L() definido por una expresin regular se define:

1. a) L() = b) L() = {}c) si , entonces L() = {}

2. si y son expresiones regulares, entonces

a) L(.) = L().L()b) L((+ )) = L() L()


3. si es una expresin regular

a) L(()) = L()b) L(()) = (L())

Ejemplos: sobre = {0, 1}:

el lenguaje que contiene una subcadena 11:

((0 + 1)),1,1.((0 + 1))

todas las cadenas que alternan 0 y 1:

(((0,1) + (0,1),0) + ((1,0) + (1,0),1))

o tambin con la expresin

(1 + ).(0,1).(0 + )

7.2. Equivalencia entre autmatas finitos y expresiones regulares

La semntica de una expresin regular define un lenguaje.Dado una expresin regular (sobre un alfabeto ). Qu tiene que ver el lenguaje L() con unlenguaje L(M) aceptado por un autmata finito M?Veremos: para cada expresin regular existe un autmata nodeterminista con transiciones M , o sea un AFND, que acepta el mismo lenguaje (es decir, L() = L(M)).Ya sabemos: entonces tambin existe un autmata finito determinista, o sea un AFD, aceptandoel mismo lenguaje.De hecho, comprobaremos algo ms: para cada sobre existe un AFNDM = (, Q, , q0, F )con L() = L(M) y

no existe ninguna transicin hacia el estado inicial, es decir

q Q, : q0 / (q, ) (q, )

M tiene exactamente un estado final del cual no sale ninguna transicin, es decir,

|F | = 1 y , f F : (f, ) (f, ) =


La comprobacin sigue la definicin inductiva de la expresin regular, lo describimos solamentecon los grafos de los autmatas. Entonces, sean , , y expresiones regulares sobre algnalfabeto .

1. a) = regexprafnde1

b) = regexprafnde2

c) = aregexprafnde3

2. a) = regexprafnde4

b) = ( + )regexprafnde5

3. a) = ()regexprafnde6

b) = ()regexprafnde7

Ejemplo: construimos el AFND para = (((a.b) + a) + b.b)regexprafndeej

La otra direccin, es decir, comprobando que para cada autmata finito existe una expresinregular que describe el mismo lenguaje, nos costar un poco ms de trabajo.Sea M = (, Q, , q0, F ) un AFD (sabemos que cualquier AFND o AFND se puede convertiren un AFD).Describimos un algoritmo que sucesivamente construye la clausura transitiva del autmata da-do y as construye finalmentecomo atributos de las aristas entre q0 y un nuevo estado flaexpresin regular.

Por eso permitimos que se pueden escribir expresiones regulares a las aristas de un autmata, esdecir, para (p, ) = q escribimos (p, , q) (pues, la arista del estado p al estado q con atributo a),o teniendo expresiones regulares (p, , q) (pues, una arista de p a q con atributo ), o con dibujo:aristaexpr


1. aadimos un nuevo estado f y conectamos todos los estados en F con transiciones a f ,es decir, cambiamos M por M = (Q {f},, , q0, {f}) donde = para estados enQ y adems q F : (q, ) = f . As no hemos cambiado el lenguaje aceptado por M .(Pero siguimos escribiendo abajo simplemente M , , y Q para simplificar la notacin.)

2. para todos los estados q 6= q0 y q 6= fa) para cada pareja de aristas (p, , q) y (q, , r) y arista reflexiva (q, , q) (nota, puede

ser p = r)aade arista (p, , r)

b) elimina q con todas sus aristas adyacentespqr

c) agrupa las aristas construidas (p, 1, r), . . . , (p, k, r) escribiendo (p, 1+. . .+k, r)3. cuando termina el proceso, es decir, solamente existen aristas entre q0 y f , precisamente

(q0, , q0) y/o (q0, , f), la expresin regular final es .

(Observa: si q0 F entonces existe una arista con entre q0 y f , por eso, L(), y entoncesno hay que considerar un caso especial para contemplar lazos reflexivos en q0 porque + =.)Ejemplo:XXX

Una comprobacin formal de la correccin del algoritmo es bastante tcnica. Principalmentehay que realizar una induccin estructural con propiedades de dichos autmatas extendidos (quetienen expresiones regulares en sus aristas). No lo detallamos aqu, cae en la categora: lo creemos(en estos momentos).Como vimos en el ejemplo, hemos construido una expresin regular totalmente diferente a la departida. Debemos transformar dicha expresin regular sin cambiar el lenguaje que define paraconseguir finalmente una expresin regular igual a la de partida. Por eso:

Dos expresiones regulares y son equivalentes ( ) si definen el mismo lenguaje, esdecir, si L() = L().

Obviamente hay operaciones con expresiones regulares que mantienen la equivalencia, por ejem-plo:

Asociatividad:

(+ ( + )) ((+ ) + ).(.) (.).


Conmutatividad:

(+ ) ( + )

Elementos neutros:

(+ ) (+ )

(.) (.)

Eliminacin:

(.) (.)

Distributividad:

.( + ) (. + .)(+ ). (. + .)

Simplificacin:

(()) ()() ()

Con eso y un poco de mpetu podemos transformar sucesivamente la expresin regular obtenidapara obtener al final la expresin regular que era la base para el autmata finito inicial.

XXX

El problema de comprobar en general si dos expresiones regulares son equivalentes no es nadafcil. Dicho problema cae en la clase de los problemas PSPACE que contiene problemas an mscomplejos que los problemas de la clase NP que (a lo mejor) veremos hacia el final del curso (unproblema NP es el problema del viajante). Aqu nos basta constatar que un algoritmo deterministaque resuelve el problema necesita un tiempo que crece ms que exponencial en la longitud de laexpresin regular.


7.3. Abreviaciones para el uso de expresiones regulares

Para simplificar ms el uso de expresiones regulares, introducimos prioridades para eliminarparentesis, atorgamos

a la operacin asterisco de Kleene mxima prioridad (parecido a la exponenciacin enexpresiones algebraicas)a la operacin concatenacin segunda prioridad (parecido a la multiplicacin en expre-siones algebraicas) ya la operacin addicin la mnima prioridad (parecido a la adicin en expresiones alge-braicas)

Ejemplos:XXX

Adicionalmente describimos algunos ejemplos de abreviaciones de uso comn para expresionesregulares (puede ser que dicha notacin describe lenguajes que ya no son lenguajes regulares!):Sea = {0, 1, . . . , n} un alfabeto, donde los smbolos implcitamente estn ordenados, esdecir, si i < j para i, j {1, . . . , n} entonces i viene antes en el orden de todos los smbolosque j (pues, entonces es tal cual como estamos acostrumbados de tratar nuestro alfabeto dellenguaje natural).

[i j] : i + . . .+ j , es decir, todo el rango de smbolos entre (y incluyendo) i y j .Si j < i, [i j] = .? : (+ ), es decir, una o ninguna vez .

., cualquier smbolo del alfabeto

+ : , es decir, por lo menos una vez .

n : . . . nveces

(usando tal n en varias posiciones y exigiendo que tenga en casos concretos

en todos los sitios el mismo valor se pueden describir lenguajes ya no regulares){m,n} por lo menos m veces, pero como mucho n veces . (igual como arriba, usando taln y m se pueden describir algunos lenguajes no regulares)


7.4. Smbolos y metasmbolos

Resolvemos el problema de tener smbolos iguales en y en el metaalfabeto:

Se suele usar un smbolo de escape en el metalenguaje, normalmente el smbolo \. Si \ aparecedelante de otro smbolo, entonces se considera un smbolo de , sino un metasmbolo. (En-tonces, si \ es en , se anotara como \\.)Entonces podemos escribir la expresin regular que define una direccin de correo electrnicosintcticamente correta como:

= [a zA Z][a zA Z0 9\ _] = (\.)@(\.)+[a zA Z]{2,4}

donde unimos adicionalmente varios rangos en uno.

8. Lenguajes regulares

8.1. Equivalencia entre gramticas lineales por la derecha y aut-matas finitos

Sea M = (, Q, , q0, F ) un AFD.

Construimos una gramtica lineal por la derechaG con L(G) = L(M), es decir, genera el mismolenguaje que el AFD acepta.

G = (N ,T , P, $) = (Q,, P, q0)

es decir

N = Q, los estados del autmata determinan los smbolos noterminales de la gramtica

T = , los smbolos del autmata determinan los smbolos terminales de la gramtica

$ = q0, el estado inicial del autmata determina el smbolo inicial de la gramtica


El sistema de producciones P est dado por:

Si (q, ) = p es una transicin del AFD, con p, q Q y , entonces aadimos a Pla produccin q p.Si (q, ) = p es una transicin del AFD, con q Q, p F y , entonces aadimosa P la produccin q .Si q0 F , entonces aadimos a P la produccin q0 .

Ejemplo:afdabc

a b c= ?q0 q0 q1 q2

?q1 q1 q2?q2 q2

Entonces el sistema de producciones P de la gramtica ser:

P = {q0 aq0|a|bq1|b|cq2|c|, q1 bq1|b|cq2|c, q2 cq2|c}

Sea G = (N ,T , P, $) una gramtica lineal por la derecha, es decir, P N (T .N T ) {$ }.Construimos una autmata finito M con L(M) = L(G), es decir, el autmata acepta el mismolenguaje que la gramtica genera.

M = (, Q, , q0, F ) = (T ,N {f}, , $, {f})

es decir,

T = , los smbolos terminales de la gramtica determinan los smbolos del autmata

Q = N {f}, los smbolos noterminales de la gramtica determinan los estados delautmata, y aadimos un nuevo estado f , es decir, f / Nq0 = $, el smbolo inicial de la gramtica determina el estado inicial del autmata

Las transiciones estn dadas por:


Si A B es una produccin de G, con A,B N y T , entonces aadimos latransicin (A, ) = B.

Si A es una produccin de G, con A N y T , entonces aadimos latransicin (A, ) = f .

Si $ es una produccin de G, entonces aadimos la transicin ($, ) = f .

Observamos que el autmata construido es un autmata finito nodeterminista (AFND) quepodemos convertir en un AFD si hace falta.

Ejemplo:Para la gramtica de arribarenombrando los smbolosconvertimos

P = {$ a$|a|bA|cB|c|, A bA|b|cB|c, B cB|c}

a la tabla de transiciones

a b c= $ {$, f} {A} {B, f}

A {A, f} {B, f}B {B, f}?f

graafd

8.2. Equivalencia entre gramticas lineales por la derecha y lin-eales por la izquierda

Como era de esperar, gramticas lineales por la derecha y gramticas lineales por la izquierdadescriben el mismo fenmeno, es decir, generan los lenguajes regulares.Sea G = (N ,T , P, $) una gramtica lineal por la derecha, es decir, P N (N .T T ) {$ }.Construimos una gramtica G = (N ,T , P , $) lineal por la izquierda con el siguiente algorit-mo en cuatro pasos:

1. Si el smbolo inicial $ de G aparece a la derecha en una produccin de P , se sustitue $ endichas reglas de la siguiente manera:

Se introduce un nuevo smbolo noterminal $, es decir, N = N {$}.


Por cada regla de forma $ con N .T T se crea una nueva regla$ .Cada regla de forma X $ (X N , T ) se sustitue por X $.Si $ P , se aade para cada regla X $ (X N , T ) la reglaX .

Con esas modificaciones obtenemos un nuevo sistema de producciones P y un alfabeto devariables o bien N = N o bien N = N {$}.

2. Se crea un grafo dirigido con las siguientes propiedades:

El conjunto de nodos es N {}.Se aade una arista entre los nodesA yB con atributo , si existe una reglaA Ben P .

Se aade una arista entre los nodes A y con atributo , si existe una regla A en P .

Se aade una arista entre los nodes $ y con atributo , si existe la regla $ enP .

3. Se inverte el grafo, ms preciso:

Se intercambian los nodos $ y .Se invierte la direccin de todas las aristas.

4. Se transforma el grafo obtenido en el conjunto de reglas P :Para cada arista entre A y B con atributo se crea una regla A B (A N , B N {} y T {}).

Ejemplo: Partimos de la gramticaG = ({$, A}, {0, 1}, {$ |1A,A 0$|0}, $)

1. el smbolo inicial $ aparece a la derecha entonces:

Introducimos un nuevo smbolo noterminal $.Aadimos la regla $ 1A.Sustituimos la regla A 0$ por A 0$siendo $ P , aadimos la regla A 0 (pero que ya est en P )

Queda el sistema de producciones intermedio comoP = {$ |1A,A 0$|0, $ 1A}


2. El grafo reflejando dichas reglas es:graphldli

3. Y el grafo invertido es:igraphldli

4. con lo cual obtenemos el conjunto de reglas:P = {$ |A0, A $1|1, $ A0}

8.3. Lema de bombeo

Siendo ab una expresin regular, podemos construir un autmata finito que acepta el lenguajeas definido, tambin podemos construir para cualquier n IN fijo un autmata finito adecuado(anbn sera una expresin regular extendida que define el lenguaje correspondiente que contieneuna sola palabra).Pero no podemos construir un autmata finito que acepte el lenguaje:

Lab = {anbn | n IN} = {, ab, aabb, aaabbb, . . .}

donde el parmetro n no es fijo, sino se quiere que haya tantas as como bs.Por qu no podemos construir tal autmata?

asumimos que tengamos un autmata finito M con k estados que acepta Lab

anotamos los estados de M despus de haber ledo las palabras ai para i = 0, . . . , k (sonk + 1 palabras)pues sern (usando la ampliacin de la funcin ):

(q0, ), (q0, a), (q0, aa), (q0, aaa), . . . , (q0, ak)

Entonces, un estado tiene que aparecer por lo menos dos veces (se llama principio de loscajones (pigeonhole principle): si se quiere poner ms calcetines que hay cajones en loscajones, por lo menos en un cajn acaban por lo menos dos calcetines)es decir: (q0, ai) = (q0, aj) para algunos i 6= j


Entonces:

(q0, aibj) = ((q0, ai), bj)

= ((q0, aj), bj)

= (q0, ajbj) F

pues, el autmata tambin acepta aibj, i 6= j que no debe hacer. Una contradiccin!Entonces asumimos mal, es decir, no existe un autmata que acepte Lab, o en otras pal-abras, Lab no es regular.

Observamos el comportamiento del siguiente autmata:

afdcpl

w0 = 110 10w1 = 110 010 10w2 = 110 010010 10w3 = 110 010010010 10

. . .wk = x y

k z

Lema (de bombeo para lenguajes regulares): Sea L un lenguaje regular (infinito). Entoncesexiste un n IN de tal manera que cada palabra w L con |w| n se puede dividir en trespartes, w = xyz cumplindose las tres propiedades:

1. y 6= 2. |xy| n3. para todos los k 0 : xykz L

Comprobacin (ideas principales):

Sea L un lenguaje regular (infinito).Entonces existe un autmata finito determinista M que acepta L.

Sea n el nmero de estados de M (n = |Q|).Sea w una palabra con |w| n (tal palabra existe porque L es infinito).Entonces se visita un estado de M por lo menos dos veces.


Escogemos el estado que se visita la primera vez dos veces, le llamamos q.

La parte de w que se lee hasta llegar la primera vez a q llamamos x (puede ser que x = ).La parte de w que se lee hasta llegar la segunda vez a q llamamos y (y 6= porque un bucleen un AFD tiene aristas con smbolos).La longitud |xy| n porque hemos recorrido un camino dondo solo un estado aparece dosveces.

La parte que sobra para terminar aceptando w llamamos z.

Entonces dividimos w en tres partes, es decir, w = xyz.

M acepta tanto xz, como xyz, como cualquier xykz para todos los k 0 porque podemosrecorrer el bucle de y tantas veces como queremos (esto se debe comprobar formalmentecon induccin).

Entonces, comprobamos de nuevo que Lab no es regular, ahora usando el lema de bombeo:

Asumimos que Lab sea regular.

El lema de bombeo nos garantiza la existencia de un n tal que se cumplen las propiedadespara palabras w con |w| n.(Pensamos...): Elegimos w = anbn. Obviamente w Lab y |w| = 2n n.El lema de bombeo nos garantiza la existencia de una particin w = xyz con y 6= ,|xy| n, y k 0 : xykz Lab. (No conocemos la particin en concreto, pero suspropiedades.)Porque |xy| n el prefijo xy no contiene ninguna b.Porque y 6= la subpalabra y contiene por lo menos una a.Todos las bs estn en z.

Tanto xz = xy0z Lab como xy1z Lab pero xz contiene por lo menos una a menos quexyz (hemos quitado y).Eso es una contradiccin porque xz no debe estar dentro Lab.

Entonces Lab no puede ser regular.

Receta para el uso del lema de bombeo:

Dado un lenguaje L.


Queremos comprobar que L no es regular.Comprobacin con contradiccin.

Asumimos que L sea regular.

El lema de bombeo garantiza la existencia de un n (pero no lo conocemos).Buscamos w L (con un poco de sabidura) que depende de n, tal que |w| nEl lema de bombeo garantiza la existencia de la particin de w = xyz cumpliendo las 3propiedades.

Comprobamos (con un poco de sabidura) que, independiente de la particin de w en con-creto (en los lmites de las primeras dos propiedades), se produce una contradiccin con latercera propiedad.

Podemos describir dicha receta tambin como un juego para dos personas:

Juego para un lenguaje L.Jugador 1 selecciona n.

Jugador 2 selecciona w L con |w| n.Jugador 1 selecciona particin w = xyz con y 6= y |xy| n.Jugador 2 selecciona k.

si xykz / L gana jugador 2, sino gana jugador 1.si jugador 2 puede ganar siempre, entonces L no es regular.

El lema de bombeo es el jugador 1, quin es el jugador 2?Otro Ejemplo:

Lquad = {0m | m es nmero cuadrado}

es decir, todas las cadenas de ceros que tienen un nmero cuadrado de smbolos.

Asumimos que Lquad sea regular.

El lema de bombeo nos garantiza la existencia de un n tal que se cumplen las propiedadespara palabras w con |w| n.


(Pensamos...): Elegimos w = 0n2 . Obviamente w Lquad y |w| = n2 n.El lema de bombeo nos garantiza la existencia de una particin w = xyz con y 6= ,|xy| n, y k 0 : xykz Lquad. (No conocemos la particin en concreto, pero suspropiedades.)Tanto xyz Lquad como xy2z Lquad con y 6= .Tenemos entonces:

n2 = |xyz| porque es w< |xy2z| porque es y tiene una longitud > 0= |xyz|+ |y| n2 + n porque si |xy| n tambin |y| n< n2 + 2n+ 1

= (n+ 1)2

Eso es una contradiccin porque xy2z no puede ser una palabra cuya longitud es un nmerocuadrado entre dos nmeros cuadrados consecutivos.

Entonces Lquad no puede ser regular.

Dos comentarios ms:

Este lema de bombeo solo garantiza una propiedad para lenguajes regulares, es decir, todoslos lenguajes regulares (infinitos) la tienen, pero pueden existir ms lenguajes que la ten-gan, o en otras palabras, pueden existir lenguajes L donde encontramos tal n y la divisinde w en xyz con todas las propiedades, pero L no es regular.

Con el lema de bombeo tambin se puede derivar: si tal w / L entonces xykz / L (elargumento es fcil: no hace falta que lleguemos a una estado final en la comprobacin, loimportante eran los caminos recorridos).

Reglas de mano:

Un lenguaje es regular si independientemente de la longitud de la palabra de entrada, hayque memorizar solamente una cantidad constante de informacin (en el caso de Lab de-beramos memorizar el nmero de as que no es constante).La comprobacin formal se realiza con el lema de bombeo.

El lema de bombeo se usa para comprobar que un lenguaje no es regular, para comprobarque es regular, por ejemplo, se construye un autmata finito, una expresin regular, o unagrmatica de tipo 3.


Pero ojo, existen lenguajes regulares que tienen que ver con nmeros:Ltres = {w | w es codificacin de un nmero divisible por 3}

Ejercicio: contruye un autmata finito que acepte Ltres.

9. Propiedades, algoritmos de decisin,y aplicaciones para lenguajes regulares

La clase de los lenguajes regulares es una clase de alguna manera muy robusta: hay muchasposibilidades de describir los lenguajes y exhiben un gran nmero de propiedades de clausura,como vemos ahora.

9.1. Propiedades de lenguajes regularesSean L1 y L2 dos lenguajes regulares.

Unin: L = L1L2 es regular, porque podemos construir una expresin regular paraL, teniendolas expresiones regulares para L1 y L2, ms preciso: con L1 = L() y L2 = L() tenemosL = L((+ ))

Concatencin: L = L1.L2 es regular, porque podemos construir una expresin regular para L,teniendo las expresiones regulares para L1 y L2, ms preciso: con L1 = L() y L2 = L()tenemos L = L()

Clausura: L = L1 es regular, porque podemos construir una expresin regular para L, teniendola expresin regular para L1, ms preciso: con L1 = L() tenemos L = L(())

Complemento: L = L1 = L1 es regular, porque podemos construir, dado un AFD com-pleto M1 que acepta L1, un AFD M que acepta L simplemente invertiendo sus esta-dos finales, es decir, los estados no finales de M1 sern los estados finales de M y losfinales se convierten en los no finales, entonces, si M1 = (, Q, , q0, F ) construimosM = (, Q, , q0, Q F ).

Interseccin: L = L1 L2 es regular, porque con las reglas de DeMorgan obtenemos L =L1 L2 = L1 L2. Complemento y unin producen lenguajes regulares, como vistoantes. Dicha construccin es bastante laborosa, abajo vemos una construccin directa ysimple.


Diferencia: L = L1L2 es regular, porque se puede expresar la diferencia como L = L1L2 =L1 L2 = L1 ( L2) y las operaciones usadas mantienen la regularidad.

En vez de usar la lgica booleana, es decir, aplicando las reglas de DeMorgan, se puede construirdirectamente un autmata que acepta el lenguaje L = L1 L2.La idea principal es, simular en paralelo en un solo autmata (digamos autmata de producto)las transiciones de los dos autmatas (por ejemplo finitos deterministas y completas) para L1 yL2.

Entonces sean M1 = (1, Q1, 1, q1, F1) y M2 = (2, Q2, 2, q2, F2) los dos AFDs completosque aceptan L1 y L2, es decir, L1 = L(M1) y L2 = L(M2).

Construimos el AFD completo M que acepta L = L1 L2 = L(M) como

M = (, Q, , q0, F )

donde

asumimos que = 1 = 2, es decir, usamos solamente los smbolos comunes. Es fcileliminar en M1 y en M2 todas las dependencias de smbolos superflues antemano en casoque haya.

Q = Q1 Q2, es decir, el producto cartesiano de los estados de M1 y M2. es la funcin de transicin con

((p, q), ) = (1(p, ), 2(q, ))

para p Q1, q Q2 y .q0 = (q1, q2), es decir, la pareja de los dos estados inicialesF = F1F2, es decir, todas las parejas donde ambos estados son estados finales de ambosautmatas.

Ejemplo:afdprod

Obviamente la construccin funciona igual con autmatas finitos nodeterministas (AFND).

Homomorfismo: a lo mejor lo incluyo.


9.2. Algoritmos de decisin de lenguages regulares

Pertenencia: w L? s, se puede contestar la pregunta (es decir, es un problema computable),porque

construimos un AFD M que acepte Lsimulamos su comportamiento leyendo la palabra wsi acabamos en un estado final, w est en L, sino w no est en L

Vaciedad: L = ? s, se puede contestar la pregunta (es decir, es un problema computable)porque

construimos un autmata que acepte Lanalizamos el grafo del autmata para averiguar si existe un camino desde el estadoincial hacia un estado final (dicho proceso resulta ms fcil, si se aade un estado yse conecta todos los estados finales a este estado, as basta buscar un camino entre elestado inicial y el estado aadido)si existe tal camino, entonces L no es vaco, sino L es vaco lrempty

Cardinalidad: |L| < ? s, se puede contestar la pregunta (es decir, es un problema com-putable) porque

construimos un autmata que acepte Lanalizamos el grafo del autmata para averiguar si existe un ciclo en un camino entreel estado inicial y algn estado finalsi existe tal ciclo, entonces L es infinito, sino L es finito

Igualidad: L1 = L2? s, se puede contestar la pregunta (es decir, es un problema computable)porque

construimos los autmatas finitos deterministas y mnimos que acepten L1 y L2comparamos la estructura de los grafos de ambos autmatassi son iguales, entonces ambos lenguajes son iguales, sino son diferentes(Nota: comparar dos grafos generales y decidir si son iguales ,es decir, el problema deisomorfa de grafos, es un problema que se puede calcular, pero todava no se conoceel algoritmo ptimo. Para los AFD mnimos se reduce la complejidad porque lasaristas llevan atributos y se conoce ambos estados iniciales que tengan que coincidir.)


9.3. Aplicaciones para lenguajes regularesAnlisis sintctico: El trabajo de un compilador es la traduccin de algn cdigo fuente (escrito

en un lenguaje de programacn, es decir, el cdigo fuente no es nada ms que una palabra(larga) sobre el alfabeto de los smbolos permitidos) en una serie de instrucciones para unprocesador.En la primera fase, el compilar analiza lexicogrficamente el texto, es decir, transforma conla ayuda de autmatas finitos, el texto continuo en una secuencia de entidades, llamadastoken, por ejemplo, palabras claves, valores numricos, operadores, comentarios, etc.Existen herramientas para el desarrollador que ayudan en la construccin de dichos aut-matas, cuyas entradas suelen ser expresiones regulares y cdigo de accin y cuyas salidasson programas que realizan la tarea del anlisis lexicogrfico. Un ejemplo es lex para unsistema Unix.

Bsqueda de palabras en texto: Existen herramientas para el desarrollador que ayudan en labsqueda de secuencias de texto descritas por expresiones regulares. Un ejemplo es greppara un sistema Unix o comandos internos a editores como el vi o emacs.

Diagramas de estados en UML: El lenguaje UML (unified modeling language) se usa para ladescripcin durante el proceso de desarrollo de software. El lenguaje grfico usa diferentestipos de diagramas para este fin. Uno de ellos son los diagramas de estados que visualizanel cambio de estados de los objetos debido al paso de mensajes entre ellos.

10. Lenguajes libres de contexto

Lo que ya visto:

Lab = {anbn | n 0}Labc = {anbncn | n 0}Lpal = {w | w {0, 1}, w = vvR}Ldup = {w | w {0, 1}, w = vv}Lquad = {0n2 | n nmero cuadrado}Lprim = {0n | n nmero primo}L() = {w | w {(, )}, w correcto}


Una gramtica libre de contexto es una cudrupla

G = (N ,T , P, $)

donde

N es un alfabeto de smbolos noterminales (o variables)T es un alfabeto de smbolos terminales (o constantes)P N (N T )+ {$ } es un sistema de producciones (o reglas)$ N es el smbolo inicial

Es decir, la definicin de las gramticas libres de contexto nos da mucha libertad para el sistemade producciones.

Por eso (y tambin para otros objetivos como por ejemplo mostrar que existe un tipo de autmataque justamente acepta lenguajes libres de contexto como veremos en adelante) se ha desarrolladoformas normales de la representacin de gramticas libres de contexto, es decir, se transforma elsistema de producciones de la gramtica de tal manera que no se vara el lenguaje generado perolas reglas tengan cierta propiedad.

Especialmente la definicin arriba exluye reglas de forma X siendo X un smbolo noterminal diferente a $, sin embargo, si permitesemos tales producciones, es decir, permitir P N (N T ), obtendramos los mismos lenguajes, porque, como veremos a continuacin,dichas producciones se pueden eliminar sin cambiar el lenguaje que genera la gramtica.

10.1. Forma Normal de Chomsky

Sea G = (N ,T , P, $) una gramtica con P N (N T ) y X N un smbolonoterminal (o una variable). Podemos clasificar tales smbolos X en tres clases:

variables acesibles: si existe una derivacin desde el smbolo inicial que contiene X , es decir,existe $ X donde , .

variables generativas: si existe una derivacin desde el la variable que produce una sentenciaw, es decir, existe X w donde w T .

variables tiles: si existe una derivacin desde el smbolo inicial usando X que produce unasentencia w, es decir, existe $ X w donde , y w T .

Una gramtica est en forma normal de Chomsky (FNC)


si G (es decir, su N ) solamente contiene variables tiles ysi todas las producciones de G (es decir, en su P ) son o bien de la forma X Y Z con X,Y, Z N o bien de la forma X con X N y T

si $ (es decir, el smbolo inicial de G) no aparece al lado derecho de ninguna produccin,tambin est permitido que $ P .

La tercera condicin es necesaria para poder derivar . Si $ aparece a la derecha, primero habrque sustituir las producciones implicadas adecuadamente como lo vimos en la conversin de unagramtica lineal por la derecha a una gramtica lineal por la izquierda.

Observamos:

la primera condicin garantiza que todas las variables

teoria de automatas y lenguajes formales

Documents