Quel est le Lemme de Pompage en termes simples?

le lemme de pompage est une preuve simple pour montrer qu'un langage n'est pas régulier, ce qui signifie qu'une Machine à état fini ne peut pas être construite pour lui. L'exemple canonique est la langue (a^n)(b^n) . C'est le langage simple qui est juste n'importe quel nombre de a s, suivi par le même nombre de b . Afin que les chaînes

ab
aabb
aaabbb
aaaabbbb

etc. sont dans la langue, mais

aab
bab
aaabbbbbb

etc. ne le sont pas.

il est assez simple de construire un FSM pour ces exemples:

celui-ci fonctionnera jusqu'à n=4. Le problème est que notre langue n'a pas mis de contrainte sur n, et Machines D'État finis doivent être, bien, finis. Peu importe le nombre d'états que j'ajoute à cette machine, quelqu'un peut me donner une entrée où n égale le nombre d'États plus un et ma machine échouera. Donc, si il peut y avoir une machine construite pour lire cette langue, il doit y avoir une boucle quelque part pour garder le nombre d'états finis. Avec ces boucles ajoutées:

toutes les ficelles de notre langue seront acceptées, mais il y a un problème. Après les quatre premiers a s, la machine perd le compte de combien de a ont été d'entrée, parce qu'il reste dans le même état. Cela signifie que qu'après quatre, je peux ajouter autant de a s que je veux à la chaîne, sans ajouter de b s, et obtenir toujours la même valeur de retour. Cela signifie que les cordes:

aaaa(a*)bbbb

avec (a*) représentant un nombre quelconque de a s, seront tous acceptés par la machine même s'ils ne sont évidemment pas tous dans la langue. Dans ce contexte, nous dirions que la partie de la chaîne (a*) peut être pompée. Le fait que l'État Fini Machine est finie et n n'est pas limité, garantit que toute machine qui accepte toutes les chaînes dans la langue doit avoir cette propriété. La machine doit faire une boucle à un moment donné, et au moment où elle fait une boucle, le langage peut être pompé. Par conséquent, aucune Machine D'état fini ne peut être construite pour cette langue, et la langue n'est pas régulière.

se rappeler que les Expressions régulières et les Machines à états finis sont équivalentes , puis remplacer a et b avec ouverture et fermeture de balises Html qui peuvent être imbriquées les unes dans les autres, et vous pouvez voir pourquoi il n'est pas possible d'utiliser des expressions régulières pour analyser Html

C'est un dispositif destiné à prouver qu'une langue donnée ne peut pas être d'une certaine classe.

considérons le langage des parenthèses équilibrées (signifiant les symboles '(' et ')', et incluant toutes les chaînes qui sont équilibrées dans le sens habituel, et aucune qui ne le sont pas). On peut utiliser le lemme de pompage pour montrer que ce n'est pas régulière.

(une langue est un ensemble de chaînes possibles. Un analyseur est une sorte de mécanisme que nous pouvons utiliser pour voir si une chaîne est dans l' la langue, donc il doit être capable de faire la différence entre une chaîne dans la langue ou une chaîne en dehors de la langue. Un langage est "régulier" (ou "sans contexte" ou "sensible au contexte" ou autre) s'il existe un analyseur régulier (ou autre) qui peut le reconnaître, en faisant la distinction entre les chaînes dans le langage et les chaînes non dans le langage.)

LFSR Consulting a fourni une bonne description. Nous pouvons dessiner un analyseur pour une langue régulière comme une collection finie de les cases et les flèches, avec les flèches représentant les caractères et les cases les reliant (agissant comme des"États"). (Si c'est plus compliqué que ça, ce n'est pas une langue normale. Si nous pouvons obtenir une chaîne plus longue que le nombre de boîtes, cela signifie que nous avons traversé une boîte plus d'une fois. Cela signifie que nous avons eu une boucle, et nous pouvons passer à travers la boucle autant de fois que nous voulons.

donc, pour une langue normale, si nous pouvons créer une chaîne arbitrairement longue, nous pouvons la diviser en xyz, où x est les caractères que nous devons obtenir au début de la boucle, y est la boucle réelle, et z est ce que nous avons besoin pour rendre la chaîne valide après la boucle. L'important est que les longueurs totales de x et y sont limitées. Après tout, si la longueur est supérieure au nombre de boîtes, nous avons évidemment passé par une autre boîte en faisant cela, et il ya donc une boucle.

ainsi, dans notre langage équilibré, nous pouvons commencer par écrire n'importe quel nombre de parenthèses de gauche. Dans en particulier, pour un analyseur donné, nous pouvons écrire plus de parens gauches qu'il n'y a de boîtes, et donc l'analyseur ne peut pas dire combien il y a de parens gauches. Par conséquent, x est une certaine quantité de parens gauche, et cela est fixé. y est aussi un certain nombre de parens gauche, et cela peut augmenter indéfiniment. On peut dire que z est un certain nombre de bons parents.

cela signifie que nous pouvons avoir une chaîne de 43 parens gauches et 43 parens droits reconnus par notre analyseur, mais l'analyseur ne peut pas dire que d'une chaîne de 44 parens de gauche et 43 parens de droite, qui n'est pas dans notre langue, donc l'analyseur ne peut pas Parser notre langue.

comme n'importe quel analyseur régulier possible a un nombre fixe de boîtes, nous pouvons toujours écrire plus de parens gauche que cela, et par le lemme de pompage nous pouvons alors ajouter plus de parens gauche d'une manière que l'analyseur ne peut pas dire. Par conséquent, le langage de la parenthèse équilibrée ne peut pas être analysé par un analyseur régulier, et n'est donc pas une expression régulière.

c'est une chose difficile à obtenir en termes profanes, mais fondamentalement les expressions régulières devraient avoir un substrat non vide qui peut être répété autant de fois que vous le souhaitez tandis que le nouveau mot entier reste valide pour la langue.

Dans pratique , le pompage de lemmes ne sont pas suffisantes pour PROUVER une langue correcte, mais plutôt comme un moyen de faire une preuve par contradiction et de montrer une langue ne rentre pas dans la classe de langues (Régulier ou Sans contexte) en montrant le lemme de pompage ne fonctionne pas pour lui.

fondamentalement, vous avez une définition d'une langue (comme XML), qui est une façon de dire si une chaîne donnée de caractères (un" mot") est un membre de cette langue ou non.



Le lemme de pompage établit une méthode par laquelle vous pouvez choisir un "mot" de la langue, et ensuite appliquer certaines modifications. Le théorème déclare que si la langue est régulière, ces changements devraient produire un "mot" qui est encore de la même langue. Si le mot que vous trouver n'est pas dans la langue, alors la langue n'aurait pas pu être régulière en premier lieu.

le lemme de pompage simple est celui pour les langues régulières, qui sont les ensembles de cordes décrites par automata finis, entre autres choses. La caractéristique principale d'une automatisation finie est qu'elle n'a qu'une quantité finie de mémoire, décrite par ses États.

supposons maintenant que vous avez une chaîne, qui est reconnue par un automate fini, et qui est assez longue pour "dépasser" la mémoire de l'automatisation, c.-à-d. dans laquelle les États doivent répéter. Ensuite, il ya un sous-chaîne où l'état de l'automate au début de la sous-chaîne est la même que l'état à la fin de la sous-chaîne. Puisque la lecture de la sous-couche ne change pas l'état, elle peut être supprimée ou dupliquée un nombre arbitraire de fois, sans que l'automate soit plus sage. Ces chaînes modifiées doivent donc aussi être acceptées.

il y a aussi un lemme de pompage un peu plus compliqué pour les langues sans contexte, où vous pouvez supprimer / insérer ce qui peut être intuitivement considéré comme des parenthèses à deux endroits dans la chaîne.

par définition, les langues régulières sont celles reconnues par un automate d'état fini. Pensez - y comme un labyrinthe : les États sont des pièces, les transitions sont des couloirs à Sens Unique entre les pièces, il y a une pièce initiale, et une salle de sortie (finale). Comme le dit le nom "finite state automaton", il y a un nombre fini de pièces. Chaque fois que vous voyagez le long d'un couloir, vous prenez la lettre écrite sur son mur. Un mot peut être reconnu si vous pouvez trouver un chemin de l'initiale à la salle finale, allant par des couloirs Marqués de ses lettres, dans le bon ordre.

le lemme de pompage dit qu'il y a une longueur maximale (La longueur de pompage) pour laquelle vous pouvez vous promener à travers le labyrinthe sans jamais retourner à une pièce par laquelle vous êtes allé auparavant. L'idée est que depuis il ya seulement tellement de chambres distinctes, vous pouvez marcher dans, passé un certain point, vous devez quitter le labyrinthe ou la croix sur vos pistes. Si tu arrives à marcher un chemin plus long que ce longueur de pompage dans le labyrinthe, puis vous faites un détour : vous insérez un(au moins un) cycle dans votre chemin qui pourrait être enlevé (si vous voulez que votre traversée du labyrinthe reconnaisse un mot plus petit) ou répété (pompé) indéfiniment (permettant de reconnaître un mot super-long).

il existe un lemme similaire pour les langues sans contexte. Ces langages peuvent être représentés en tant que mot accepté par les automates pushdown, qui sont des automates d'état finis qui peuvent faire usage d'un pile pour décider quelles transitions effectuer. Néanmoins, puisqu'il y a stilla nombre fini d'États, l'intuition expliquée ci-dessus porte, même à travers l'expression formelle de la propriété peut être légèrement plus complexe .

en termes simples, je pense que vous avez presque raison. C'est une technique de preuve (deux en fait) pour prouver qu'une langue est et non dans une certaine classe.

Fer exemple, considérons un langage régulier (regexp, automates, etc) avec un nombre infini de chaînes. À un certain point, comme starblue dit, vous manquez de mémoire, car la chaîne est trop longue pour l'automate. Cela signifie qu'il doit y avoir un morceau de la corde que le automate ne peut pas dire combien d'exemplaires de ce que vous avez (vous êtes dans une boucle). Donc, n'importe quel nombre de copies de ce substrat au milieu de la chaîne, et vous êtes toujours dans la langue.

cela signifie que si vous avez une langue qui n'a pas cette propriété, c'est-à-dire qu'il y a une chaîne de caractères suffisamment longue avec Non substrat que vous pouvez répéter n'importe quel nombre de fois et être toujours dans la langue, alors la langue n'est pas régulière.

, Par exemple, de profiter de cette langue L = un ⁿ b ⁿ .

Maintenant, essayez de visualiser automate fini pour la langue ci-dessus, pour certains n .

si n = 1, la chaîne w = ab . Ici, nous pouvons faire un automate fini avec boucle si n = 2, la chaîne w = ² b ² . Ici, nous pouvons faire un automate fini avec la boucle

si n = p , la chaîne w = un ^p b ^p . Essentiellement un automate fini peut être supposé avec 3 étapes. Première étape, il faut une série d'entrées et entrer deuxième étape. De même, de l'étape 2 à l'étape 3. Appelons ces étapes comme x , y et z .

Il y a quelques observations

1. Certainement x contient " a " et z contiennent "b".
2. maintenant nous devons être clairs sur y :
   • cas un : y peut contenir " a " seulement
   • cas b : y peut contenir " b " seulement
   • cas c : y peut contenir une combinaison de 'a' et 'b'

ainsi les états finis d'automate pour l'étape y devraient être en mesure de prendre des entrées" a " et "b" et aussi il ne devrait pas prendre plus de a et b qui ne peuvent pas être comptés.

1. si l'étape y ne prend qu'un " a "et un "b", alors il y a deux états requis
2. S'il prend deux 'a' et un 'b', trois états sont nécessaires avec des boucles externes et ainsi de suite....

ainsi la conception de l'étape y est purement infinie. Nous pouvons seulement le rendre fini en mettant quelques boucles et si nous mettons des boucles, l'automate fini peut accepter les langues au-delà de L = a ⁿ b ⁿ . Donc pour ce langage, nous ne pouvons pas construire un automate fini. Il n'est donc pas régulier.

Ce n'est pas une explication, mais il est simple. Pour a^n B^n Notre FSM doit être construit de telle manière que b doit savoir le nombre de a déjà parsé et acceptera le même n nombre de B. Un FSM ne peut pas simplement faire des choses comme ça.