Gramática regular

Se dice que una Gramática ($V_N, V_T$, P, S) es regular (GR), o regular a la derecha, si toda regla en P tiene la forma A → aB o A → a con A, B ∈ $V_N$ y a ∈ $V_T$.

Intuitivo: Una gramática regular a la derecha es aquella en la que las transformaciones ocurren añadiendo cosas hacia la derecha.

La siguiente gramática es regular, G = ({S, B}, {a, b}, P, S): 

 S → aS
 S → aB
 B → bB
 B → b

Transformación de GR en autómatas

Existe un algoritmo para pasar automáticamente de gramática regular a Autómatas finitos (generalmente no determinista). Los pasos son los siguientes:

  1. Para cada símbolo no terminal A de la gramática se crea un estado A del autómata finito.

  2. El estado inicial del autómata será el correspondiente al símbolo inicial de la gramática.

  3. Para cada regla de la forma A → aB, se crea una transición entre los estados correspondientes a los símbolos A y B etiquetada con a:

    A ----a----> B
  1. Para una regla de la forma A → B se crea una transición-ε entre los estados correspondientes a los símbolos A y B:
    A ----ε----> B

  1. Las reglas de la forma A → ε significan que el estado A es un estado terminal (o de aceptación).

  2. Por último, para las reglas A → a, creamos nuevos estados terminales (de aceptación) F, y transiciones a así:

    A ----a----> F

[!note] Observación Realmente, las gramáticas de la forma anterior no cuadran exactamente con la definición que hicimos de una gramática regular; no obstante, es muy sencillo transformar una gramática de la forma anterior en otra gramática equivalente que cumpla con la definición de una gramática regular (podemos decir que se trata de gramáticas regulares "disfrazadas").

3.2. TRANSFORMACIÓN DE AUTÓMATAS FINITOS EN GRAMÁTICAS REGULARES

El proceso anterior se invierte si consideramos que una transición del tipo:

    A ----a----> B

corresponde a una producción del tipo A → aB.

Toda transición se convierte en una nueva regla para la gramática que se está construyendo. Se termina añadiendo a la gramática producciones ε para todos los estados de aceptación.

[!example] Ejemplo 7 Dado el autómata que acepta la expresión regular ab + bbaa*, se va a construir una gramática que genere dicho lenguaje.

La gramática correspondiente se obtendría partiendo del símbolo inicial. Dado que con el terminal a se pasa al estado A, creamos la regla S₀ → aA. De la misma manera, se tiene S₀ → bB. El estado A incluye un bucle etiquetado b que equivale a la regla A → bA. Como A es un estado de aceptación, debemos crear también A → ε.

Continuando así, la gramática resultante sería: 

S₀ → aA|bB
A → bA|ε
B → bB|aC
C → aC|ε