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.