En informática teórica y teoría del lenguaje formal , una gramática regular es una gramática regular por la derecha o por la izquierda . Si bien su definición exacta varía de un libro de texto a otro, todos requieren que
Cada 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 de inicio.
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 solo símbolos terminales y pueden derivarse del símbolo inicial mediante la aplicación repetida de reglas de producción. Dos gramáticas se denominan débilmente equivalentes si describen el mismo lenguaje.
No se deben mezclar reglas de ambos tipos; por ejemplo, la gramática con el 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 derecha (o gramática lineal derecha ) [1] y al tipo anterior gramática estrictamente regular derecha (o gramática estrictamente lineal derecha ). [2]
Una gramática regular izquierda extendida 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*, es decir, el conjunto de todas las cadenas que constan de un número arbitrario de " a ", seguidas de una única " b ", seguidas de un número arbitrario de " c ".
Una gramática regular derecha extendida algo más larga pero más explícita G 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 en la expresión regular.
Como ejemplo del área de lenguajes de programación, el conjunto de todas las cadenas que denotan un número de punto 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 de inicio y P consta de las siguientes reglas:
Existe una correspondencia directa biunívoca entre las reglas de una gramática (estrictamente) regular-derecha y las de un autómata finito no determinista , de modo que la gramática genera exactamente el lenguaje que el autómata acepta. [3] Por lo tanto, las gramáticas regulares-derechas generan exactamente todos los lenguajes regulares . Las gramáticas regulares-izquierdas describen los reversos de todos esos lenguajes, es decir, también exactamente los lenguajes regulares.
Toda gramática regular derecha estricta es regular derecha extendida, mientras que toda gramática regular derecha extendida puede hacerse estricta insertando nuevos no terminales, de modo que el resultado genere el mismo lenguaje; por lo tanto, las gramáticas regulares derechas extendidas generan también los lenguajes regulares. Análogamente, lo mismo ocurre con las gramáticas regulares izquierdas extendidas.
Si no se permiten producciones vacías, solo se podrán generar todos los idiomas regulares que no incluyan la cadena vacía. [4]
Si bien las gramáticas regulares sólo pueden describir lenguajes regulares, lo inverso no es cierto: los lenguajes regulares también pueden ser descritos por gramáticas no regulares.
Si se permite la mezcla de reglas regulares de izquierda y de derecha, todavía tenemos una gramática lineal , pero no necesariamente regular. Es más, una gramática de este tipo no necesita generar un lenguaje regular: todas las gramáticas lineales pueden llevarse fácilmente a esta forma y, por lo 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 de inicio S y reglas
genera , el lenguaje lineal no regular paradigmático.
