Gramática regular

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.

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:

• .
• .