Questions sur les dispositifs mathématiques qui lisent un flux d'entrée symbole par symbole et utilisent une carte de transition d'état pour produire un flux de sortie, peut-être en utilisant un stockage secondaire.
Convertir des expressions régulières en NFA (minimales) acceptant le même langage est facile avec des algorithmes standard, tels que celui de Thompson . L’autre direction semble être plus fastidieuse, cependant, et les expressions résultantes sont parfois désordonnées. Quels algorithmes existe-t-il...
Je conviens qu'une machine de Turing peut résoudre "tous les problèmes mathématiques possibles". Mais c’est parce qu’il ne s’agit que d’une représentation machine d’un algorithme: faites ceci en premier, puis faites-le, et enfin en sortie. Je veux dire que tout ce qui peut être résolu peut être...
Il existe de nombreuses méthodes pour prouver qu'une langue n'est pas régulière , mais que dois-je faire pour prouver qu'une langue est régulière? Par exemple, si on me donne que est régulier, comment puis - je prouver que les éléments suivants L ' est régulière, aussi?LLLL′L′L' L′: = { W ∈ L : u v...
Reportez-vous à la fin de cet article pour obtenir des éclaircissements sur la définition des automates min-tas. On peut imaginer utiliser diverses structures de données pour stocker des informations destinées à être utilisées par des machines à états. Par exemple, les automates déroulants stockent...
Dans cette réponse, il est mentionné Un langage régulier peut être reconnu par un automate fini. Un langage sans contexte nécessite une pile et un langage sensible au contexte nécessite deux piles (ce qui revient à dire qu'il nécessite une machine Turing complète) . Je voulais savoir en ce qui...
Appelons un langage déterministe sans contexte si et seulement si il peut être accepté par un automate push-down déterministe, et non déterministe autrement. Appelons un langage dépourvu de contexte intrinsèquement ambigu si et seulement si toutes les grammaires sans contexte qui génèrent le...
En théorie des automates, nous lisons tous les automates comme des automates finis, depuis le tout début. Ce que je veux savoir, c'est pourquoi les automates sont-ils finis? Pour être clair, qu'est-ce qui est fini dans un automate - l'alphabet, le langage, les chaînes faites avec des expressions...
Voyant que, dans la hiérarchie de Chomsky, les langues de type 3 peuvent être reconnues par une machine à états dépourvue de mémoire externe (c'est-à-dire un automate fini), le type 2 par une machine à états à pile unique (un automate à pile) et le type 0 par une machine d'état à deux piles (ou, de...
Dans ma classe, un étudiant a demandé si tous les automates finis pouvaient être dessinés sans croiser les bords (il semble que tous mes exemples l'ont fait). Bien sûr, la réponse est négative, l'automate évident pour la langue {x∈{a,b}∗∣#a(x)+2#b(x)≡0mod5}{x∈{a,b}∗∣#a(x)+2#b(x)≡0mod5}\{\;...
Je viens de terminer le premier chapitre de l' introduction à la théorie du calcul de Michael Sipser qui explique les bases des automates finis. Il définit un langage régulier comme tout ce qui peut être décrit par un automate fini. Mais je n'ai pas pu trouver où il explique pourquoi une langue...
Wikipédia ainsi que d'autres sources que j'ai trouvées listent le voidtype C comme type d'unité par opposition à un type vide. Je trouve cela déroutant car il me semble que cela voidcorrespond mieux à la définition d'un type vide / bas. Autant voidque je sache , aucune valeur n'habite . Une...
J'ai un ensemble de paires. Chaque paire est de la forme (x, y) telle que x, y appartiennent à des entiers de la plage [0,n). Donc, si le n est 4, alors j'ai les paires suivantes: (0,1) (0,2) (0,3) (1,2) (1,3) (2,3) J'ai déjà les paires. Maintenant, je dois construire une combinaison en utilisant...
Je fais une présentation sur les machines Turing et je voulais donner quelques informations sur les FSM avant de présenter les machines Turing. Le problème est que je ne sais vraiment pas ce qui est TRÈS différent les uns des autres. Voici ce que je sais que c'est différent: FSM a des états...
Cette question a été migrée depuis Stack Overflow car il est possible d'y répondre sur Computer Science Stack Exchange. Migré il y a 7 ans . J'ai créé un lexer et un analyseur d'expressions régulières simples pour prendre une expression régulière et générer son arbre d'analyse. La création d'un...
Le contexte linguistique suivant est-il libre? L={uxvy∣u,v,x,y∈{0,1}+,|u|=|v|,u≠v,|x|=|y|,x≠y}L={uxvy∣u,v,x,y∈{0,1}+,|u|=|v|,u≠v,|x|=|y|,x≠y}L = \{ uxvy \mid u,v,x,y \in \{ 0,1 \}^+, |u| = |v|, u \neq v, |x| = |y|, x \neq y\} Comme indiqué par sdcvvc, un mot dans cette langue peut également être...
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...
Existe-t-il un langage "naturel" indécidable? par "naturel", j'entends un langage défini directement par les propriétés des chaînes, et non via des machines et leurs équivalents. En d'autres termes, si le langage ressemble à où est un TM, DFA (ou regular-exp), PDA (ou grammaire), etc., alors n'est...
Étant donné une grammaire sans contexte G, il existe un automate N non déterministe à refoulement qui accepte exactement le langage que G accepte. (et vice versa) Il peut également exister un automate déterministe à refoulement qui accepte exactement le langage que G accepte également. Cela dépend...
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...