Quelqu'un peut-il aider à comprendre que L = {a m b n, m ≥ n + 2, m ≤ 3} est régulière ou non en utilisant le lemme de pompage, il semble être un peu difficile à prouver.Preuve que la langue est régulière ou pas régulière en utilisant le lemme de pompage?
J'ai essayé d'utiliser le lemme de pompage et cela montre que c'est un langage régulier mais je suis vraiment confus que ce soit vrai ou pas.
J'ai essayé de utilisé lemme de pompage et il montre qu'il est langue régulière mais je suis vraiment confus qui est ou non ce droit.
Notons d'abord, le lemme de pompage peut être utilisé à la preuve que « la langue est certaine pas une langue régulière ». Mais nous ne pouvons pas utiliser le lemme de pompage pour prouver que "certain langage est un régulier".
Oui, le lemme de pompage pour les langages réguliers décrit une propriété essentielle de toutes les langues régulières, et si une langue ne satisfait pas le conditions described by pumping lemma ou ne répond pas à la propriété lemma de pompage alors cette langue n'est pas une langue régulière, Mais l'inverse de ce n'est pas vrai !! & mdash- il y a des « langues satisfait les conditions de pompage des lemme de et peut-être encore non -Regular », signifie: -
lemme de pompage est 'necessary but not sufficient condition' pour une langue à régulière.
C'est quelque chose comme: chaque ingénieur est étudiant en mathématiques - donc si un étudiant est ingénieur, on peut dire qu'il connaît les mathématiques, mais leur sont des étudiants en mathématiques ne connaissent pas ces techniques. (juste en vous donnant un exemple à expliquer)
De votre question, j'ai l'impression que vous ne comprenez pas fondamentalement - "what is a regular language?". Contrairement au lemme de pompage pour les langues normales, nous devons apprendre d'autres caractéristiques des langues régulières - les trouver dans une langue preuves que la langue est une langue régulière. Si vous pouvez représenter une langue en utilisant des automates finis ou/et une expression régulière qui prouve que la langue est une langue régulière.
Maintenant, venez à votre question initiale:
Comment prouver que la langue {a m b n, m ≥ n + 2, m ≤ 3} est régulière ou non?
Parce que ni « m » ou « n » peut être négatif (une chaîne sans apparition d'un symbole est possible, par exemple. Chaîne vide , mais une chaîne avec occurrence négative des symboles de langue n'est pas possible) et selon la condition "m ≥ n + 2", 'm' est toujours supérieur à 'n' — donc la valeur minimale de 'm' (quand 'n' vaut 0) est 2.De la deuxième condition "m ≤ 3", la valeur maximale de 'm' est '3', et donc 'm' peut être 2 ou 3.
Si vous remarquez de nouveau la condition de poing: "m ≥ n + 2" pour m = {2, 3} les valeurs possibles pour 'n' peuvent être:
Ainsi, il est venu que le langage est un langage fini e. seulement se compose de trois chaînes. Chaque langage fini est une langue régulière, vérifier diagramme de Venn:
(appentis plus sur cette lecture: Finiteness of Regular Language)
Expression régulière pour votre langue L = {a m b n, m ≥ n + 2, m ≤ 3} serait aa (a + & Lambda;) (b + & Lambda;), d'où il est prouvé que le langage est un langage régulier. Une chaîne sans occurrence de n'importe quel symbole est appelée chaîne vide ou nulle dans les langages formels, dans la plupart des livres de langage formel symbole Ɛ pour chaîne vide.
& Lambda; est le symbole vide.
nous ne pouvons pas utiliser le lemme de pompage pour prouver la langue est regular.To prouver une langue est régulière, nous devrions concevoir DFA pour cette langue
Ce n'est pas une programmation, mais une question théorique. Aussi: Vous ne fournissez pas d'informations sur ce que vous avez déjà essayé. Veuillez lire la page d'aide de Stack Overflow sur "comment écrire une bonne question". –
@Marcus Müller j'ai suppléé plus d'informations est-ce bien? –
Postez cela sur le site d'informatique à la place. – EvilTeach