Si une grammatie G est partie et droite régulière, pourquoi $ || L (g) ||\ Leq || p || $?
-
29-09-2020 - |
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
La solution
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.