En informatique théorique, et notamment en théorie des automates, l'algorithme appelé la construction par sous-ensembles, en anglais « powerset construction » ou « subset construction », est la méthode usuelle pour convertir un automate fini non déterministe (abrégé en « AFN ») en un automate fini déterministe (abrégé en « AFD ») équivalent, c'est-à-dire qui reconnaît le même langage rationnel.
L'existence même d'une conversion, et l'existence d'un algorithme pour la réaliser, est remarquable et utile. Elle est remarquable parce qu'il existe peu de modèles de machines pour lesquels les versions déterministe et non déterministe ont la même puissance de reconnaissance : ainsi, les automates à pile déterministes sont moins puissants que les automates à pile généraux. Elle est utile dans la pratique parce que la reconnaissance par un automate déterministe est bien plus facile à mettre en œuvre que la reconnaissance par automate non déterministe. Toutefois, la construction par sous-ensembles peut produire un automate dont la taille, mesurée en nombre d'états, est exponentielle par rapport à la taille de l'automate de départ.
La construction par sous-ensembles a été publiée pour la première fois par Michael O. Rabin et Dana S. Scott dans un article fondateur paru en 1959. Ils ont obtenu le prix Turing pour leurs travaux autour du non-déterminisme en 1976.
Pour décrire le comportement d'un automate fini déterministe sur une entrée donnée, il suffit de conserver la trace d'un seul état à chaque instant, à savoir l’état atteint après avoir lu le début du mot donné en entrée.
Dans le cas d'un automate fini non déterministe, on doit conserver la trace d'un ensemble d'états, à savoir tous les états qui sont atteints, après la lecture d'un début du mot d'entrée, selon le choix des transitions qui ont été faites. Si, par la lecture d'un début de l'entrée, un ensemble d'états peut être atteint, alors l'ensemble des états accessibles par la lecture de la lettre suivante est une fonction déterministe de et de .
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
This course applies concepts from chemical kinetics and mass and energy balances to address chemical reaction engineering problems, with a focus on industrial applications. Students develop the abilit
We teach the fundamental aspects of analyzing and interpreting computer languages, including the techniques to build compilers. You will build a working compiler from an elegant functional language in
Learn the basics of plasma, one of the fundamental states of matter, and the different types of models used to describe it, including fluid and kinetic.
Learn the basics of plasma, one of the fundamental states of matter, and the different types of models used to describe it, including fluid and kinetic.
vignette|upright=1.5|Dans cet automate, tous les états sont accessibles, les états c, d et e sont indistinguables, ainsi que les états a et b. vignette|upright=1.5|Automate minimal équivalent. Les états indistinguables sont regroupés en un seul état. En informatique théorique, et plus particulièrement en théorie des automates, la minimisation d'un automate fini déterministe est l'opération qui consiste à transformer un automate fini déterministe donné en un automate fini déterministe ayant le nombre minimal d'états et qui reconnaît le même langage rationnel.
Un automate fini (on dit parfois, par une traduction littérale de l'anglais, machine à états finis, au lieu de machine avec un nombre fini d'états ou machine à états finie ou machine finie à états), finite-state automaton ou finite-state machine (FSA, FSM), est une machine abstraite qui est un outil fondamental en mathématiques discrètes et en informatique. On les retrouve dans la modélisation de processus, le contrôle, les protocoles de communication, la vérification de programmes, la théorie de la calculabilité, dans l'étude des langages formels et en compilation.
En informatique théorique, un automate de Büchi est un ω-automate ou automate fini opérant sur des mots infinis, avec une condition d'acceptation particulière : une trace (ou calcul ou chemin infini) est réussie si et seulement si elle passe un nombre infini de fois par au moins un état acceptant. Un mot infini est accepté s'il est l'étiquette d'un calcul réussi. Ce type d'automate est utilisé en vérification de modèles. Ce type d'automate a été défini par le mathématicien Julius Richard Büchi.
Explore la transition des expressions régulières aux automates finis, couvrant la création de lexers, les différents types d'automates et les processus de conversion.
Explore la conception du réacteur isotherme, y compris la stœchiométrie, les lois de vitesse et les simulations MATLAB, mettant en évidence le compromis entre la réactivité et la chute de pression.
Debugging real systems is hard, requires deep knowledge of the target code, and is time-consuming. Bug reports rarely provide sufficient information for debugging, thus forcing developers to turn into detectives searching for an explanation of how the prog ...
EPFL2013
,
We use results from communication complexity, both new and old ones, to prove lower bounds for unambiguous finite automata (UFAs). We show three results. 1) Complement: There is a language L recognised by an n-state UFA such that the complement language ...
Schloss Dagstuhl - Leibniz-Zentrum für Informatik2022
,
Non-malleable codes are a generalization of classical error-correcting codes where the act of "corrupting" a codeword is replaced by a "tampering" adversary. Non-malleable codes guarantee that the message contained in the tampered codeword is either the or ...