Si una gramática G es izquierda y derecha regular, por qué $ || L (g) ||\ leq || p || $?

Question

Estaba estudiando la teoría de autómatas y las lenguas formales y se encontró con esta pregunta:

Si una gramática $ G $ es de izquierda y derecha regular, por qué $ || l (g) || \ leq || p || $ ?

He buscado en la teoría, pero me estoy perdiendo algo. Y no puedo encontrar la respuesta en ninguna parte, así que estoy preguntando aquí.

Definiciones:

$ P $ = conjunto de reglas

Regla regular derecha: gramática $ g= (n, t, p, s) $ , una regla está en $ P $ Si la regla está en el formulario: $ A \ RightArow BA $ $ (a, B \ in n) \ wedge (A \ in t) $

Regla de izquierda-regular: Gramática $ g= (n, t, p, s) $ , una regla está en $ P $ Si la regla está en el formulario: $ A \ RightArow Ab $ $ (a, B \ in n) \ wedge (A \ in t) $ .

Gramática regular izquierda: una gramática donde todas las reglas son las reglas de izquierda-regulares.

Gramática normal-regular: una gramática donde todas las reglas son reglas correctas regulares.

Ejemplo de un conjunto de reglas $ P $ con reglas de izquierda-regular y derecha: $ P={A \ Rudowarrow A, B \ Rudowarrow B \} $

y ser ambos a la izquierda, regularmente, regularmente, hace que la gramática regular y el tipo 3

Answer 1

Su gramática solo contiene reglas del formulario $ A \ a $ , para $ a \ in n $ y $ a \ in t $ .Por lo tanto, $ L (g)={\ SIGMA \ IN T: S \ a \ SIGMA \ IN P \} $ .Lo tomas de aquí.