Il existe un théorème qui dit que: Etant donné un automate à états finis ayant états, s'il existe une chaîne dont la longueur satisfait alors le langage accepté par l'automate est infini.nnnwwwn ≤ | w | ≤ 2 n - 1n≤|w|≤2n-1n \leq |w| \leq 2n-1 Je comprends la contrainte , mais je ne comprends pas...
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...
J'ai en quelques jours un examen et j'ai des problèmes pour résoudre cette tâche. Laisser LLL être une langue régulière sur l'alphabet ΣΣ\Sigma. Nous avons l'opération cycle(L)={xy∣x,y∈Σ∗ and yx∈L}cycle(L)={xy∣x,y∈Σ∗ and yx∈L}\operatorname{cycle}(L) = \{ xy \mid x,y\in \Sigma^* \text{ and } yx\in...
Donc, je me gratte la tête sur ce problème depuis quelques jours maintenant. Étant donné une certaine langueUNEAA et BBB c'est régulier, montrer que la langue LLL qui se compose de toutes les chaînes UNEAA dont la longueur est égale à une chaîne BBB est une langue régulière. Sous forme d'équation:...
Comment puis-je montrer que le problème de décider si un PDA accepte une chaîne du formulaire { w! w ∣ w ∈ { 0 , 1}∗}{w!w∣w∈{0,1}∗}\{ w!w \mid w \in \{ 0, 1 \}^*\} est indécidable? J'ai essayé de réduire ce problème à un autre indécidable, par exemple si deux grammaires sans contexte acceptent la...
Soit A={L∣Lis one-counter and L¯ is also one-counter}A={L∣Lis one-counter and L¯ is also one-counter}A= \{L \mid L \;\text{is one-counter and \(\bar{L}\) is also one-counter} \} En clair,Deterministic one-counter⊆ADeterministic one-counter⊆A\text{Deterministic one-counter} \subseteq A Est-ce le cas...
Est la langue L={0n1m∣n and m are co-prime}L={0n1m∣n and m are co-prime} L = \{0^n 1^m \mid n \text{ and } m \text{ are co-prime}\} sans contexte? Je suppose que ce n'est pas sans contexte car il semble trop compliqué pour un PDA de décider si 2 nombres sont co-amorcés ou non. J'ai essayé...
Notre PC fonctionne-t-il comme machine de Turing? Le modèle d'une machine de Turing se compose d'une bande mémoire infinie, ce qui signifie des états infinis. Mais supposons que si notre PC a 128 Mo de mémoire et 30 Go de disque, il aurait 256 ^ 30128000000 états et donc, il a des états finis. Je...
Considérez le problème d'univers suivant . Le problème de l'univers. Étant donné un ensemble fini pour une classe de langages, et un automate acceptant le langage L , décidez si L = \ Sigma ^ * .ΣΣ\SigmaLLLL=Σ∗L=Σ∗L=\Sigma^* Dans [1], il est indiqué et prouvé que le problème de l'univers est...
Ces diapositives de cours esquissent une preuve queL = {unenbn∣ n ≥ 0 } ∪ {unenb2 n∣ n ≥ 0 }L={anbn∣n≥0}∪{anb2n∣n≥0}L=\{ a^n b^n \mid n \geq 0 \} \cup \{ a^n b^{2n} \mid n \geq 0 \} ne peut être accepté par aucun automate déterministe à refoulement. Malheureusement, les diapositives ne donnent...
C'est quelque peu lié à une autre question que j'ai posée , mais je pense qu'elle est suffisamment différente pour justifier sa propre question. Je fais des recherches où j'essaie de trouver la structure des compléments d'une certaine classe de langages finis. Il est facile pour moi d'obtenir les...
J'essaie depuis un certain temps de trouver une construction afin de pouvoir démontrer formellement qu'un PDA déterministe est fermé sous complémentation. Cependant, il arrive que chaque idée que j'ai a quelque chose qui ne correspond pas à la fin. Pourriez-vous me donner un coup de main? Le...
Laisser MMM être un NFA acyclique. Depuis MMM est acyclique, L(M)L(M)L(M) est fini. Pouvons-nous calculer |L(M)||L(M)||L(M)| en temps polynomial? Sinon, pouvons-nous l'approcher? Notez que le nombre de mots n'est pas le même que le nombre de chemins d'acceptation dans MMM, qui est facilement...
Selon ce graphique , les DCFL sont fermés sous inversion. Cependant, je ne suis pas convaincu que la preuve intuitive (inversant les flèches de la machine à états finis contrôlant et commutant les poussées et les pops) pour cela semble dépendre du non-déterminisme dans le choix de la transition...
J'ai un automate fini sans état final / acceptant, donc F est vide. Comment puis-je le minimiser? J'ai obtenu ceci sur un test et je ne savais pas comment aborder le problème parce que l'automate n'avait aucun état d'acceptation. Un seul état initial avec toutes les transitions en lui-même est-il...
Je n'ai pas pu trouver de graphique décrivant ou de texte répondant à la question suivante: Existe-t-il une relation directe entre la complexité d'un algorithme (tel que le meilleur / pire cas de tri rapide) et la classe d'automates qui peuvent implémenter l'algorithme. Par exemple, existe-t-il une...
L:={w∈{0,1}∗|L:={w∈{0,1}∗|L := \{w \in \{0,1\}^* | la longueur de est impaire 1 est au milieu dewww∧∧ \wedge w}w}w\} Donc l'alphabet est . Mon problème est que je ne peux pas suivre l'égalité des caractères avant et après . Un DFA limité pour une longueur inférieure à 6:{0,1}∗{0,1}∗\{0,1\}^*111...
C'est quelque chose que je n'ai pas trouvé - mais j'ai toujours trouvé intéressant que le lemme de pompage soit juste un lemme (d'autant plus qu'il a le même nom pour les langues régulières, les langues sans contexte, etc ...) Qu'est-ce qu'un
Étant donné un DFA, A, soit L (A) le nombre de mots que A accepte. Je pense qu'il est facile de calculer L (A): Traduisez l'encodage de A en une expression régulière. Si l'étoile Kleene apparaît n'importe où dans l'expression - le langage est infini. Sinon: Parcourez et comptez toutes les...
Après ma classe de théorie du calcul aujourd'hui, cette question m'est venue à l'esprit: si un problème peut être résolu par un automate fini, ce problème appartient à P. Je pense que c'est vrai, puisque les automates reconnaissent des langages très simples, donc tous ces langages auraient des...