DEFINICIÓN

Como toda gramática está formada por la cuadrupla (V,T,P,S); diremos que es una gramática regular si sus reglas de producción P son de la siguiente forma:

                A→ uB o A→ u

En este caso se llama Gramática Regular Lineal por la derecha, ya que el símbolo no terminal del consecuente (parte derecha de la flecha) es el más a la derecha de los símbolos.

O bien: A Bu o A u se llama Gramática Regular Lineal por la izquierda porque el símbolo más a la izquierda del consecuente es el símbolo no terminal.

 

EJEMPLOS DE GRAMÁTICAS REGULARES:

S→0A

A→ 10A

A→ε

Esta gramática es lineal por la derecha y genera el lenguaje 0(10)*     2.- V={S,A}, T={0,1}, las producciones son S→10

S→0
 

Es una gramática lineal por la izquierda. Genera el lenguaje (10)*
 
 

 
 
 

EQUIVALENCIA ENTRE GRAMÁTICA REGULAR Y AFD.

Si L es un lenguaje generado por una gramática regular , entonces existe un autómata determinístico que lo reconoce. Por tanto, existe equivalencia ente la gramática regular y el autómata finito determinístico.
 

ALGORITMO que muestra la relación entre una Gramática Regular por la Derecha y el AFND con TN.
 

Sea L un lenguaje generado por la gramática G=(V,T,P,S) que es lineal por la derecha. Vamos a construir un AFND con TN que acepta el lenguaje L. Este autómata será M=(Q,T,d, q0, F) donde:  
1.- Q={[α] / (α=S)∨(∃A∈V, u∈T* ; tales que A→uα ∈ P)}

       q0=[S]

       F={[ε]}

2.- Las transiciones d vienen definidas por :

si A es una variable d([A],ε )={[α ] /Aαes una producción de P}   si a∈T y α ∈T*V entonces d([aα] a)={[α ]} EJEMPLO Siguiendo el algoritmo anterior y dada la gramática lineal por la derecha mediante las siguientes producciones: S→0A, A→10A,A→ ε . Obtener el AFND con TN.

 
 
 

ALGORITMO PARA OBTENER EL AFND CON TN DESDE UNA GRAMÁTICA LINEAL POR LA IZQUIERDA.