TeoLeng: Consulta de gramatica regular

Hola! A la hora de ver si una gramatica es regular me gustaria saber si una regla que tiene una sola variables (ej: S -> B) puede formar parte de una gramatica regular ya sea derecha o izquierda, si tomamos como que la variable (B) esta acompañada de un epsilon en cualquiera de sus lados ya que epsilon forma parte de los terminales no?

Re: Consulta de gramatica regular

de Santiago Gongora - jueves, 19 de mayo de 2022, 21:27

Buenas noches Dylan :)

Si entiendo bien, estás consultando si la producción:

$A \longrightarrow B$

puede ser parte de una gramática regular. La respuesta es que sí.

Siempre intento transmitir que una gramática regular puede verse como si fuera una gramática libre de contexto con dos fuertes restricciones:

Todas las reglas cumplen que las variables aparecen del mismo lado. Si todas aparecen a la derecha, la gramática es lineal derecha. Si todas aparecen a la izquierda, la gramática es lineal izquierda.
En las lineales derechas, todas las producciones siguen la forma $A \longrightarrow wB$ o $A \longrightarrow w$ , donde "B" es una variable y $w \in T^*$ . Análogamente todas las reglas de las lineales izquierdas tienen la forma $A \longrightarrow Bw$ o $A \longrightarrow w$ .