J'ai eu des difficultés à saisir ce que cela signifie pour une machine de reconnaître et de décider une langue. Je pense que je suis proche des définitions, mais pas de droite.
Quand on dit qu'une machine de Turing Où DFA = DFA = DÉTERINISTIQUE Automaton fini Je crois comprendre qu'il est possible de construire une machine de Turing qui compte tenu de tout type d'entrée (chaînes , voitures, personnes, peu importe!) Sera capable de vous dire si cette chose que vous avez donnée comme entrée est une DFA ou non. Avec cela, je veux dire, acceptera toujours une DFA et rejetera toujours une entrée non-DFA. c'est-à-dire, si cette entrée est membre de D'autre part, un merci t reconnaît la langue l où l . Par exemple, cela disait que Guy X est un reconnaissance de son père, comme tout ce que vous avez mis devant lui, il sera capable de vous dire si ce qui est devant lui est son père ou non. Est-ce correct? Quelle partie n'est pas correcte? Decider sur une langue semble être une machine de Turing qui n'a jamais Loops , c'est-à-dire Il s'arrêtera toujours dans un état d'acceptation ou de rejet pour toute entrée. N'est-ce pas semblable ou de la même chose, comme ce que j'ai expliqué ci-dessus sur les reconnaissants?
4 Réponses :
Je pense que cela signifie pour une machine de Turing pour reconnaître une langue telle que L, c'est que la machine Turing acceptera toute la même entrée que la DFA que L est composé. Ainsi ils sont dans un sens équivalent à cet égard.
Après quelques études, je pense avoir la différence entre les deux.
Pour commencer, un langage distinct Un langage reconnaissable est une langue pour laquelle il existe au moins une machine qui l'a comme langue. Au début, cela peut sembler être une autre de ces définitions circulaires, mais .. en termes pondus, une langue est reconnaissable si vous pouvez penser à une machine qui serait capable d'accepter tout son cordes. élabore une langue vraiment simple: Ce langage est composé que par le mot abc. Cela signifie que pour prouver que cette langue est reconnaissable, il faut construire une machine qui l'accepte. Nous le ferons de manière informelle: m est la machine qui, lorsque cela est donné ABC comme entrée accepte, sinon des boucles infiniment.
Cette machine accepte tous les membres de la langue L, il s'agit donc d'un reconnaissance pour L. Pourtant, pour toutes les autres intrants qu'elle restera à jamais. Une machine existerait-elle que pour chaque entrée accepte / rejete, cette langue pourrait également faire partie de la classe de langues décrides. Pouvez-vous en créer un? (alerte spoiler !!! 11 @ # $! 1) M 'est la machine qui, lorsque cela est donné ABC comme entrée accepte, sinon rejets.
C'est-à-dire, comme il existe une machine qui reconnaît L et que, quelle que soit l'entrée que vous le donnez, vous accepterez toujours la langue est considérée comme déterminable. a outre Vous vous intéressez à une journée de construction d'une machine qui reconnaît L, vous sauriez que vous avez au moins une machine capable de le faire toujours sans engager dans le problème de la possibilité d'accepter ABC mais que vous défailliez les autres cas, suspendu à Pour toujours! un exemple
Cela signifie-t-il qu'un DFA est toujours un décideur (en supposant une entrée finie)? Comme il n'a aucune transition Epsilon, il doit toujours se terminer lorsqu'il a traité toutes les intrants. Un NFA pourrait éventuellement continuer à simuler les transitions Epsilon après que l'entrée s'arrête, donc je pense que cela n'est pas garanti pour NFAS. Est-ce exact? Puisque vous pouvez construire une DFA qui accepte la même langue normale qu'un NFA, cela signifie que toute langue régulière est déterminable?
Étant donné que les DFAS et les NFA ne sont pas TMS, il n'a pas de sens strictement d'appliquer ces termes. Néanmoins, question intéressante @jochemkuijpers. Vous pouvez écrire un algo qui vérifie si une chaîne donnée est dans la langue d'une NFA et qui ne s'arrête jamais sur certaines intrants. Mais vous pouvez aussi écrire un qui arrête toujours, alors la langue {
La réponse simple comme je pense est la suivante:
DÉCIDER s'arrête toujours, accepte ou rejeter
mais
Reconnaître Ne pas toujours arrêter, la machine peut accepter, rejeter ou boucle. Par boucle signifie que la machine ne s'arrête pas.
Pour reconnaître, nous utilisons parfois des décideurs pour décider, si la machine est en boucle, alors le décréteur rejetera en fonction de notre description.
Turing DiCidable signifie qu'il existe une machine de Turing qui accepte toutes les cordes dans la langue et rejette toutes les chaînes non pas dans la langue, notez que cette machine n'est pas autorisée à boucler sur une chaîne pour toujours s'il s'agissait d'un décenteur, il doit s'arrêter à une étape et accepter ou rejeter la chaîne d'entrée.
Turing reconnaissable signifie qu'il y a une machine de Turing qui accepte toutes les cordes dans cette langue. Notez que la machine n'a pas à rejeter les chaînes qui ne sont pas dans la langue, en d'autres termes, cette machine est autorisée à boucle pour toujours sur des cordes qui ne sont pas dans la langue.
Pour le mettre en anglais de haut niveau, une machine de décision doit répondre "oui" ou "non" à la question "est la chaîne x dans la langue a" Un reconnaissance doit répondre à "oui" à la même question si la chaîne est dans la langue, mais si la chaîne n'est pas, il est autorisé à dire "non" ou "pas de commentaire I.e. boucle pour toujours"