Si une grammatie G est partie et droite régulière, pourquoi $ || L (g) ||\ Leq || p || $?

Question

J'étudiais la théorie des automates et les langues formelles et je suis tombé sur cette question:

Si une grammaire $ g $ est laissée et droite régulière, pourquoi $ || L (g) || \ Leq || p || $ ?

J'ai fouillé la théorie mais je manque quelque chose. Et je ne peux pas trouver la réponse n'importe où, alors je demande ici.

Définitions:

$ p $ = ensemble de règles

règle régulière droite: grammaire $ g= (n, t, p, s) $ , une règle est dans $ P $ si la règle est sous la forme: $ a \ rightarrow ba $ $ (A, B \ in n) \ coin (a \ in t) $

règle gauche-régulière: grammaire $ g= (n, t, p, s) $ , une règle est dans $ P $ si la règle est sous la forme: $ a \ rightarrow AB $ $ (A, B \ in n) \ wedge (A \ in t) $ .

grammaire gauche-régulière: une grammaire où toutes les règles sont des règles gauche-régulières.

Grammaire régulière à droite: une grammaire où toutes les règles sont des règles régulières correctes.

Exemple d'un jeu de règles $ P $ avec des règles de gauche-régulière et régulière droite: $ p={A \ RightArrow A, B \ RightARrow b \} $

et être à la fois laissé-régulier et régulier à droite rend la grammaire régulière et de type 3

Answer 1

Votre grammaire ne contient que des règles de la forme $ A \ to a $ , pour $ a \ in n $ et $ a \ in t $ .Par conséquent, $ l (g)={\ sigma \ in t: s \ to \ sigma \ in p \} $ .Vous le prenez d'ici.