1.6. EXPRESIONES REGULARES.

     Construiremos lenguajes regulares más complejos a partir de otros lenguajes regulares pequeños. Los lenguajes más simples del alfabeto S serán cadenas simples de longitud uno. Sin embargo, con estos no podremos construir el lenguaje vacío Æ ni el lenguaje { l}. Cojamos como base la colección de bloques que contiene el lenguaje vacío y todos los lenguajes de cadenas simples de longitud uno (luego se verá porque no se coge la cadena vacía como bloque de formación). Para un mismo alfabeto y con las operaciones de unión, concatenación y estrella de Kleene de los bloques de construcción, podremos construir otros lenguajes regulares más complejos.

 

1.6.1. Unión de lenguajes

     La unión de dos lenguajes regulares es otro lenguaje regular. Se utiliza la operación de unión de conjuntos; así, para el alfabeto S ={x,y} si L1 = {x,xy} y L2 = {yz,yy} entonces su unión será L1 È L2 = {x,xy,yz,yy }.

     Para modificar los diagramas de transiciones deberemos conseguir que se vaya a una u otra de las estructuras originales, pero sin mezclarlas (si se mezclan, se admitirían cadenas que no pertenecen al lenguaje). Para ello cogeremos los diagramas originales de los dos lenguajes. Se dibuja un estado nuevo:

  1. Será el nuevo estado inicial
  2. Será de aceptación si alguno de los estados iniciales de los diagramas originales lo era
  3. Por cada uno de los arcos que hay desde los estados iniciales originales hacia otros (puede ser el mismo), se dibuja desde el nuevo estado inicial un arco hacia el estado destino del arco correspondiente en el diagrama original y se etiqueta con el mismo símbolo
  4. A continuación se elimina la característica de inicio de los estados iniciales originales.

 

1.6.2. Concatenación de lenguajes

La concatenación de dos lenguajes regulares es otro lenguaje regular. Se concatenan una cadena del primer lenguaje y una cadena del segundo. Con L1 y L2 anteriores la concatenación (que se denota °) será L1 ° L2 ={xyx,xyy,xyyz,xyyy}. La concatenación no es conmutativa (L1 ° L2 ¹ L2 ° L1 ).

     Cogemos los diagramas originales de los dos lenguajes:

  1. Se dibuja el diagrama original de L1
  2. desde cada estado de aceptación del diagrama de L1 se dibuja un arco hacia cada estado de L2 que sea el destino de un arco del estado inicial de L2 y se rotula con el mismo símbolo
  3. Dejar que los estados de aceptación de L1 lo sean si el estado inicial de L2 también lo es.

 

1.6.3. Estrella de Kleene

     La estrella de Kleene de cualquier lenguaje regular también es regular. Se caracteriza por que se utiliza solo un lenguaje en lugar de dos. Se logra formando todas las concatenaciones de cero (cadena vacía) o más cadenas del lenguaje que se amplía. La operación se representa con el asterisco supraíndice ( * ).

     Como se vio al principio de este apartado, la cadena vacía, l, no se consideraba como uno de los bloques de formación de lenguajes, y es porque se genera a partir de Æ por medio de la estrella de Kleene; la cadena vacía pertenece a la estrella de Kleene de cualquier lenguaje posible y por lo tanto debe pertenecer a Æ* y, por tanto, Æ**={l }.

     Para modificar el diagrama de transiciones, se coge el diagrama:

  1. Se añade un nuevo estado que va a ser el de inicio
  2. Este nuevo estado inicial también lo marcaremos como de aceptación (para que así puede aceptar la cadena vacía)
  3. Por cada uno de los arcos que hay desde el estado inicial original hacia otros (puede ser el mismo), se dibuja desde el nuevo estado inicial un arco hacia el estado destino del arco correspondiente en el diagrama original y se etiqueta con el mismo símbolo
  4. Desde cada estado de aceptación se dibuja un arco por cada uno de los que salen desde el estado inicial original hacia otros (puede ser el mismo). Este sale hacia el estado destino del arco correspondiente que salía del estado inicial en el diagrama original y se etiqueta con el mismo símbolo.
  5. Se quita la característica de inicio del estado inicial original.

 

1.6.4 Expresiones regulares

     Una expresión regular para un alfabeto S se define como:

  • Æ es una expresión regular
  • Cada miembro de S es una expresión regular
  • Si p y q son expresiones regulares, entonces también lo es (p È q)
  • Si p y q son expresiones regulares, entonces también lo es (p ° q)
  • Si p es regular, entonces también lo es p*

     Para cada expresión regular r de un alfabeto S representa un lenguaje L(r). Además, si p y q son expresiones regulares, L(p È q) = L(p) È L(q), L(p °q) = L(p) °L(q) y L(p*) = L (p) *.

     Las expresiones regulares también especifican lenguajes (al igual que diagramas tablas, autómatas y gramáticas) . Son una manera concisa de expresar lenguajes regulares (en una sola línea se puede describir un autómata finito completo).

TEOREMA.- Dado un alfabeto S (tiene que ser el mismo), los lenguajes regulares de S son exactamente los lenguajes representados por las expresiones regulares de S.

DEMOSTRACIÓN

     Lo primero que hay que tener en cuenta es que un lenguaje representado por una expresión regular es regular (demostrado en los subapartados anteriores). Lo siguiente que haremos será representar con una expresión regular cualquier lenguaje aceptado por un autómata finito. Además, vamos a considerar válidos unos diagramas, que llamaremos generalizados, en los que los arcos van a estar etiquetados con expresiones regulares, en lugar de sólo símbolos. Para ello, vamos a ir reduciendo el diagrama hasta tener solo uno o dos estados:

  1. Llamemos T al diagrama de transiciones original. Se hacen tantas copias de T como estados de aceptación haya. Cada Ti tendrá sólo un estado de aceptación distinto. La expresión regular resultante será la unión de cada una de las expresiones resultantes de cada Ti (T = T1 È T2 È .... È Tn)
  2. Considerando por separado cada Ti, y para ir reduciendo el diagrama estado por estado, se usan las operaciones que se definieron anteriormente:
  3. Unión.- Si hay varios arcos que conectan en la misma dirección dos estados, estos se puede sustituir por uno etiquetado con la unión de las expresiones de esos arcos
  4. Estrella de Kleene.- La expresión regular será la unión de las etiquetas de los arcos que salen e inciden en un mismo estado
  5. Concatenación.- Hay dos casos: dado un estado, si solo tiene un arco incidente y otro saliente, la expresión resultante será la concatenación de las etiquetas del arco incidente y la del saliente; si en el estado tiene un arco solo incidente, arcos que salen e inciden en el mismo estado y un solo arco saliente, la expresión resultante será la concatenación de la etiqueta del arco incidente, la estrella de Kleene de la unión de las etiquetas de los arcos que iban del estado al mismo y la etiqueta del arco saliente por ese orden.

     Estas operaciones se van aplicando estado a estado, de manera que nos van quedando sucesivamente diagramas con n estados, n-1 estados, ..., 3 estados, y 2 ó 1 estado. En estos dos últimos casos:

  1. Si el diagrama T queda con sólo un estado, que es inicial y de aceptación a la vez, la expresión resultante es la estrella de Kleene de la unión de las etiquetas de los arcos que salen e inciden en este mismo estado.
  2. Que T quede con dos estados, uno inicial, y el otro de aceptación. Aquí se pueden tener alguno o todos de estos 4 arcos: (r)del inicial al inicial, (s) del inicial al de aceptación, (t) de aceptación a aceptación y (u) de aceptación al inicial. Si s no existe entonces la expresión regular es la cadena vacía, pues no se puede llegar a algún estado de aceptación. Si existe s pero no u entonces la expresión regular es (r* o s o t*). Si existe u entonces la expresión queda ((r* o s o t*) o (u o (r* o s o t*))*). Si r y t no existen son sustituidos por Æ. Aquí r* representa la unión de las etiquetas de los arcos que salían y entraban en el mismo estado, como se dijo anteriormente.

1.6.5. Intersección de lenguajes

     La intersección de varios lenguajes regulares es otro lenguaje regular. Se utiliza la operación de intersección de conjuntos; así, para el alfabeto S ={x,y} si L1 = {x,xy,yy}, L2 = {yz,yy} y L3 = {y,yy} entonces su intersección será L1 Ç L2 ÇL3 = {yy}.

     Para diseñar el autómata que reconoce este lenguaje, vamos a considerar los autómatas finitos L(Mn). El nuevo autómata estará definido por la quintupla (S', S' ,d ', i', F'), donde:

  1. S' será el producto cartesiano de todos los conjuntos de estados originales S' = S1 x S2 x S3 x...x Sn.
  2. El alfabeto tiene que ser el mismo para todos los autómatas. S' = S .
  3. La transición desde el estado p=(p1,p2,p3,...,p n) al estado q=(q1,q2,q3,...,qn)de S' (todas las transiciones posibles), para un símbolo del alfabeto, si y solo si existe la transición desde pi a qi para todo i e n.
  4. El estado inicial será aquel que está formado por los estados iniciales originales: i' = ( i1, i2, i3,..., in).
  5. Los estados de aceptación serán aquellos que están formados por estados de aceptación originales. F' = (F1,F2,F3,..., Fn).

 

principal  anterior  siguiente

 

© 1999 Roberto de la Fuente López. Todos los derechos reservados

Fecha de actualización: 15 de abril de 1999