Wenn eine Grammatik G links und richtig ist, warum $ || l (g) ||\ leq || p || $?

Question

Ich studierte Automatentheorie und formale Sprachen und stieß auf diese Frage:

Wenn eine Grammatik $ g $ links und rechts regelmäßig ist, warum $ || l (g) || \ leq || p || $ ?

Ich habe die Theorie gesucht, aber ich vermisse etwas. Und ich kann die Antwort überall nicht finden, also frage ich hier.

Definitionen:

$ P $ = Regeln für Regeln

Rechtsregulierung: Grammatik $ g= (n, t, p, s) $ , eine Regel ist in $ P $ Wenn sich die Regel im Formular befindet: $ A \ Rightsarrow BA $ $ (A, B \ in n) \ wedge (a \ in t) $

Linke Regelmäßige Regel: Grammatik $ g= (n, t, p, s) $ , eine Regel ist in $ P $ Wenn sich die Regel im Formular befindet: $ A \ Rightarrow AB $ $ (A, B \ in n) \ wedge (a \ in t) $ .

Links-reguläre Grammatik: Eine Grammatik, in der alle Regeln linken reguläre Regeln sind.

Rechtsreguläre Grammatik: Eine Grammatik, in der alle Regeln richtig reguläre Regeln sind.

Beispiel eines Regelsatzes $ P $ mit linkstörpern und rechts regelmäßigen Regeln: $ p={a \ rightarrow a, b \ rightarrow b \} $

und sowohl linkstörpern als auch rechts regelmäßig sind die Grammatik regelmäßig und Typ 3

Answer 1

Ihre Grammatik enthält nur Regeln des Formulars $ A \ bis A $ , für $ a \ in n $ und $ a \ in t $ .Daher $ l (g)={\ Sigma \ in T: s \ to \ sigma \ in p \} $ .Sie nehmen es von hier aus.