Décrivez une langue régulière qui ne peut être acceptée par aucun DFA qui ne comporte que trois états. Je ne sais pas trop par où commencer et je me demandais si quelqu'un pourrait me donner quelques conseils ou astuces. Je comprends que le lemme de pompage peut être utilisé pour prouver qu'une...
La question est à peu près dans le titre. Y a-t-il jamais un moment où une langue peut être acceptée par un DFA minimal avec états, mais , l'inversion de , peut être acceptée par un DFA avec états, où ?LLLL R L m m < nnnnLRLRL^RLLLmmmm <
Je travaille avec un algorithme de correspondance de motifs qui génère un automate à états finis acyclique qui accepte une chaîne de texte donnée et toutes ses sous-chaînes. L'algorithme FSA est exécuté sur une représentation symbolique d'un flux musical (par exemple, des données MIDI). Le flux...
J'ai essayé de déterminer si le problème d'arrêt est décidable pour les automates cellulaires unidimensionnels à 3 symboles. Définition Soit f(w,i)f(w,i)f(w,i) la configuration du système au pas de temps . Plus formellement , où est l'alphabet.iiif:A∗×N→A∗f:A∗×N→A∗f:A^*\times \mathbb{N} \to A^*AAA...
L'algorithme de Brzozowski peut être étendu aux automates de Moore mais sa complexité temporelle est exponentielle en général. Existe-t-il un autre algorithme pour minimiser les automates Moore? Quels sont les temps d'exécution de ces algorithmes, le cas
Il existe un moyen d'effectuer une analyse floue (accepte les chaînes même avec des fautes de frappe à une certaine distance d'édition), avec un DFA et un automate Levenshtein construit au moment de l'exécution du mot d'entrée. Peut-on faire quelque chose de similaire avec un analyseur Earley? J'ai...
J'apprends à convertir des NFA en DFA et je veux m'assurer de bien faire les choses. Évidemment, revenir dans l'autre sens n'est pas une chose. Quelqu'un connaît-il un algorithme pour vérifier qu'un DFA est équivalent à un
Prenons comme exemple la réduction 3d → 2d: Quel est le coût de simulation d'un automate cellulaire 3d par un automate cellulaire 2d? Voici un tas de questions plus spécifiques: Quels types d'algorithmes verront leur complexité temporelle modifiée, de combien? Quelle serait l'idée de base pour...
J'ai commencé à étudier les automates non déterministes en utilisant le livre de Hopcroft et Ullman . Je suis coincé dans un problème que j'ai trouvé très intéressant: Donnez un automate fini non déterministe acceptant toutes les chaînes qui ont la même valeur lorsqu'elles sont évaluées de gauche à...
Je suis coincé à résoudre le prochain exercice: Faire valoir que si est sans contexte et R est régulier, alors L / R = { w ∣ ∃ x ∈ RLLLRRR (c'est-à-dire lebon quotient) est sans contexte.L/R={w∣∃x∈Rs.twx∈L}L/R={w∣∃x∈Rs.twx∈L}L / R = \{ w \mid \exists x \in R \;\text{s.t}\; wx \in L\} Je sais qu'il...
Récemment, j'ai posé une question sur Math SE. Pas encore de réponse. Cette question est liée à cette question, mais plus de détails techniques vers l'informatique. Étant donné deux DFA et B = ( Q , Σ , δ , q 2 , F 2 ) où l'ensemble des états, l'alphabet d'entrée et la fonction de transition de A...
Existe-t-il un ensemble de règles ou de méthodes pour convertir une grammaire sans contexte en automates push down? J'ai déjà trouvé des diapositives en ligne mais je n'ai pas pu les comprendre. Dans la diapositive 10, il parle de certaines règles. Quelqu'un pourrait-il expliquer...
Je travaille sur le livre Sipser (2e édition) et suis tombé sur cet exemple, que je ne comprends pas. Dans le livre, il indique que ce NFA accepte la chaîne vide,ϵϵ\epsilon. Quelqu'un pourrait-il m'expliquer pourquoi c'est le cas? Ma compréhension est que ϵϵ\epsilon se déplacera vers q3q3q_3 qui...
J'ai lu des articles théoriques sur le langage formel et je suis tombé sur un terme que je ne comprends pas. Le document fera souvent référence à un ensemble «effectivement fermé sous intersection» ou à d'autres opérations. Que signifie "effectivement" ici? En quoi cela diffère-t-il de la fermeture...
Je génère des DFA aléatoires pour tester un algorithme de réduction DFA sur eux. L'algorithme que j'utilise actuellement est le suivant: pour chaque état , pour chaque symbole de l'alphabet c , ajoutez δ ( q , c ) à un état aléatoire. Chaque état a la même probabilité de devenir un état...
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...
Étant donné une langue régulière infinie LLL, comment puis-je prouver que LLL peut être partitionné en 2 langages réguliers infinis disjoints L1,L2L1,L2L_1, L_2? C'est:L1∪L2=LL1∪L2=LL_1 \cup L_2 = L, L1∩L2=∅L1∩L2=∅L_1 \cap L_2 = \varnothing, et L1L1L_1 et L2L2L_2 sont à la fois infinies et...
DFA, NFA et epsilon NFA tous les trois nous permettent de représenter une langue régulière particulière. Avec n'importe laquelle de ces représentations, nous pouvons arriver à la même expression régulière, alors pourquoi devons-nous étudier les trois formes de représentation des automates finis? Il...
Il me semble me rappeler dans une classe de premier cycle que pour une machine de Turing avec une bande finie, il existera toujours un automate d'état fini correspondant, mais je n'ai pu le trouver confirmé nulle part sur Internet. Est-ce vraiment le cas ou est-ce que je me souviens...
Soit une chaîne d'entrée donnée comme . Ensuite, si un NFA est actuellement dans l'état (et a lu l'entrée jusqu'à l'alphabet ), puis avant de lire le symbole d'entrée suivant, le NFA se divise en deux NFA, l'un étant dans l'état r et l'autre dans s , s'il y a une transition de le type r \...