Si una gramática G es izquierda y derecha regular, por qué $ || L (g) ||\ leq || p || $?
-
29-09-2020 - |
Pregunta
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
Solución
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í.