En informática teórica y teoría del lenguaje formal , una gramática regular es una gramática que es regular a la derecha o regular a la izquierda . Si bien su definición exacta varía de un libro de texto a otro, todos requieren que
Toda gramática regular describe un lenguaje regular .
Una gramática regular derecha (también llamada gramática lineal derecha ) es una gramática formal ( N , Σ, P , S ) en la que todas las reglas de producción en P son de una de las siguientes formas:
donde A , B , S ∈ N son símbolos no terminales, a ∈ Σ es un símbolo terminal y ε denota la cadena vacía , es decir, la cadena de longitud 0. S se llama símbolo inicial.
En una gramática regular por la izquierda (también llamada gramática lineal por la izquierda ), todas las reglas obedecen a las formas
El lenguaje descrito por una gramática dada es el conjunto de todas las cadenas que contienen sólo símbolos terminales y pueden derivarse del símbolo inicial mediante la aplicación repetida de reglas de producción. Dos gramáticas se llaman débilmente equivalentes si describen el mismo idioma.
No deben mezclarse normas de ambos tipos; por ejemplo, la gramática con conjunto de reglas { S → aT , T → Sb , S→ε } no es regular y describe el lenguaje , que tampoco es regular.
Algunos libros de texto y artículos no permiten reglas de producción vacías y asumen que la cadena vacía no está presente en los idiomas.
Una gramática regular derecha extendida es aquella en la que todas las reglas obedecen a una de
Algunos autores llaman a este tipo de gramática gramática regular por la derecha (o gramática lineal por la derecha ) [1] y al tipo anterior gramática estrictamente regular por la derecha (o gramática estrictamente lineal por la derecha ). [2]
Una gramática extendida regular por la izquierda es aquella en la que todas las reglas obedecen a una de
Un ejemplo de una gramática regular derecha G con N = {S, A}, Σ = {a, b, c}, P consta de las siguientes reglas
y S es el símbolo de inicio. Esta gramática describe el mismo lenguaje que la expresión regular a*bc*, a saber. el conjunto de todas las cadenas que consta de muchas " a " arbitrarias, seguidas de una sola " b ", seguida de muchas " c " arbitrarias.
Una gramática regular derecha G algo más larga pero más explícita para la misma expresión regular viene dada por N = {S, A, B, C}, Σ = {a, b, c}, donde P consta de las siguientes reglas:
...donde cada letra mayúscula corresponde a frases que comienzan en la siguiente posición de la expresión regular.
Como ejemplo del área de los lenguajes de programación, el conjunto de todas las cadenas que denotan un número de coma flotante se puede describir mediante una gramática regular derecha extendida G con N = {S,A,B,C,D,E,F}, Σ = {0,1,2,3,4,5,6,7,8,9,+,−,.,e}, donde S es el símbolo inicial y P consta de las siguientes reglas:
Existe una correspondencia directa uno a uno entre las reglas de una gramática regular (estrictamente) correcta y las de un autómata finito no determinista , de modo que la gramática genera exactamente el lenguaje que acepta el autómata. [3] Por lo tanto, las gramáticas regulares por la derecha generan exactamente todos los lenguajes regulares . Las gramáticas regulares por la izquierda describen los reversos de todos esos lenguajes, es decir, exactamente también los lenguajes regulares.
Cada gramática regular a la derecha estricta se extiende a la derecha regular, mientras que cada gramática regular a la derecha extendida se puede hacer estricta insertando nuevos no terminales, de modo que el resultado genere el mismo lenguaje; por lo tanto, las gramáticas regulares extendidas por la derecha también generan los lenguajes regulares. De manera análoga, también lo hacen las gramáticas regulares extendidas por la izquierda.
Si no se permiten producciones vacías, solo se podrán generar todos los idiomas normales que no incluyan la cadena vacía. [4]
Si bien las gramáticas regulares sólo pueden describir lenguajes regulares, lo contrario no es cierto: los lenguajes regulares también pueden describirse mediante gramáticas no regulares.
Si se permite la combinación de reglas regulares por izquierda y regulares por derecha, todavía tenemos una gramática lineal , pero no necesariamente regular. Es más, dicha gramática no necesita generar un lenguaje regular: todas las gramáticas lineales pueden adoptarse fácilmente en esta forma y, por tanto, dichas gramáticas pueden generar exactamente todos los lenguajes lineales , incluidos los no regulares.
Por ejemplo, la gramática G con N = {S, A}, Σ = {a, b}, P con símbolo inicial S y reglas
genera , el paradigmático lenguaje lineal no regular.
