Je voudrais savoir comment obtenir les productions pour la langue {0^m 1^m 2^n | n> = 0, m> n}.Quelles sont les productions pour la langue {0^m 1^m 2^n | n> = 0, m> n}
C'est ce que j'avais, mais je ne suis pas sûr que ce soit correct. Veuillez me corriger si je me trompe:
S -> 01A | 0B1A | 00B11A
A -> 2A | 2 | λ
B -> 01
Merci.
Cette langue n'est pas sans contexte. Ceci peut être montré en utilisant le lemme de pompage pour des langages sans contexte. Vous vous retrouvez avec cinq cas; trois des cas pompent seulement l'un des symboles 0, 1 ou 2; et deux cas pompent des symboles adjacents. Notez que vous pouvez presque le faire, sauf que nous pouvons choisir la chaîne 0^(p + 1) 1^(p + 1) 2^p et même lorsque vous étendez 0s et 1s et que vous pompez uniformément, vous échouez toujours au m> n tester lors du pompage.
Il y a des grammaires plus puissantes que sans contexte. Nous pouvons produire une grammaire générale pour cette langue.
S -> RT
R -> 0R1X | 01
X1 -> 1X
XT -> T2 | T
1T -> e
Les deux premières productions produisent des chaînes de la forme 0^n (01) (1X)^n T.
La troisième production produit des chaînes de la forme 0^n (01) 1^n X^n T. Cela permet aux X de "flotter" vers la droite après tous les 1s.
Les deux dernières productions produisent des chaînes de la forme 0^n (01) 1^n 2^m, m < = n. Ceux-ci permettent au T de "flotter" au-delà des X, traduisant chaque X en 2 ou rien.
Ce n'est évidemment pas correct: il ne peut pas produire '00001111' (m = 4, n = 0), mais il peut produire' 0122' (ne respecte pas la contrainte m> n). Le premier problème peut être résolu en rendant B répétable, peut-être 'B -> 01 | 0B1' (notez que ceci rend votre option finale pour S redondant). Je ne peux pas imaginer de moyen de faire respecter m> n sans passer à quelque chose de plus puissant, comme une grammaire contextuelle. – jasonharper