Concept
Langage rationnel
Concepts associés (32)
Semiautomaton
In mathematics and theoretical computer science, a semiautomaton is a deterministic finite automaton having inputs but no output. It consists of a set Q of states, a set Σ called the input alphabet, and a function T: Q × Σ → Q called the transition function. Associated with any semiautomaton is a monoid called the characteristic monoid, input monoid, transition monoid or transition system of the semiautomaton, which acts on the set of states Q.
Hiérarchie de Chomsky
vignette|Hiérarchie de Chomsky. En informatique théorique, en théorie des langages, et en calculabilité, la hiérarchie de Chomsky (parfois appelée hiérarchie de Chomsky-Schützenberger) est une classification des grammaires formelles (et par extension, des langages formels respectifs engendrés par les grammaires), esquissée par Noam Chomsky en 1956, et décrite de façon formelle en 1959. La hiérarchie introduite par Noam Chomsky repose sur le modèle de grammaire formelle.
Grammaire régulière
En informatique théorique, en théorie des langages, une grammaire régulière, rationnelle ou à états finis est une grammaire hors-contexte particulière qui décrit un langage régulier. Les grammaires régulières donnent donc une autre possibilité que les expressions rationnelles et les automates finis pour décrire un langage régulier. Une grammaire régulière peut être « à gauche » ou « à droite ». Une grammaire régulière à gauche est un ensemble de règles de la forme : où , sont des symboles non-terminaux et un symbole terminal.
Classe de complexité
En informatique théorique, et plus précisément en théorie de la complexité, une classe de complexité est un ensemble de problèmes algorithmiques dont la résolution nécessite la même quantité d'une certaine ressource. Une classe est souvent définie comme l'ensemble de tous les problèmes qui peuvent être résolus sur un modèle de calcul M, utilisant une quantité de ressources du type R, où n, est la taille de l'entrée. Les classes les plus usuelles sont celles définies sur des machines de Turing, avec des contraintes de temps de calcul ou d'espace.
Recursively enumerable language
In mathematics, logic and computer science, a formal language is called recursively enumerable (also recognizable, partially decidable, semidecidable, Turing-acceptable or Turing-recognizable) if it is a recursively enumerable subset in the set of all possible words over the alphabet of the language, i.e., if there exists a Turing machine which will enumerate all valid strings of the language. Recursively enumerable languages are known as type-0 languages in the Chomsky hierarchy of formal languages.
Monoïde syntaxique
En informatique théorique, et en particulier dans la théorie des automates finis, le monoïde syntaxique d'un langage formel est un monoïde naturellement attaché au langage. L'étude de ce monoïde permet de refléter certaines propriétés combinatoires du langage par des caractéristiques algébriques du monoïde. L'exemple le plus célèbre de cette relation est la caractérisation, due à Marcel-Paul Schützenberger, des langages rationnels sans étoile (que l'on peut décrire par des expressions rationnelles avec complément mais sans l'étoile de Kleene) : ce sont les langages dont le monoïde syntaxique est fini et apériodique, c'est-à-dire ne contient pas de sous-groupe non trivial.
Construction par sous-ensembles
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.
Transducteur fini
En informatique théorique, en linguistique, et en particulier en théorie des automates, un transducteur fini (appelé aussi transducteur à états finis par une traduction littérale de l'anglais finite state transducer) est un automate fini avec sorties. C'est une extension des automates finis. Ils opèrent en effet sur les mots sur un alphabet d'entrée et, au lieu de simplement accepter ou refuser le mot, ils le transforment, de manière parfois non déterministe, en un ou plusieurs mots sur un alphabet de sortie.
Langage de Dyck
En informatique théorique, et plus spécialement en théorie des langages, les langages de Dyck sont des langages formels particuliers. Un langage de Dyck est l'ensemble des mots bien parenthésés, sur un alphabet fini de parenthèses ouvrantes et fermantes. Par exemple, sur la paire de parenthèses formée de '(' et ')', le mot '(())()' est un mot bien parenthésé, alors que le mot '())(' ne l'est pas. Les langages de Dyck jouent un rôle important en informatique théorique pour caractériser les langages algébriques.
Lemme d'itération pour les langages algébriques
Le lemme d'itération pour les langages algébriques, aussi connu sous le vocable lemme de Bar-Hillel, Perles et Shamir, donne une condition de répétition nécessaire pour les langages algébriques. Sa version simplifiée pour les langages rationnels est le lemme de l'étoile. Une version plus élaborée du lemme d'itération est le lemme d'Ogden. Le lemme indique donc que, dans un langage algébrique, certains facteurs de mots assez longs peuvent être itérés de concert.