Gramática regular (Modelo de gramáticas regulares)

Requisitos previos: jerarquía de Chomsky

Gramática tipo 3/gramática regular:

La gramática regular genera lenguaje regular. Tienen un solo no terminal en el lado izquierdo y un lado derecho que consta de un solo terminal o un solo terminal seguido de un no terminal.

Las producciones deben estar en la forma:

A ⇢ xB 
A ⇢ x
A ⇢ Bx
where A, B ∈ Variable(V) and x ∈ T*  i.e. string of terminals.

Tipos de gramática regular:

• Gramática lineal izquierda (LLG)
• Gramática lineal derecha (RLG)

1. Gramática lineal izquierda (LLG):
En LLG, las producciones están en la forma si todas las producciones son de la forma 

A ⇢ Bx
A ⇢ x
where A,B ∈ V and x ∈ T*

2. Gramática lineal derecha (RLG):
en RLG, las producciones tienen la forma si todas las producciones tienen la forma

A ⇢ xB
A ⇢ x
where A,B  ∈ V and x ∈ T*

El lenguaje generado por la gramática de tipo 3 es un lenguaje regular, para el cual se puede diseñar un FA. La FA también se puede convertir en gramática de tipo 3

Ejemplo: FA para aceptar strings que comienzan con b

∑  = {a,b}
Initial state(q0) = A
Final state(F)  = B

El RLG correspondiente a FA es 

A ⇢ bB   
B ⇢  ∈/aB/bB 

La gramática anterior es RLG, que se puede escribir directamente a través de FA.

El RLG anterior puede derivar strings que comienzan con b y luego cualquier símbolo de entrada (es decir, se puede aceptar ∑ ={a, b}).

The regular language corresponding to RLG is
 L= {b, ba, bb, baa, bab ,bba,bbb ..... }

Si invertimos la producción anterior del RLG anterior, obtenemos

A ⇢ Bb  
B ⇢  ∈/Ba/Bb 
It derives the language that contains all the strings which end with b.
i.e. L' = {b, bb, ab, aab, bab, abb, bbb .....}

Entonces podemos concluir que si tenemos FA que representa el lenguaje L y si lo convertimos, en RLG, que nuevamente representa el 
lenguaje L, pero después de invertir RLG obtenemos LLG que representa el lenguaje L’ (es decir, el reverso de L). 

Para convertir el RLG en LLG para el idioma L, se debe seguir el siguiente procedimiento: 

Step 1: Reverse the FA for language L
Step 2: Write the RLG for it.
Step 3: Reverse the right linear grammar.
after this we get the grammar that generates the language that represents the LLG for the same language L.

Aquí L es un idioma para FA y L ^R es una inversión del idioma L.
Ejemplo:
El FA anterior representa el idioma L (es decir, un conjunto de todas las strings sobre los símbolos de entrada ayb que comienzan con b).
Lo estamos convirtiendo en LLG.

Paso 1: La inversión de FA es

Paso 2: El RLG correspondiente para este FA invertido es

B ⇢ aB/bB/bA
A ⇢  ∈

Paso 3: Al invertir el RLG anterior obtenemos

B ⇢ Ba/Bb/Ab
A ⇢  ∈

Entonces esto es LLG para el idioma L (que representa todas las strings que comienzan con b).
L = {b, ba, bb, baa, bab, bba, bbb ….. }

Conversión de RLG a FA:

• Empezar desde la primera producción.
• Desde cada alfabeto (o variable) de la izquierda, vaya al símbolo que le sigue.
• Estado de inicio: Será el primer estado de producción.
• Estado final: tome aquellos estados que terminan con terminales sin más no terminales.

Ejemplo: la gramática RLL para Language(L) representa un conjunto de todas las strings que terminan en 0. 

A ⇢ 0A/1B/0B
B ⇢ ∈

Entonces, el FA correspondiente a RLG se puede encontrar como
Comience con la variable A y use su producción.

• Para la producción A ⇢ 0A, esto significa que después de obtener el símbolo de entrada 0, la transición permanecerá en el mismo estado.
• Para la producción, A ⇢ 1B, esto significa que después de obtener el símbolo de entrada 1, la transición de estado tendrá lugar del Estado A al B.
• Para la producción A ⇢ 0B, esto significa que después de obtener el símbolo de entrada 0, la transición de estado tendrá lugar del Estado A al B.
• Para la producción B ⇢ ∈, esto significa que no hay necesidad de transición de estado. Esto significa que sería el estado final en el FA correspondiente ya que RHS es terminal.

Entonces, el NFA final para el RLG correspondiente es

Conversión de LLG a FA:

Explicación: primero convierta el LLG que representa el idioma (L) en RLG, que representa la inversión del idioma L (es decir, L ^R ), luego diseñe FA correspondiente (es decir, FA para el idioma L ^R ). Luego invierta la FA. Entonces el FA final es FA para el idioma L).  

Conversión de LLG a RLG: por ejemplo, se toma la gramática anterior que representa el idioma L (es decir, un conjunto de todas las strings que comienzan con b)
El LLG para esta gramática es

B ⇢ Ba/Bb/Ab
A ⇢  ∈

Paso 1: Convierta el LLG en FA (es decir, el procedimiento de conversión es el mismo que el anterior)

Paso 2: invierta el FA (es decir, el estado inicial se convierte en el estado final y convierte el estado final en el estado inicial e invierte todos los bordes)

Paso 3: Escriba RLG correspondiente a FA invertida.

A ⇢  bB
B ⇢ aB/bB/∈