Gramática regular

En informática teórica y teoría del lenguaje formal, una gramática regular es una gramática que es regular por la derecha o regular por la izquierda. Si bien su definición exacta varía de un libro de texto a otro, todos requieren que

• todas las reglas de producción tienen en la mayoría de un símbolo no final;
• ese símbolo es siempre al final o siempre al comienzo del lado derecho de la regla.

Toda gramática regular describe un lenguaje regular.

Gramáticas estrictamente regulares

Una gramática regular derecha (también llamada gramática lineal derecha) es una gramática formal (N, Σ, P, S) en el que todas las reglas de producción en P son de una de las siguientes formas:

1. A → a
2. A → aB
3. A → ε

donde A, B, S ∈ N son símbolos no terminales, a< /i> ∈ Σ es un símbolo terminal, y ε denota la cadena vacía, es decir, la cadena de longitud 0. S se denomina 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

1. A → a
2. A → Ba
3. A → ε

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 de inicio mediante la aplicación repetida de reglas de producción.

Las reglas de ambos tipos no deben mezclarse; por ejemplo, la gramática con el conjunto de reglas { S→aT, T→Sb, S→ε } no es regular, y describe el idioma { aⁱbⁱ: i ▪ ${displaystyle mathbb {N}$ }, 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.

Gramáticas regulares extendidas

Y la gramática derecha-regular extendida es aquella en la que todas las reglas obedecen a una de

1. A → w, donde A es un no-terminal en N y w está en una cadena (posiblemente vacía) de terminales^*
2. A → wB, donde A y B están dentro N y w está en la^*.

Algunos autores llaman a este tipo de gramática una gramática regular por la derecha (o gramática lineal por la derecha) y el tipo anterior una gramática estrictamente regular por la derecha< /i> (o gramática estrictamente lineal a la derecha).

Una gramática regular izquierda extendida es aquella en la que todas las reglas obedecen a una de

1. A → w, donde A es un no-terminal en N y w está en la^*
2. A → Bw, donde A y B están dentro N y w está en la^*.

Ejemplos

Un ejemplo de gramática regular derecha G con N = {S, A}, Σ = {a, b, c}, P< /i> consta de las siguientes reglas

S → aS

S → bA

A → ε

A → cA

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 arbitrariamente de muchas "a"s, seguidas de una única "b", seguida de arbitrariamente muchos "c"s.

Una gramática regular derecha extendida algo más larga pero más explícita G para la misma expresión regular está dada por N = {S, A, B, C}, Σ = {a, b, c}, donde P consta de las siguientes reglas:

S → A

A → aA

A → B

B → bC

C → ε

C → cC

... 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 los 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:

S → +A	A → 0A	B → 0C	C → 0C	D → +E	E → 0F	F → 0F
S → -A	A → 1A	B → 1C	C → 1C	D → -E	E → 1F	F → 1F
S → A	A → 2A	B → 2C	C → 2C	D → E	E → 2F	F → 2F
	A → 3A	B → 3C	C → 3C		E → 3F	F → 3F
	A → 4A	B → 4C	C → 4C		E → 4F	F → 4F
	A → 5A	B → 5C	C → 5C		E → 5F	F → 5F
	A → 6A	B → 6C	C → 6C		E → 6F	F → 6F
	A → 7A	B → 7C	C → 7C		E → 7F	F → 7F
	A → 8A	B → 8C	C → 8C		E → 8F	F → 8F
	A → 9A	B → 9C	C → 9C		E → 9F	F → 9F
	A →.B		C → eD			F → ε
	A → B		C → ε

Poder expresivo

Existe una correspondencia biunívoca directa entre las reglas de una gramática (estrictamente) regular 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. Por tanto, las gramáticas regulares correctas generan exactamente todos los lenguajes regulares. Las gramáticas regulares de izquierda describen los reversos de todos esos lenguajes, es decir, exactamente también los lenguajes regulares.

Toda gramática regular derecha estricta es regular derecha extendida, mientras que toda gramática regular derecha extendida puede volverse estricta insertando nuevos no terminales, de modo que el resultado genere el mismo idioma; por lo tanto, las gramáticas regulares correctas extendidas también generan los lenguajes regulares. Análogamente, también lo hacen las gramáticas extendidas de izquierda regular.

Si no se permiten producciones vacías, solo se pueden generar todos los idiomas regulares que no incluyen la cadena vacía.

Mientras que las gramáticas regulares solo pueden describir lenguajes regulares, lo contrario no es cierto: los lenguajes regulares también pueden ser descritos por gramáticas no regulares.

Mezcla de reglas izquierda-regular y derecha-regular

Si se permite la combinación de reglas regulares izquierda y derecha, todavía tenemos una gramática lineal, pero no necesariamente regular. Es más, tal gramática no necesita generar un lenguaje regular: todas las gramáticas lineales pueden adoptar fácilmente esta forma y, por lo tanto, tales 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 comienzo símbolo S y reglas

S → aA

A → Sb

S → ε

genera ${displaystyle {a^{i}b^{i}:igeq.$, el lenguaje lineal paradigmático no regular.