Existe-t-il des propriétés indécidables des automates linéaires bornés (en évitant l'astuce de la langue vide)? Et pour un automate fini déterministe? (mettre de côté l'intraçabilité). J'aimerais obtenir un exemple (si possible) d'un problème indécidable défini sans utiliser de machines Turing...
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...
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...
Étant donné un alphabet , combien de langues différentes sont régulièrement là- bas qui peuvent être acceptées par un -state automate fini non déterministe?Σ={a,b}Σ={a,b}\Sigma = \{ a,b \}nnn À titre d'exemple, considérons . Nous avons alors configurations de transition différentes et...
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 suis programmeur et je maîtrise les automates, mais pas la logique. J'ai lu dans les journaux que les deux sont très étroitement liés. Les automates finis déterministes (DFA), les automates arborescents et les automates à refoulement visible sont tous liés à la logique monadique du second ordre...
Je veux savoir si le problème suivant est décidable: Instance: un NFA A avec n états Question: Existe-t-il un nombre premier p tel que A accepte une chaîne de longueur p. Ma conviction est que ce problème est indécidable, mais je ne peux pas le prouver. Le décideur peut facilement avoir un...
J'étudie les langages formels et les systèmes de bases de production (systèmes de bases de règles) et je suis un peu confus quant à la raison pour laquelle ces deux mots "production" et "règle" signifient la même chose dans tant de contexte en informatique. En langue anglaise, ils ne semblent pas...
J'ai trouvé que si je ne comprends pas l'étymologie derrière un terme cs / programmation, cela signifie généralement que j'ai manqué ou mal compris un concept sous-jacent important. Je ne comprends pas pourquoi l'étoile Kleene est aussi appelée la fermeture Kleene. Est-ce lié aux fermetures de...
Apropois à la suggestion de Raphaël sur l' intersection de deux NPDA : Soit et A 2 NPDA pour les langues sans contexte L 1 et L 2 , respectivement. En supposant que nous savons que L = L 1 ∩ L 2 est sans contexte, pouvons-nous (effectivement) construire NPDA A pour L
Existe-t-il des structures robustes dans Game of Life de Conway ? Par exemple, quelqu'un a-t-il construit un vaisseau spatial avec un bouclier qui absorbe tous les petits oscillateurs et planeurs avec lesquels il entre en
J'ai lu dans Wikipedia et dans quelques autres textes Le problème d'arrêt est décidable [...] pour les automates linéaires bornés (LBA) et les machines déterministes à mémoire finie. Mais plus tôt, il est écrit que le problème d'arrêt est un problème indécidable et donc TM ne peut pas le résoudre!...
Existe-t-il un moyen naturel ou notable de relier ou de lier des groupes mathématiques et des langages CS formels ou un autre concept CS fondamental, par exemple les machines de Turing? Je recherche des références / applications. Notez cependant que je suis conscient du lien entre les semigroupes...
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...
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...
L'objectif est de créer DFA à partir d'une expression régulière et l'utilisation de "Exp régulière> NFA> Conversion DFA" n'est pas une option. Comment faut-il s'y prendre? J'ai posé cette question à notre professeur mais il m'a dit que nous pouvions utiliser l'intuition et a gentiment refusé...
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...
Donc, je sais que tester si un langage régulier RRR est un sous-ensemble du langage régulier SSS est décidable, car nous pouvons les convertir tous les deux en DFA, calculer R∩S¯R∩S¯R \cap \bar{S} , puis tester si ce langage est vide. Cependant, comme cela nécessite une conversion en DFA, il est...
Je suis nouveau dans les automates et je n'ai reçu une brève introduction aux expressions régulières qu'hier. J'ai lu les différentes règles qui définissent une expression régulière. Mais je suis incapable de faire la différence entre les expressions régulières et la grammaire d'une langue (on ne...
Sinon, qu'est-ce que cela signifie quand pour un état et un symbole , n'existe pas?a δ ( q , a )qqqaaaδ(q,a)δ(q,a)\delta(q,