Gramática regular
| ||||||
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.
Sumario
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
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.
