Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Langage rationnel
Résumé
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 automates finis, d'où le nom de langages reconnaissables.
Les langages rationnels ont de très nombreuses applications, à la fois théoriques et pratiques. Ils sont utilisés en informatique (par exemple en compilation), en linguistique (par exemple pour décrire la morphologie d'une langue), ils interviennent dans les traitements de texte, ou dans des commandes spécifiques comme grep du système Unix.
Pour la manipulation des langages rationnels et des automates, il existe de nombreux outils informatiques, notamment dans les systèmes du type Unix comme la commande lex. Le langage informatique Java fournit aussi la classe Pattern. Les algorithmes utilisés pour manipuler les langages rationnels possèdent en général une implémentation rapide et efficace.
On considère un ensemble fini de caractères ou lettres, appelé alphabet. Une chaîne de caractères (ou chaîne ou mot) est une suite finie, éventuellement vide, de caractères. Par exemple, la chaîne formée de la lettre , puis de la lettre , puis encore de la lettre , se note .
L'ensemble des mots que l'on peut former avec ces lettres de est noté .
Toute partie de s'appelle un langage.
Les opérations suivantes, définies sur les langages, sont appelées les opérations rationnelles. Soient et deux parties de :
- la concaténation ou le produit de et , noté , est l'ensemble de mots , où est dans et est dans . Par exemple, le produit de et de est ;
- lunion ensembliste, de et , notée , est l'ensemble des mots appartenant à ou à . Par exemple, l'union ensembliste de et de est ;
Source officielle
À propos de ce résultat
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.
Publications associées (1)
Concepts associés (48)
Théorie des automates
En informatique théorique, l'objectif de la théorie des automates est de proposer des modèles de mécanismes mathématiques qui formalisent les méthodes de calcul.
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
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.
Cours associés (14)
MATH-305: Introduction to partial differential equations
This is an introductory course on Elliptic Partial Differential Equations. The course will cover the theory of both classical and generalized (weak) solutions of elliptic PDEs.
MATH-483: Gödel and recursivity
Gödel incompleteness theorems and mathematical foundations of computer science
MATH-213: Differential geometry
Ce cours est une introduction à la géométrie différentielle classique des courbes et des surfaces, principalement dans le plan et l'espace euclidien.
Séances de cours associées (116)
Construction de solutions par Dirichlet-Laplace
Explore la construction de solutions par Dirichlet-Laplace dans des domaines généraux.
Produits dérivés en continu
Couvre le concept de dérivés continus et leur application dans l'analyse des fonctions et la détermination des points critiques.
Régularité des solutions faibles
Explore les PDE elliptiques, les solutions faibles, la régularité et les solutions fortes, en mettant l'accent sur les solutions classiques et les techniques de preuve.