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 la 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 si es GRD o 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 una 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 carácter es una mayúscula o un subrayado
w = w[1:] #Se quita el primer carácter
while w and (w[0].isalnum() or w[0]=='_'):
#Mientras queden caracteres en "w" y el primer carácter actual sea un alfanumérico o un subrayado, todo está bien
w = w[1:] #Quitar el primer carácter
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áticas 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 imágenes 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 imágenes pares pueden 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.

• Lenguaje regular.
• Expresión regular.
• Flex.
• Jerarquía de Chomsky.

Fuentes

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