Home

GRAMÁTICAS REGULARES

 

1.5.1. Gramáticas formales

     Gramática es un conjunto de reglas que estructuran la formación de un lenguaje. Una frase en español tendría las siguientes reglas gramaticales:

< frase >  < sujeto > < predicado > < punto >
< sujeto >  < sustantivo >
< sustantivo >  María
<sustantivo >  Juan
< predicado >  < verbo intransitivo >
< predicado >  < verbo transitivo > < objeto >
< verbo intransitivo >  patinar
< verbo transitivo >  golpear
< verbo transitivo >  quiere < objeto >
< objeto >  a < sustantivo >
< punto >  .

     Una gramática estará formada por los siguientes elementos

     El conjunto de terminales, no terminales, símbolo de inicio y un conjunto finito de reglas de reescritura constituye lo que se denomina gramática estructurada por frases.

     Denotar que puede darse el caso de que haya varias reglas de reescritura que tengan el símbolo de inicio en su parte izquierda; esto es necesario para que una misma gramática represente patrones distintos de cadenas.

     Formalmente, una gramática está definida por la cuádrupla (V,T,S,R) donde:

     En general los dos lados de las reglas de reescritura pueden ser combinaciones de terminales y no terminales, la parte izquierda siempre debe tener al menos un no terminal. El lado derecho puede tener la cadena vacía, la cual se denomina regla  .

     A partir de ahora vamos a representar los terminales con letras en minúscula y los no terminales con mayúsculas.

     La derivación de una cadena consiste en generar una cadena aplicando las reglas de la gramática. Se puede derivar si al comenzar con el símbolo de inicio, se puede producir esa cadena sustituyendo sucesivamente los patrones de la izquierda por las expresiones del lado derecho correspondiente, hasta que solo quedan terminales.

     Sea una gramática G cualquiera; si sus terminales son símbolos de un alfabeto  decimos que G es una gramática de y las cadenas generadas por ella pertenecen a * ; la gramática G del alfabeto  especifica un lenguaje y se representa por L(G).

 

1.5.1. Gramáticas regulares

     Se llama gramática regular a aquella que en sus reglas de reescritura tiene las siguientes restricciones:

     En el caso de no querer reglas con solo un terminal (b.2), estas se pueden sustituir por dos reglas de reescritura, una cuya parte derecha será siempre un terminal seguido de un no terminal, el cual no existía en la gramática original y la otra cuya parte izquierda es ese no terminal nuevo y la derecha es la cadena vacía.

   N x      se sustituye por      N  xX

X  

TEOREMA Para cada alfabeto , {L(G): G es una gramática regular de } = {L(M): M es una autómata finito de } (los lenguajes generados por gramáticas regulares son exactamente los lenguajes que aceptan los autómatas finitos).

DEMOSTRACIÓN

     Sea G una gramática regular. Primero tenemos que convertirla en una gramática G' que genera el mismo lenguaje pero que no contiene reglas de reescritura cuyo lado derecho sea solo un terminal (como se vio antes). Definimos el autómata finito M como el autómata finito no determinista (S,  , ,  , F) donde:

  1. S es la colección de no terminales de G'
  2.  es el símbolo inicial de G’
  3. F es la colección de no terminales de G' que aparecen en el lado izquierdo de alguna regla 
  4.  consiste en la tripleta (P, x, Q) (de aquí que el autómata sea no determinista)para el cual G' contiene una regla de reescritura de la forma P xQ

     Al revés, sea M un autómata finito no determinista (S, , , , F), entonces podemos definimos la gramática regular G' del alfabeto  tal que:

  1. los no terminales definen el conjunto de estados S de M
  2. el símbolo inicial es 
  3. las reglas de reescritura son de la forma P xQ si la tripleta (P, x, Q) está en  (si existe la transición del estado P al Q con la etiqueta x)
  4. y Q   si Q está en F.

     L(M) = L(G') ya que la derivación de la cadena corresponde con la ruta a seguir en el diagrama de transiciones de M

     Hay que aclarar dos conceptos: en primer lugar se trata de un autómata finito no determinista debido a que se están haciendo equivalencias con tripletas, y no con una función; en segundo lugar hay que tener en cuenta que pueden existir gramáticas no regulares que definan un lenguaje regular.

 EXPRESIONES REGULARES.

     Construiremos lenguajes regulares más complejos a partir de otros lenguajes regulares pequeños. Los lenguajes más simples del alfabeto  serán cadenas simples de longitud uno. Sin embargo, con estos no podremos construir el lenguaje vacío  ni el lenguaje {}. 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  ={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  L2L1 ).

     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, , 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, **={ }.

     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  se define como:

     Para cada expresión regular r de un alfabeto  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  (tiene que ser el mismo), los lenguajes regulares de  son exactamente los lenguajes representados por las expresiones regulares de .

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* s  t*). Si existe u entonces la expresión queda ((r*  s  t*)  (u  (r*  s  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  ={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', ' , ', ', 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. ' = .
  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  n.
  4. El estado inicial será aquel que está formado por los estados iniciales originales: ' = ( 1, 2, 3,..., n).
  5. Los estados de aceptación serán aquellos que están formados por estados de aceptación originales. F' = (F1,F2,F3,..., Fn).