Dans mon cours de théorie de l'informatique, beaucoup de nos problèmes impliquent l'utilisation de l'induction sur la longueur de la chaîne d'entrée pour prouver les déclarations sur les automates finis. Je comprends l'induction mathématique, mais lorsque les cordes entrent en jeu, je suis vraiment...
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...
J'ai lu la page wikipedia de la règle 110 dans les automates cellulaires, et je sais plus ou moins comment ils fonctionnent (un ensemble de règles décide où tracer le prochain 1 ou 0). Je viens de lire qu'ils sont complets de Turing, mais je ne peux même pas comprendre comment «programmez-vous» la...
Laisser L={an∣∃p≥n p, p+2 are prime}.L={an∣∃p≥n p, p+2 are prime}.\qquad L = \{a^n \mid \exists_{p \geq n}\ p\,,\ p+2 \text{ are prime}\}. est-il régulier?LLL Cette question paraissait suspecte au premier coup d'œil et je me suis rendu compte qu'elle était liée à la conjecture principale jumelle ....
Je suis coincé sur la question suivante: "Les langages réguliers sont précisément ceux acceptés par les automates finis. Étant donné ce fait, montrez que si le langage est accepté par un automate fini, alors est également accepté par un certain fini; compose de tous les mots de inversé....
Une grammaire sans contexte peut-elle inclure des "états morts" d'un automate, tels que G = ( {a,b,c},{A,B,C} , { A → a B , B → b , B → C, C→ c C} , A )?g=({une,b,c},{UNE,B,C},{UNE→uneB,B→b,B→C,C→cC},UNE)?G = \big(\{a, b, c\}, \{A, B, C\}, \{A\to aB, B\to b, B\to C, C\to cC\}, A\big)\,? Les règles...
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...
Une machine de Turing sans capacité d'écriture sur des cellules vierges est-elle moins puissante que la Turing standard? Je pense que la réponse est oui mais je ne suis pas en mesure de trouver un calcul qu'une machine standard de Turing peut faire mais cette machine ne le peut pas. Des...
Par exemple, lorsque nous considérons un DFA qui autorise les chaînes n'ayant aucune sous-chaîne 00ou 11je peux produire les deux DFA suivants:
Le problème de savoir si deux automates déroulants reconnaissent la même langue est indécidable. Le problème de savoir si un automate pushdown reconnaît la langue vide est décidable, d'où il est également décidable s'il reconnaît une langue finie donnée. Il est indécidable que la langue acceptée...
On dit que l'intersection d'un langage L sans contexte avec un langage M normal est toujours sans contexte. J'ai compris la preuve de la construction de produits croisés, mais je ne comprends toujours pas pourquoi elle est sans contexte mais pas régulière. Le langage généré par une telle...
J'ai utilisé FSM dans les conceptions de circuits séquentiels numériques. Mais je ne connais pas les automates finis. Quelqu'un peut-il m'aider à comprendre la différence «fondamentale» entre les deux?
L'algorithme de minimisation DFA de Brzozowski crée un DFA minimal pour DFA en:GGG inverser tous les bords de , faisant de l'état initial un état accepté, et des états acceptés initiaux, pour obtenir un NFA pour le langage inverse,GGGN′N′N' en utilisant la construction du jeu de puissance pour...
Je me demande si cela est encore possible, puisque {anbncn∣n≥0}∉CFL{anbncn∣n≥0}∉CFL\{a^n b^n c^n \mid n \geq 0\} \not\in \mathrm{CFL} . Par conséquent, un PDA qui peut distinguer un mot w∈{anbncn∣n≥0}w∈{anbncn∣n≥0}w\in\{a^n b^n c^n \mid n \geq 0\} du reste de {a∗b∗c∗}{a∗b∗c∗}\{a^*b^*c^*\} pourrait...
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...
Un automate fini déterministe (DFA) est un modèle de machine à états capable d'accepter tous et seulement les langages réguliers. Les DFA peuvent être (et sont généralement) définis de telle manière que chaque état doit fournir une transition pour tous les éléments de l'alphabet d'entrée; en...
Les machines de comptage avec deux compteurs ou plus sont généralement équivalentes aux machines de Turing dans les cours sur la théorie du calcul. Cependant, je n'ai pas vu d'analyse formelle des langues pouvant être reconnues par une machine à guichet unique. Ces langues sont-elles équivalentes...
Étant donné un langage , définissez l'ensemble de longueur de comme l'ensemble de longueurs de mots dans : L L L S ( L ) = { | u |LLLLLLLLLL S (L)={ | u | ∣u∈L}LS(L)={|u|∣u∈L}\mathrm{LS}(L) = \{|u| \mid u \in L \} Quels ensembles d'entiers peuvent être l'ensemble de longueurs d'une langue...
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...
Récemment, une question intéressante a été posée puis supprimée. Pour un langage régulier , sa complexité DFA est la taille du DFA minimal qui l'accepte, et sa complexité NFA est la taille du NFA minimal qui l'accepte. Il est bien connu qu'il existe une séparation exponentielle entre les deux...