Concept
Kleene's algorithm
Concepts associés (6)
Problème de la hauteur d'étoile
Le problème de la hauteur d'étoile, en théorie des langages formels, est le problème qui consiste à déterminer la hauteur d'étoile d'un langage rationnel, c'est-à-dire le nombre minimal d'étoiles de Kleene imbriquées nécessaires dans une expression rationnelle pour qu'elle puisse dénoter ce langage. Il existe des langages rationnels de hauteur d'étoile arbitrairement grande, mais la détermination de la hauteur d'étoile d'un langage rationnel, tout en étant décidable, est très difficile.
Algorithme de Thompson
En informatique théorique plus précisément en théorie des langages, l'algorithme de Thompson est un algorithme qui, étant donné une expression régulière, crée un automate fini qui reconnaît le langage décrit par cette expression. Il est nommé ainsi d'après Ken Thompson qui l'a décrit en 1968. Le théorème de Kleene affirme que l'ensemble des langages rationnels sur un alphabet est exactement l'ensemble des langages sur reconnaissables par automate fini. Il existe des algorithmes pour passer de l'un à l'autre.
Automate fini non déterministe
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.
Expression régulière
vignette|Stephen Cole Kleene, dont les travaux ont fondé le concept d'expression régulière. En informatique, une expression régulière ou expression rationnelle ou expression normale ou motif est une chaîne de caractères qui décrit, selon une syntaxe précise, un ensemble de chaînes de caractères possibles. Les expressions régulières sont également appelées regex (un mot-valise formé depuis l'anglais regular expression). Les expressions rationnelles sont issues des théories mathématiques des langages formels des années 1940.
Langage rationnel
En théorie des langages, les langages rationnels ou langages réguliers ou encore langages reconnaissables peuvent être décrits de plusieurs façons équivalentes : ce sont les langages décrits par les expressions régulières ou rationnelles, d'où le nom de langages réguliers ; ce sont les langages obtenus, à partir des lettres et de l'ensemble vide, par les opérations rationnelles, à savoir l'union, le produit et l'étoile de Kleene, d'où le nom de langages rationnels ; ce sont les langages reconnus par des auto
Automate fini déterministe
Un automate fini déterministe, parfois abrégé en AFD (en anglais deterministic finite automaton, abrégé en DFA) est un automate fini dont les transitions à partir de chaque état sont déterminées de façon unique par le symbole d'entrée. Un tel automate se distingue ainsi d'un automate fini non déterministe, où au contraire plusieurs possibilités de transitions peuvent exister simultanément pour un état et un symbole d'entrée donné.