1.5. 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

  • Los términos que no aparecen entre corchetes son terminales
  • Los que están entre corchetes son no terminales (los corchetes se utilizan para distinguir entre terminal y no terminal)
  • Uno de los no terminales se le considera como símbolo de inicio
  • Cada una de las líneas se llama regla de reescritura, la cual consiste en una parte izquierda y otra parte derecha conectadas por una flecha. La parte derecha es una descripción más detallada de la izquierda.

     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:

  • V es un conjunto finito de no terminales
  • T un conjunto finito de terminales
  • S (un elemento de V) es el símbolo de inicio
  • R el conjunto finito de reglas de reescritura

     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 l .

     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 S decimos que G es una gramática de S y las cadenas generadas por ella pertenecen a S* ; la gramática G del alfabeto S 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:

  • Su lado izquierdo debe consistir en un solo no terminal
  • Su lado derecho debe estructurarse
    1. Un terminal seguido de un no terminal
    2. Un terminal solo
    3. La cadena vacía

     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 ® l

TEOREMA Para cada alfabeto S, {L(G): G es una gramática regular de S} = {L(M): M es una autómata finito de S} (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, S , r, i , F) donde:

  1. S es la colección de no terminales de G'
  2. i 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 l
  4. r 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, S, r, i , F), entonces podemos definimos la gramática regular G' del alfabeto S tal que:

  1. los no terminales definen el conjunto de estados S de M
  2. el símbolo inicial es i
  3. las reglas de reescritura son de la forma P ® xQ si la tripleta (P, x, Q) está en r (si existe la transición del estado P al Q con la etiqueta x)
  4. y Q ® l 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.

 

principal  anterior  siguiente

 

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

Fecha de actualización: 15 de abril de 1999