Pourquoi NFA est appelé non déterministe?

14

J'ai cette [sorte de drôle] question à l'esprit. Pourquoi l' automate fini non déterministe est-il appelé non déterministe alors que nous définissons les transitions pour les entrées. Eh bien, même s'il existe des transitions multiples et epsilon , elles sont définies, ce qui signifie que la machine est déterministe pour ces transitions. Ce qui signifie que c'est déterministe.

finite-automata nondeterminism Madhusoodan P
la source

12

Non déterministe tel qu'il est utilisé en informatique théorique est différent du hasard.

adrianN

10

C'est le choix entre les transitions qui n'est pas déterministe.

reinierpost

Qu'est-ce qu'un NFA? (Pour les non éclairés d'entre nous)

DarcyThomas

@DarcyThomas, la première introduction que j'ai eue a été swtch.com/~rsc/regexp/regexp1.html . C'est une bonne lecture - ce n'est pas le but de l'article d'introduire les NFA, mais il le fait bien dans la discussion des expressions régulières.

Wildcard

1

@Trilarion cs.stackexchange.com/questions/5008/…

adrianN

22

"Déterministe" signifie "si vous mettez le système dans la même situation deux fois, il est garanti de faire le même choix à chaque fois".

"Non déterministe" signifie "non déterministe", ou en d'autres termes, "si vous mettez le système dans la même situation deux fois, il pourrait ou non faire le même choix les deux fois".

Un automate fini non déterministe (NFA) peut avoir plusieurs transitions hors d'un état. Cela signifie qu'il existe plusieurs options pour ce qu'il pourrait faire dans cette situation. Il n'est pas obligé de toujours choisir le même; sur une entrée, il peut choisir la première transition, et sur une autre entrée, il peut choisir la même transition.

Ici, vous pouvez considérer la "situation" comme "l'état dans lequel se trouve le NFA, ainsi que le symbole qui est lu ensuite à partir de l'entrée". Même lorsque les deux sont identiques, un NFA peut toujours avoir plusieurs transitions de correspondance qui peuvent être retirées de cet état, et il peut choisir arbitrairement celle à prendre. En revanche, un DFA n'a qu'une seule transition correspondante qui peut être effectuée dans cette situation, il n'a donc pas le choix - il suivra toujours la même transition chaque fois qu'il se trouve dans cette situation.

DW
la source

"il peut choisir arbitrairement lequel prendre." Donc, il a essentiellement une nature probabiliste?

Trilarion

@Trilarion, non, cela dépend si oui ou non cela conduit à accepter l'état. En fait, l'AF probabiliste est une généralisation pour NFA.

rus9384

"Non déterministe" signifie "non déterministe", ou en d'autres termes, "si vous mettez le système dans la même situation deux fois, il pourrait ou non faire le même choix les deux fois". vous entendez par là que la machine peut accepter et rejeter la même chaîne dans deux cas différents.

Madhusoodan P

3

@MadhusoodanP Votre intuition est correcte par rapport à ce qui a été écrit ici, et cela nous amène à ce qui manque dans cette réponse: Lors de l'analyse des NFA, nous considérons toujours tous les chemins d'exécution possibles . Tant que tout chemin dans cette machine mène à un état d'acceptation, nous considérons l'entrée comme acceptée. Il ne s'agit donc pas du tout de probabilité, mais simplement de savoir si un état acceptant peut être atteint ou non. Cette intuition devient plus claire lorsque l'on réfléchit à la façon dont les NFA sont réduits en DFA: nous devons simuler toutes les exécutions possibles du NFA, ce qui conduit à l'explosion exponentielle dans la construction.

ComicSansMS

3

Une façon de le visualiser est de supposer que, lorsque plusieurs transitions peuvent être choisies, le NFA prend toutes les transitions. Vous créez une structure arborescente de tous les états atteints par une chaîne d'entrée, et si l' une des branches se termine sur un état d'acceptation, la chaîne est acceptée. En d'autres termes, avec un DFA, vous demandez " l'état atteint par mon entrée est-il un état d'acceptation?", Tandis qu'avec un NFA, vous demandez "est-ce qu'un état qui pourrait être atteint par mon entrée est un état d'acceptation?".

Harrison Paine

8

Prenez cet automate par exemple, c'est un NFA et il accepte la chaîne . Pour être plus pédant, il accepte les chaînes qui se terminent par . $0110$ $10$

Pour voir que nous avons juste besoin de vérifier s'il atteint un état d'acceptation.

\begin{aligned} q_{0} & \to 1 \\ q_{0} & \to 0 \\ q_{1} & \to 1 \\ q_{2} & \to 0 \end{aligned}

$\begin{align*} q_0 & \rightarrow 1\\ q_0 & \rightarrow 0\\ \color{red}{q_1} &\rightarrow \color{red}{1}\\ q_2 &\rightarrow 0\\ \end{align*}$

Maintenant, dans la ligne rouge, il y avait une autre possibilité, c'est que lors de la lecture du deuxième je pouvais rester dans puis rester dans lors de la lecture du dernier . Les automates n'ont pas de mémoire, il n'y a donc aucun moyen de `` sauvegarder '' un état et de vérifier plus tard si ma chaîne se termine par , c'est comme ce NFA, il fait une supposition si la chaîne se termine par avant de se ramifier dans un état acceptable. Le non-déterminisme ici fait beaucoup de choix et fait toujours les bons. $1$ $q_0$ $q_0$ $0$ $10$ $10$

Il est plus facile de construire un NFA que de construire un DFA, la bonne chose est que les deux sont équivalents .

Aristu
la source

Oui, je connais la partie théorique de NFA. Mais ce que je demandais, c'était même s'il existe plusieurs transitions pour un seul caractère d'entrée, la machine est déterministe quant à tous les états qu'elle peut atteindre (par exemple en créant des threads). C'est donc littéralement DFA. [Ou pensez-vous que

j'interprète

1

L'exemple pourrait être amélioré avec un NFA légèrement plus compliqué, car un DFA dans le même but utiliserait le même nombre d'états que votre NFA et ne serait pas particulièrement compliqué. En revanche, faire correspondre une expression régulière plus compliquée peut nécessiter un DFA compliqué et compliqué, mais être trivial dans un NFA.

supercat

ε

$\varepsilon$

1

@Aristu Si vous implémentez un NFA dans votre langage de programmation préféré, les threads sont un choix terrible . Au lieu de cela, vous devez simplement garder une trace de l'ensemble des états dans lesquels l'automate "pourrait être" après la lecture de chaque caractère d'entrée. Le code résultant sera presque aussi rapide qu'une implémentation de DFA.

David Richerby

1

ϵ

$\epsilon$

5

La fonction de transition d'un NFA spécifie les transitions autorisées à tout moment. Il pourrait y avoir plus d'une option, et la NFA choisit une transition non déterministe dans le but d'atteindre finalement un état acceptant.

Vous devriez peut-être attendre de vous familiariser avec les machines de Turing non déterministes. Le non-déterminisme signifie la même chose dans les deux cas.

Yuval Filmus
la source

pouvez-vous s'il vous plaît souligner que "une transition non déterministe". Et veuillez également revoir ma réponse

Madhusoodan P

Je pense que nos deux réponses ne sont pas super bonnes, bien que votre intuition soit saine.

Yuval Filmus

3

Commencez avec un automate fini. Il a des états et des états d'acceptation et des transitions.

Maintenant, donnez-lui plus d'une règle de transition de chaque état, et dites qu'il accepte s'il existe un ensemble de règles de transition choisies après le fait qui conduisent à l'état d'acceptation étant donné une chaîne d'entrée.

Une fois que vous avez votre chaîne d'entrée, il existe un ensemble fixe de transitions concrètes et indique qu'elle passe par (une à la fois) pour accepter cette chaîne. Mais les transitions qu'il choisit ne sont choisies qu'à la fin de la chaîne . Pendant la lecture de la chaîne, le chemin à suivre n'est pas déterminé.

C'est non déterministe. Il arrive à choisir son chemin dans le graphique après que vous lui ayez donné l'intégralité du problème, pas lorsqu'il lit l'entrée.

Maintenant, nous formalisons cela différemment de cette expérience de pensée, mais cela vous motive pourquoi il a reçu ce nom.

Cela explique comment il a obtenu le nom en premier lieu. Oui, vous pouvez modéliser NDFA de manière complètement déterministe, mais les noms sont collants . Une fois que vous avez appelé quelque chose Bob, il y a un coût de communication à le renommer en quelque chose d'autre car personne ne sait de quoi vous parlez lorsque vous l'appelez Alice.

Yakk
la source

Oui! Je suis d'accord avec votre explication sur NFA. Mais ma question est de savoir pourquoi il est non déterministe même si l'ensemble d'états est défini pour une seule entrée

Madhusoodan P

@MadhusoodanP Il est appelé non déterministe en raison de la façon dont il a été inventé / envisagé. Et les noms sont collants, même après que nous ayons défini des façons multi-déterministes de le modéliser.

Yakk

1

À partir de wikipedia , la meilleure façon d'y penser est de commencer avec les machines à états finis déterministes (DFA). Pour un DFA, chaque transition est uniquement déterminée par l'état actuel et le symbole d'entrée à traiter. Les machines à états finis non déterministes (NFA) sont simplement ce que vous obtenez lorsque vous assouplissez cette règle de déterminisme pour permettre aux transitions de ne pas être définies de manière unique. C'est ce que vous obtenez lorsque vous supprimez la règle déterministe des DFA.

Cort Ammon
la source

C'est un peu plus compliqué, car le non-déterminisme est aussi une condition d'acceptation spécifique.

Yuval Filmus

1

NFA et DFA sont tous deux utilisés pour (entre autres) reconnaître certaines chaînes.

L'automate fini non déterministe fonctionne comme s'il avait une influence sur ses décisions - il peut "choisir" de suivre un chemin, ou non.

Sur l'image ci-dessus, lorsque nous avons affaire à la chaîne "00111", notez que lorsque vous rencontrez le premier "1", il y a deux façons possibles de suivre. On peut rester à "p" ou aller à "q". Si les automates devaient se déplacer vers le "q", il n'accepterait pas la chaîne (car il n'y a pas de bords sortant du "q"). Mais la chaîne peut être acceptée par ces automates en allant au "q" avec seulement le dernier 1, tout en restant à "p" pour tout le reste (et c'est ce qui se passe).

NFA donne l'impression que les automates «savaient» ce qui les attend et choisit en conséquence.

Bien sûr que non. DFA et NFA sont équivalents en termes de puissance (vous pouvez réduire NFA en DFA et rendre DFA (probablement) plus simple avec l'utilisation de NFA), mais NFA est utile, car il permet de définir les mêmes langues que DFA tout en conservant beaucoup les graphiques plus court et plus lisible.

Il n'y a rien d'aléatoire là-dedans. La partie non déterministe met l'accent sur le fait qu'il y a un "choix" à prendre, mais la vérité est que les automates ne prennent aucune décision.

MatthewRock
la source

0

Eh bien voici le mélange de certains contenus du livre [Introduction aux langages formels et aux automates par Peter Linz 4E] et ma compréhension.

Considérez un programme de jeu où la machine doit prendre la décision pour le prochain mouvement [disons pour le tic-tac-toe]. Puisqu'il y a plusieurs coups possibles, nous choisissons chaque coup de manière déterministe et évaluons le coup et optons pour le meilleur. Même si le processus de sélection était déterministe et qu'il y avait beaucoup de coups possibles, le coup final effectué était unique et a été choisi comme meilleur coup tout en cachant tous les calculs de coups essayés à l'adversaire. [Ici, nous supposons que le processus d'évaluation de chaque coup possible a été caché à l'adversaire].

Par conséquent, un seul choix a été fait et l'adversaire se fait une illusion telle que le mouvement n'était pas déterministe.

Eh bien, si vous n'êtes pas encore convaincu en demandant que le meilleur coup était le produit de certains calculs déterministes, alors vous devez considérer la machine qui effectue des mouvements parfaitement aléatoires (peut être une machine perd mais c'est un NFA).

Madhusoodan P
la source

1

Autre façon de dire cela: pour l'adversaire , votre choix était non déterministe. Lors de la modélisation du système du point de vue de l'adversaire, votre coup est un choix non déterministe, à moins que l'adversaire n'ait compris le processus déterministe derrière lui.

reinierpost

@reinierpost exactement ce que je voulais dire

Madhusoodan P

Un exemple plus intéressant pourrait être un jeu de pièces mobiles à information limitée (par exemple, le style "flics et voleurs"). Un joueur déplace un voleur dans un labyrinthe tandis que l'autre joueur déplace des flics. À tout moment où un flic peut voir un voleur, l'état du voleur sera son emplacement, mais à chaque tour où aucun des flics ne voit le voleur, le voleur peut passer à n'importe quel carré adjacent à sa position et que les flics peuvent vois pas à ce moment.

supercat

@supercat Sympa, mais la transition effectuée est toujours un seul état, et si vous masquez le calcul du meilleur coup, cela semble non déterministe

Madhusoodan P

Pourquoi NFA est appelé non déterministe?

Réponses: