Gramáticas regulares lineales derecha e izquierda

La gramática regular es un tipo de gramática que describe un lenguaje regular. Una gramática regular es un objeto matemático, G, que consta de cuatro componentes, G = (N, E , P, S), donde 

• N: conjunto finito no vacío de símbolos no terminales,
• E: un conjunto finito de símbolos terminales, o alfabeto, símbolos,
• P: un conjunto de reglas gramaticales, cada una de las cuales tiene una de las formas
  • A ⇢ aB
  • A⇢a
  • A ⇢∈, Aquí ∈=string vacía, A, B ∈ N, a ∈ ∑
• S ∈ N es el símbolo de inicio.

Esta gramática puede ser de dos formas:

1. Gramática regular lineal derecha
2. Gramática regular lineal izquierda

Gramática regular lineal derecha

En este tipo de gramática regular, todos los no terminales del lado derecho existen en el lugar más a la derecha, es decir; extremos derechos.

Ejemplos:

A ⇢ a, A ⇢ aB, A ⇢ ∈
where,
A and B are non-terminals,
a is terminal, and
∈ is empty string

S ⇢ 00B | 11S
B ⇢ 0B | 1B | 0 | 1
where,
S and B are non-terminals, and
0 and 1 are terminals

Gramática regular lineal izquierda

En este tipo de gramática regular, todos los no terminales en el lado derecho existen en el lugar más a la izquierda, es decir; extremos izquierdos.

Ejemplos:

A ⇢ a, A ⇢ Ba, A ⇢ ∈
where,
A and B are non-terminals,
a is terminal, and
∈ is empty string

S ⇢ B00 | S11
B ⇢ B0 | B1 | 0 | 1
where
S and B are non-terminals, and
0 and 1 are terminals

Gramática regular lineal izquierda a lineal derecha

En este tipo de conversión, tenemos que cambiar todos los no terminales zurdos a la derecha como se muestra en el siguiente ejemplo:

               Left linear                       Right linear 
                      
                 A -> Ba                           A -> abaB     
                 B -> ab                           B -> epsilon   
                                        OR
                                            A -> abB
                                            B -> a
                                                                                                

Entonces, esto se puede hacer para dar múltiples respuestas. El ejemplo explicado anteriormente tiene múltiples respuestas además de la dada una vez.

Gramática lineal derecha a lineal izquierda regular

En este tipo de conversión, tenemos que cambiar todos los no terminales de la mano derecha a la izquierda como se muestra en el ejemplo a continuación:

               Right linear                      Left linear
                     
                 A -> aB                             A -> Baba  
                 B -> ab                             B -> epsilon  
                                                 OR
                                                     A -> Bab
                                                     B -> a

 Entonces, esto se puede hacer para dar múltiples respuestas. El ejemplo explicado anteriormente tiene múltiples respuestas además de la dada una vez.