Je fixe un langage régulier sur un alphabet , et je considère le problème suivant que j'appelle la planification de la lettre pour . De manière informelle, l'entrée me donne lettres et un intervalle pour chaque lettre (c'est-à-dire une position minimale et maximale), et mon objectif est de placer...
Il est bien connu que le problème suivant est PSPACE-complete: Étant donné l'expression régulière , ?L ( β ) = Σ ∗ββ\betaL ( β) = Σ∗L(β)=Σ∗L(\beta) = \Sigma^* Qu'en est-il de la détermination de l'équivalence avec d'autres expressions régulières (fixes) ?αα\alpha Étant donné l'expression régulière...
Le lemme de pompage pour les langues régulières peut être prouvé en considérant un automate à états finis qui reconnaît la langue étudiée, en choisissant une chaîne avec une longueur supérieure à son nombre d'états et en appliquant le principe du pigeonhole. Le lemme de pompage pour les langues...
Définissez la classe suivante de langues "circulaires" sur un alphabet fini Sigma. En fait, le nom existe déjà pour désigner une chose différente, semble-t-il, utilisée dans le domaine de l'informatique ADN. AFAICT, c'est une classe de langues différente. Un langage L est circulaire ssi pour tous...
Par exemple, dans les langages de programmation, il est courant d'écrire un compilateur / interprète X-in-X, mais à un niveau plus général, de nombreux systèmes Turing-complets connus peuvent se simuler de manière impressionnante (par exemple, simuler le jeu de la vie de Conway dans le jeu de la...
Je venais tout juste d'avoir une discussion sur les machines de Turing quand on m'a demandé: "La machine de Turing dérive-t-elle d'automates, ou est-ce l'inverse"? Je ne connaissais pas la réponse bien sûr, mais je suis curieux de le savoir. La machine de Turing est fondamentalement une version...
Je voudrais prouver (ou réfuter) la conjecture suivante: Conjecture : un automate à deux compteurs (2CA) ne peut pas décider de la langue suivante: les représentations ternaire et binaire de n ont à la fois une longueur paire ou une longueur impaire }L = { n ∣L={n∣L = \{ n \mid nnn}}\} Un 2CA peut...
Un DFA a un mot de synchronisation s'il existe une chaîne qui envoie n'importe quel état du DFA à un seul état. Dans «La conjecture de Cerny pour les automates apériodiques» de AN Trahtman (Mathématiques discrètes et informatique théorique vol. 9: 2, 2007, pp. 3-10), il écrit: Cerny a conjecturé en...
La question est simple et directe: pour un fixe nnn, combien de langues (différentes) sont acceptées par un DFA de taille nnn (c'est-à-dire nnn états)? Je vais déclarer officiellement ceci: Définissez un DFA comme ( Q , Σ , δ, q0, F)(Q,Σ,δ,q0,F)(Q,\Sigma,\delta,q_0,F) , où tout est comme d'habitude...
La plupart des implémentations modernes d'expressions régulières, telles que celles en perl ou .NET, vont au-delà de la définition informatique classique des REGEX avec des fonctionnalités comme lookahead et lookbehind. Ces fonctionnalités leur permettent-elles d'analyser des instructions qui ne...
Je travaille sur un problème posé pour une classe et j'ai pensé à une question liée à ce sur quoi je travaillais. Existe-t-il un nombre minimum d'états qu'un automate fini doit avoir pour accepter des chaînes binaires qui représentent des nombres divisibles par un entier n? Dans un ensemble de...
Considérons le langage composé de toutes les chaînes de k lettres sur Σ de telle sorte qu'il n'y ait pas deux lettres égales:Lk−distinctLk−distinctL_{k-distinct}kkkΣΣ\Sigma Lk−distinct:={w=σ1σ2...σk∣∀i∈[k]:σi∈Σ and ∀j≠i:σj≠σi}Lk−distinct:={w=σ1σ2...σk∣∀i∈[k]:σi∈Σ and ∀j≠i:σj≠σi} L_{k-distinct}...
Est-il possible de tester algorithmiquement si un nombre calculable est rationnel ou entier? En d'autres termes, serait-il possible pour une bibliothèque qui implémente des nombres calculables de fournir les fonctions isIntegerou isRational? Je suppose que ce n'est pas possible, et que cela est en...
J'essaie de résoudre un problème particulier et j'ai pensé que je pourrais le résoudre en utilisant la théorie des automates. Je me demande, quels modèles d'automates ont un confinement décidable en temps polynomial? c'est-à-dire que si vous avez des machines vous pouvez tester si...
Il y a de nombreuses années, j'ai entendu dire que le calcul du NFA minimal (automate fini non déterministe) à partir d'un DFA (déterministe) était une question ouverte, par opposition à la direction inverse qui est connue depuis des décennies et est bien étudiée avec un efficace algorithme....
En théorie des automates (automates finis, automates pushdown, ...) et en complexité, il existe une notion d '"ambiguïté". Un automate est ambigu s'il existe un mot avec au moins deux cycles d'acceptation distincts. Une machine est k- ambiguë si pour chaque mot w accepté par la machine il y a au...
Les automates déterministes bidirectionnels à un compteur de 2dca (Petersen, 1994) peuvent reconnaître le langage unaire suivant: POWER={02n∣n≥0}.POWER={02n∣n≥0}.\begin{equation} \mathtt{POWER} = \lbrace 0^{2^n} \mid n \geq 0 \rbrace. \end{equation} Existe-t-il une autre langue unaire non triviale...
Je m'intéresse aux propriétés des graphes dirigés aléatoires à degré fixe fixe dréd . J'imagine un modèle de graphique aléatoire où chaque sommet choisit d voisins (disons, avec remplacement) uar Question : Connaît-on la distribution stationnaire et les temps de mélange des marches aléatoires sur...
Dans le livre de Sakarovitch sur la théorie des automates, il est écrit dans l'introduction de la section sur les logiques du groupe libre que le matériel qui y est présenté jette "les bases d'une théorie véritablement mathématique des langages sans contexte". Néanmoins, cela n'est pas rendu...
Il existe des preuves théoriques que la construction de produits cartésiens naïfs pour l'intersection des DFA est "le meilleur que nous pouvons faire". Qu'en est-il de la concaténation de deux DFA? La construction triviale implique la conversion de chaque DFA en NFA, l'ajout d'une transition...