Je me rends compte que les automates de refoulement non déterministes peuvent être une amélioration par rapport aux déterministes car ils peuvent "choisir" parmi plusieurs états et il existe des langages sans contexte qui ne peuvent pas être acceptés par un refoulement déterministe.

Pourtant, je ne comprends pas exactement comment ils "choisissent". Pour les palindormes par exemple, chaque source que j'ai trouvée dit simplement que l'automate "devine" le milieu du mot. Qu'est-ce que ça veut dire?

Je peux penser à plusieurs significations possibles:

1. Il entre dans un état au hasard et peut donc ne pas accepter un mot, qui est en fait dans la langue

2. Il va d'une manière ou d'une autre "dans tous les sens", donc si le premier est faux, il teste si l'un des autres peut avoir raison

3. Il y a un mécanisme que je ne connais pas, qui choisit le milieu du mot et n'est donc pas aléatoire, mais l'automate trouve toujours le bon milieu.
   

C'est juste un exemple; ce que je veux savoir, c'est comment cela fonctionne pour tout automate qui a plusieurs états suivants pour un seul et même état avant lui.

Tout simplement, le mécanisme est magique. L'idée du non-déterminisme est qu'il sait simplement quel chemin il doit prendre pour accepter le mot, et il va dans ce sens. S'il y a plusieurs façons, il en va une.

Le non-déterminisme ne peut pas être implémenté en tant que tel dans du matériel réel. Nous le simulons en utilisant des techniques telles que le retour en arrière. Mais c'est avant tout un dispositif théorique, qui peut être utilisé pour simplifier la présentation de certains concepts.

Pour le palindrome, vous pouvez y penser de deux manières. Soit il y a un pouvoir magique qui permet à votre machine de dire "c'est le milieu du mot, il est temps de passer de la poussée à l'éclatement", soit après avoir lu chaque lettre, il est dit "je vais bifurquer un nouveau processus que cette lettre est le milieu du mot, et voir s'il trouve que c'est un palindrome. Ensuite, dans cet autre fil, je continuerai d'essayer, en supposant que ce n'est pas le milieu du mot ".

Une autre façon de penser est le parallélisme infini. Ainsi, un modèle équivalent serait qu'au lieu de choisir un nouveau chemin, il essaie simultanément les deux chemins, en dérivant de nouveaux «processus», réussissant s'il en est dans un état final après avoir lu le mot entier. Encore une fois, cela ne peut pas être construit à l'aide de matériel réel, mais peut être modélisé avec du non-déterminisme.

La chose intéressante à propos du non-déterminisme est que pour les automates finis et les machines de Turing, cela n'augmente pas du tout leur puissance de calcul, juste leur efficacité.

La principale différence (à mon avis) entre un automate déterministe et un automate non déterministe est que pour un automate déterministe un mot d'entrée donné n'a qu'un seul chemin à travers la machine. Dans un automate non déterministe, un mot d'entrée donné peut avoir plusieurs chemins à travers la machine (car il peut y avoir du choix à certains moments).

À la lumière de cela, la condition d'acceptation d'un mot d'entrée doit également être modifiée pour tenir compte du fait qu'un mot peut induire plusieurs chemins à travers la machine. La définition habituelle d'acceptation pour un automate non déterministe est la suivante: Pour qu'un mot soit accepté par l'automate, il doit y avoir au moins un chemin d'acceptation induit par ce mot.

Cela conduit alors à l'idée d'un automate «devinant», si un mot est accepté par un automate non déterministe, alors nous avons tendance à penser que l'automate fait automatiquement les bons choix afin que (l'un des) chemin (s) d'acceptation (s) est suivi lorsque ce mot est présenté en entrée.

Ce que cela signifie pour les palindromes, c'est que le pda aura essentiellement deux modes: un mode push où il pousse les lettres actuelles sur la pile et un mode popping où il supprime ces lettres et les compare à l'entrée. Cette machine aura une transition vide de l'état de poussée à l'état d'éclatement qu'elle pourra suivre à tout moment dans le mot. Cependant, la machine ne videra sa pile et ne passera à l'état d'acceptation que si elle a lu un palindrome et suivi la transition vide au milieu du palindrome. Puisque nous n'avons besoin que de l'existence d'un chemin acceptant, nous pouvons dire que l'automate "devine" où se trouve le milieu du mot.

L'idée de non-déterminisme est assez simple: l'automate peut avoir plusieurs étapes suivantes dans certaines situations. L'automate accepte s'il y a une séquence d'étapes (il peut y en avoir plusieurs!) Menant de la configuration initiale à une acceptation, il rejette uniquement s'il n'y a pas une telle séquence.

Cela signifie qu'il "décide" de la prochaine étape à suivre dans ces situations ambiguës. Une façon d'en parler est de dire qu'il sélectionne toujours comme par magie la «bonne» prochaine étape (ou une, s'il y a plusieurs «bonnes» étapes). Une autre façon de voir les choses est que dans de telles situations, le calcul de l'automate se divise en plusieurs copies, chacune poursuivant un chemin.

Dans la pratique, cela peut être implémenté par un retour en arrière, en plaçant une certaine forme de balise aux endroits où la décision a été prise, et revenir en arrière et essayer l'alternative suivante si le chemin actuel ne fonctionne pas. Ceci est généralement géré par récursivité. Ou en complétant les informations que l'automate possède "légalement" avec des informations supplémentaires (c'est ce que vous faites lorsque vous montrez comment fonctionne un automate non déterministe sur le tableau noir, en regardant en avant et en déterminant laquelle des étapes mène au succès).

"Deviner" est directement lié à notre interprétation existentielle du non-déterminisme

En bref: Cette idée qu'un automate non déterministe peut deviner (ou être aidé par un oracle) est directement liée à notre interprétation existentielle du non-déterminisme. Une autre interprétation est possible (peut-être d'autres) où «deviner» n'aurait pas de sens.

Le non déterminisme est étrange. Nous avons une façon de l'interpréter dans la théorie des automates, mais il n'est pas a priori évident de savoir comment procéder.

Cela peut sembler surprenant, mais le non-déterminisme est une situation très courante. Quand on doit prouver un théorème, étant donné les axiomes de certaines théories mathématiques, le processus est naturellement non déterministe. C'est pourquoi nous ne savons souvent pas quoi faire pour résoudre un problème, par exemple pour trouver les solutions d'une équation du troisième degré, ou prouver un théorème.

Il existe de nombreuses façons de combiner ce qui est déjà connu avec des règles d'inférence pour obtenir de nouveaux résultats. Et la situation est généralement la même si nous essayons de reconstruire une preuve à l'envers à partir du résultat.

Lorsque nous tentons de résoudre un tel problème, nous essayons de « deviner » un chemin dans un système de transition.

En fait, nous ne devinons pas, mais construisons dans notre esprit une structure qui organise et / ou simplifie le labyrinthe des possibilités afin que nous puissions voir notre chemin à travers lui. Dans certains cas, la question suit un modèle identifié pour lequel nous avons un moyen standard (parfois? Habituellement? Toujours?) De trouver une solution, et nous appelons cela un algorithme.

Une technique (généralement coûteuse) que nous pouvons utiliser consiste simplement à explorer complètement le labyrinthe: suivre tous les chemins, en le faisant d'abord pour éviter d'être pris dans un sous-graphique infini. C'est à peu près ce qui se fait en alignant tous les calculs possibles d'un automate non déterministe. Ce calcul dérivé en queue d'aronde est lui-même déterministe.

$DC$$A$$A$$A$

En fait, il pourrait y avoir différentes façons d'interpréter un calcul non déterministe . Afaik, ils sont tous cohérents, mais pas les uns avec les autres.

$R$$w$

L'idée de deviner pour le module de reconnaissance n'est qu'une image tirée de notre propre façon de "deviner" comment trouver cet arbre de preuve. Mais la grande différence est que nos cerveaux ne sont pas des PDA. Ce sont des appareils beaucoup plus complexes avec la capacité d'explorer et de cartographier approximativement les structures de transition afin que nous puissions trouver notre chemin à travers elles, que nous percevons parfois comme des suppositions.

Cette interprétation du calcul non déterministe est ce que j'appellerais l'acceptation existentielle , en référence au fait qu'elle ne nécessite que l'existence d'un seul calcul acceptant. Cela correspond à un arrêt existentiel que j'ai introduit dans une autre réponse .

Cependant, on pourrait également interpréter le non-déterminisme de manière universelle comme: un reconnaisseur est censé accepter (universellement) une entrée "w" si tous les calculs possibles arrêtent et acceptent l'entrée. Cette acceptation universelle correspond au concept d'arrêt universel introduit dans la même réponse.

L'acceptation universelle et l'arrêt universel semblent conduire à une compréhension cohérente du non-déterminisme. On pourrait donc faire un travail théorique avec cette définition. Mais cela n'est pas conforme à notre pratique habituelle dans de nombreuses situations non déterministes comme le prouve un théorème, ou dans la situation de la vie quotidienne. Lorsque nous sommes confrontés à un problème, nous ne voulons qu'une seule façon de le résoudre, et nous nous moquons ensuite de savoir si d'autres méthodes sont efficaces ou non (enfin, c'est un peu trop simplifié).

Si nous devons reconnaître un palindrome, nous pouvons le deviner en mesurant la longueur et en recherchant le milieu. Le PDA ne peut pas. Mais, comme nous ne sommes intéressés que par l'existence d'une seule solution, nous pouvons toujours prétendre qu'elle peut ... si cela peut l'aider. Ou nous pouvons considérer qu'il a des oracles fournis par des machines plus intelligentes (nous?) Pour l'aider. Ou vous pouvez même l'appeler magique, et le penser (après tout, le quantificateur existentiel est une sorte de baguette magique). Si cela peut aider, ce sera le cas. S'il n'y a pas de calcul acceptant, aucune aide ne sera d'aucune utilité.

Notez que cette idée de deviner n'aurait aucun sens dans l'interprétation de l'acceptation universelle.