Questions sur les automates finis déterministes
Je me suis amusé à réviser la théorie du calcul pour le plaisir et cette question me harcelait depuis un moment (drôle, je n'y ai jamais pensé lorsque j'ai appris la théorie des automates à mes études de premier cycle). Alors "pourquoi" étudions-nous exactement les automates finis déterministes et...
Après avoir étudié les automates à états finis (DFA) déterministes chez les étudiants de premier cycle, j’ai eu le sentiment qu’ils étaient extrêmement bien compris. Ma question est de savoir s'il y a quelque chose que nous ne comprenons toujours pas à leur sujet. Je ne parle pas de généralisations...
L'intersection de deux DFA (minimes) avec n états peut être calculée en utilisant O (n 2 ) temps et espace. Ceci est optimal en général, car le DFA résultant (minimal) peut avoir n 2 états. Cependant, si le DFA minimal résultant a z états, où z = O (n), peut-il être calculé dans l'espace n 2-eps ,...
Étant donné deux chaînes x et y, je veux créer une taille minimale DFA qui accepte x et rejette y. Une façon de le faire est la recherche par force brute. Vous énumérez les DFA en commençant par le plus petit. Vous essayez chaque DFA jusqu'à ce que vous en trouviez un qui accepte x et rejette y. Je...
Pour un alphabet fini fixe , un langage formel sur est régulier s'il existe un automate fini déterministe (DFA) sur qui accepte exactement .L ΣΣΣ\SigmaLLLΣΣ\SigmaLΣΣ\SigmaLLL Je m'intéresse aux langues qui sont "presque" régulières dans le sens où elles peuvent être reconnues par des familles...
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...
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...
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...
Il y a vingt ans, j'ai construit un package d'expressions régulières qui comprenait des conversions d'expressions régulières vers une machine à états finis (DFA) et pris en charge une multitude d'opérations d'expressions régulières fermées (Kleene star, concatenation, reverse, set operations,...
Il est connu que minimiser la taille d'une expression régulière est PSPACE-complete même si nous avons un DFA comme spécification du langage . Quels sont les résultats si la langue est finie? On peut considérer ce problème dans deux modèles: L'entrée correspond à toutes les chaînes du langage, et...
Contexte: Étant donné deux automates finis déterministes A et B, nous formons le produit C en laissant les états dans C être le produit cartésien des états dans A et des états dans B. Ensuite, nous choisissons les transitions, l'état initial et les états finaux de sorte que le langage accepté par C...
L'un des problèmes ouverts intéressants concernant les DFA est répertorié dans Existe-t-il des problèmes ouverts concernant les DFA? est la taille d'un DFA requis pour séparer deux chaînes de longueur . Je suis curieux de savoir s'il existe des résultats sur la capacité d'un DFA aléatoire à séparer...
J'ai un très gros automate fini non déterministe et je dois le convertir en DFA. En gros, je veux dire 40 000+ états. Jusqu'à présent, j'ai fait quelques expériences et programmé l'algorithme par défaut qui recherche dans la table (comme décrit ici ), mais même après l'optimisation est assez lente...
Inspiré par cette question , je suis curieux de savoir ce qui suit: Quelle est la pire des situations pour vérifier si un DFA donné accepte le même langage qu'une expression régulière donnée? Est-ce connu? L'espoir serait que ce problème soit en P - qu'il existe un algorithme polynomial dans la...
Tous mes manuels utilisent le même algorithme pour produire un DFA avec une expression régulière: créez d'abord un NFA qui reconnaît le langage de l'expression régulière, puis, en utilisant la construction du sous-ensemble (aka "powerset"), convertissez le NFA en un DFA équivalent ( en minimisant...
Je suis intéressé par une légère généralisation de DFA. Comme d'habitude, nous avons un ensemble d'états , un alphabet fini , une action définie sur par et l'état initial ; mais au lieu de l'ensemble habituelle terminal, nous prenons une famille de sous - ensembles de . Un DFA multilingue est alors...
Les transducteurs considérés ici sont ceux que Wikipedia appelle les transducteurs à états finis . Le comportement d'un transducteur , qui est la relation qu'il calcule, est écrit : un mot est une sortie pour ssi .[ T ] y x x [ T ] yTTT[ T][T][T]yyyXxxx [ T] yx[T]yx[T]y Question: Le problème...
Mise à jour: Il semble que ce problème ait été étudié et résolu récemment, voir cet article wiki: http://en.wikipedia.org/wiki/Tree_walking_automaton Et aussi cette enquête: http://www.mimuw.edu.pl/~bojan /papers/twasurvey.pdf Supposons qu'au lieu de l'ensemble habituel de mots, {0,1} *, nos mots...
Je suis intéressé par des algorithmes efficaces pour l'intersection DFA pour des cas spéciaux. A savoir, lorsque les DFA se croisent obéissent à une certaine structure et / ou opèrent sur un alphabet limité. Y a-t-il une source où je peux trouver des algorithmes de tels cas? Afin de ne pas rendre...
Soit un alphabet de taille 2 , et considérons des DFA minimaux dont la taille est limitée par au plus m . Soit f ( m ) le nombre de différents DFA minimaux.ΣΣ\Sigma222mmmF( m )f(m)f(m) Peut-on trouver une formule sous forme fermée pour ?F( m )f(m)f(m) Considérant que pour la fonction de transition...