Questions sur les automates, les grammaires formelles ou d'autres modèles de calcul qui se rapportent spécifiquement à l'utilisation du non-déterminisme. À ne pas confondre avec le hasard ou l'ambiguïté!
Je passais par la discussion sur la question Comment définir les machines de Turing quantiques? et je sens que TM quantique et TM non déterministe sont une seule et même chose. Les réponses à l'autre question ne touchent pas à cela. Ces deux modèles sont-ils identiques? Sinon, Quelles sont les...
Quelles sont les différences et les relations entre les algorithmes randomisés et les algorithmes non déterministes? De Wikipédia Un algorithme randomisé est un algorithme qui utilise un degré d'aléatoire dans le cadre de sa logique. L'algorithme utilise généralement des bits uniformément...
Nous savons que les DFA sont équivalents aux NFA en termes de pouvoir d'expressivité; il existe également un algorithme connu pour convertir les NFA en DFA (malheureusement je connais maintenant l'inventeur de cet algorithme), qui dans le pire des cas nous donne états, si notre NFA avait états....
Un automate est un modèle abstrait d'un ordinateur numérique. Les ordinateurs numériques sont complètement déterministes; leur état à tout moment est uniquement prévisible à partir de l'entrée et de l'état initial. Lorsque nous essayons de modéliser des systèmes réels, pourquoi inclure le...
Tous les automates finis non déterministes peuvent être transformés en automates finis déterministes équivalents. Cependant, un automate fini déterministe ne permet qu'une seule flèche par symbole pointant à partir d'un état. Par conséquent, ses États devraient être membres de l'ensemble des États...
La définition principale de la machine de Turing (TM), au moins dans mon propre manuel de référence (Hopcroft + Ullman 1979) est déterministe. Par conséquent, ma propre compréhension du problème de l' arrêt concerne principalement la MT déterministe, bien que je sache qu'il peut être envisagé pour...
Il s'agit d'une question complémentaire à celle- ci . Dans une question précédente sur les machines à états exotiques , Alex ten Brink et Raphael ont abordé les capacités de calcul d'une sorte particulière de machine à états: les automates à tas min. Ils ont pu montrer que l'ensemble des langages...
De Wikipedia sur les algorithmes randomisés Il faut distinguer les algorithmes qui utilisent l'entrée aléatoire pour réduire le temps d'exécution prévu ou l'utilisation de la mémoire, mais qui se terminent toujours par un résultat correct dans un laps de temps limité, et les algorithmes...
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...
Je sais que nous pouvons minimiser les DFA en trouvant et en fusionnant des états équivalents, mais pourquoi ne pouvons-nous pas faire de même avec les NFA? Je ne cherche pas une preuve ou quelque chose comme ça - à moins qu'une preuve soit plus simple à comprendre. Je veux juste comprendre...
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...
Je viens de commencer à lire sur la théorie du calcul. Si nous comparons ce qui est le plus puissant (en acceptant des chaînes), les deux sont identiques. Mais qu'en est-il de l'efficacité? DFA sera rapide par rapport à NFA, car il n'a qu'un seul bord sortant et il n'y aura aucune ambiguïté. Mais...
Demain c'est ma présentation et je veux clarifier mes concepts… J'ai lu que dans DFA, "Pour chaque état, la transition sur tous les symboles possibles (alphabet) devrait être définie." La définition de la transition sur tous les symboles possibles est-elle obligatoire pour chaque état dans DFA? Si...
Quelles sont les différences entre les machines de Turing déterministes et non déterministes? Modèles différents mais équivalents de NDTM. En particulier, quelle est cette expression fréquemment utilisée "devinez de façon non déterministe"? Comment l'utiliser correctement et exemples d'utilisation...
Dans l'image ci-dessous, j'essaie de comprendre exactement ce que cette NFA accepte. Ce qui me déroute, c'est le saut à .q 0ϵϵ\epsilonq0q0q_0 Si un est entré, le système passe-t-il à la fois à et (l'état d'acceptation)?q 0 q 1000q0q0q_0 q1q1q_1 Si un est entré, le système passe-t-il à la fois à et...
Au travail, j'ai été chargé de déduire des informations de type sur un langage dynamique. Je réécris des séquences d'instructions en imbriquéeslet expressions , comme ceci: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x then...
Mon manuel dit: "Nous définissons la fonction comme suit: f ( 1 ) = 2 et f ( i + 1 ) = 2 f ( i ) 1.2 . Notez que étant donné n , nous pouvons facilement trouver dans O ( n 1,5 ) fois le nombre i tel que n soit pris en sandwich entre f ( i ) et f ( i + 1f:N→Nf:N→Nf\colon
J'apprends à convertir des NFA en DFA et je veux m'assurer de bien faire les choses. Évidemment, revenir dans l'autre sens n'est pas une chose. Quelqu'un connaît-il un algorithme pour vérifier qu'un DFA est équivalent à un
Je travaille sur le livre Sipser (2e édition) et suis tombé sur cet exemple, que je ne comprends pas. Dans le livre, il indique que ce NFA accepte la chaîne vide,ϵϵ\epsilon. Quelqu'un pourrait-il m'expliquer pourquoi c'est le cas? Ma compréhension est que ϵϵ\epsilon se déplacera vers q3q3q_3 qui...
Soit une chaîne d'entrée donnée comme . Ensuite, si un NFA est actuellement dans l'état (et a lu l'entrée jusqu'à l'alphabet ), puis avant de lire le symbole d'entrée suivant, le NFA se divise en deux NFA, l'un étant dans l'état r et l'autre dans s , s'il y a une transition de le type r \...