Obras literarias

Gramática regular
En informática una gramática regular es una gramática formal (N, Σ, P, S) que puede ser clasificada como regular izquierda o regular derecha. Lasgramáticas regulares sólo pueden generar a los lenguajes regulares de manera similar a los autómatas finitos y las expresiones regulares.
Dos gramáticas regulares que generan elmismo lenguaje regular se denominan equivalentes. Toda gramática regular es una gramática libre de contexto.
Una gramática regular derecha es aquella cuyas reglas de producciónP son de la siguiente forma:
1. A → a, donde A es un símbolo no-terminal en N y a uno terminal en Σ
2. A → aB, donde A y B pertenecen a N y a pertenece a Σ
3. A →ε, donde A pertenece a N.
Análogamente, en una gramática regular izquierda, las reglas son de la siguiente forma:
1. A → a, donde A es un símbolo no-terminal en N y auno terminal en Σ
2. A → Ba, donde A y B pertenecen a N y a pertenece a Σ
3. A → ε, donde A pertenece a N.

Una definición equivalente evita la regla 1 (A → a) yaque es sustituible por:
A → aL
L → ε
en el caso de las gramáticas regulares derechas y por:
A → La
L → ε
en el caso de las izquierdas.
Algunosautores alternativamente no permiten el uso de la regla 3 suponiendo que la cadena vacía no pertenece al lenguaje.
Un ejemplo de una gramática regular G con N = {S, A}, Σ ={a, b, c}, P se define mediante las siguientes reglas:
S → aS
S → bA
A → ε
A → cA
donde S es el símbolo inicial. Esta gramática describe el mismolenguaje expresado mediante la expresión regular a*bc*.
Dada una gramática regular izquierda es posible convertirla, mediante un algoritmo en una derecha y viceversa.