Gramática regular

Gramática regular Concepto: Gramática que permite la definición de lenguajes regulares o de tipo 3.

Gramática regular. En Lingüística, Matemáticas e Informática y en la jerarquía de Chomsky se refiere a las gramáticas que definen a los lenguajes de tipo 3 o lenguajes regulares.

Se dividen en dos tipos fundamentales según la forma de sus producciones.

• Gramática regular derecha.
• Gramática regular izquierda.

Dependiendo de si la recursión de los símbolos no terminales se produce a la derecha o izquierda respectivamente.

Definiciones.

Se define una gramática formal G como la cuarteta <N,T,P,S> donde N es el conjunto de símbolos no terminales, S es un símbolo de N que identifica el símbolo inicial o de partida, T es el alfabeto o conjunto de símbolos terminales y P es el conjunto de reglas de la forma donde y contiene al menos un no terminal de N.

Gramática regular derecha (GRD).

Sea una gramática G=<N,T,P,S> se dice que la misma es gramática regular derecha (GRD) si todas sus producciones tienen una de estas formas:

• 
• 
• 

donde A y B son elementos no terminales de N, x es un símbolo del alfabeto T y es la cadena vacía.

Gramática regular izquierda (GRI).

Sea una gramática G=<N,T,P,S> se dice que la misma es gramática regular izquierda (GRI) si todas las producciones en P tienen una de estas formas:

• 
• 
• 

donde A y B son elementos no terminales de N, x es un símbolo del alfabeto T y es la cadena vacía.

Gramática regular.

G es una gramática regular ssi es GRD ó GRI.

Ejemplos.

Ejemplo 1.

Demuestre que el lenguaje conformado por los nombres de variables de PROLOG es un lenguaje regular.

Primero debe recordarse que un nombre de variable PROLOG viene dada por la forma:

cualquier palabra que comience con una letra mayúscula seguida o no de combinaciones de letras, cifras o subrayados o que comience con al menos un subrayado seguido o no de cualquier secuencia de alfanuméricos o subrayados.

Cada de las siguientes construcciones son equivalentes en virtud de la definición dada antes:

• Una gramática regular derecha <{S,F},{_;0...9;A...Z;a...z},P,S>con las producciones P conformadas por:
  • .
  • .
• La expresión regular (_|(A|B|...|Z))(A|B|...|Z|a|b|...|z|_)*.
• El siguiente autómata finito representado como diagrama de estados permite el reconocimiento de variables de PROLOG.
  • 

o la definición de la función reconocedora hecha en Python:

def variablePROLOG(w):
        '''(str)-->bool. True si "w" es un nombre de variable correcto'''
        if (w[0].isalpha and w[0]==w[0].upper()) or w[0]=='_':
                #El primer caracter es una mayuscula o un subrayado
                w = w[1:] #Se quita el primer caracter
                while w and (w[0].isalnum() or w[0]=='_'):
                        #Mientras queden caracteres en "w" y el primer caracter actual sea un alfanumerico o un subrayado, todo esta bien
                        w = w[1:] #Quitar el primer caracter
                if w=='':
                        #Si ya no quedan elementos a revisar, es una variable PROLOG
                        return True
        return False

En todos los casos se percibe la estrecha relación entre las gramáica regulares y las demás formalizaciones de lenguajes regulares.

Ejemplo 2.

En un acuario de Miami se entrenan las capacidades intelectuales de los delfines en cautiverio y tiene especial importancia los resultados que tiene uno de los ejemplares quien ha aprendido a reconocer cantidades pares a partir de imagenes de peces, llegando a distinguir cuando hay un número par o no de peces en la imagen. Muestre que las imágenes de cantidad de peces pares es un lenguaje regular que puede percibir el delfín.

Se define a cada pez de las imágenes con la letra p minúscula y se ve que para las imagenes pares puede definirse las siguientes producciones P de una gramática regular <{I},{p},P,I>:

• 

Por ende, se trata de un LR.

Ejemplo 3.

Defina una gramática regular que permita reconocer números naturales.

Primero, desde el punto de vista lexicográfico un número natural en base decimal es al menos un dígito entre 1 y 9, seguido o no de una secuencia de cifras decimales.

La gramática para representarlos podría ser:

Naturales=<{U,N}.{0,1,2,3,4,5,6,7,8,9},P,U> con el conjunto de producciones P dado por:

• .
• .

Véase también.

• Autómata finito.
• Expresión regular.
• Flex.
• Jerarquía de Chomsky.

Fuentes.

1. Tanembaum, A. Compilers: Principles, Tecniques, and Tools. Tomo 1. ACM Press. 5ta Edición.
2. Conferencias de la Asignatura "Compilación 1" del Departamento de Ciencias de la Computación de la Universidad de Oriente. Santiago de Cuba, 2000.
3. Lenguajes regulares en Wikipedia.