Un langage formel, en mathématiques, en informatique et en linguistique, est un ensemble de mots. L'alphabet d'un langage formel est l'ensemble des symboles, lettres ou lexèmes qui servent à construire les mots du langage ; souvent, on suppose que cet alphabet est fini. La théorie des langages formels a pour objectif de décrire les langages formels.
Les mots sont des suites d'éléments de cet alphabet ; les mots qui appartiennent à un langage formel particulier sont parfois appelés mots bien formés ou formules bien formées. Un langage formel est souvent défini par une grammaire formelle, telle que les grammaires algébriques et analysé par des automates.
La théorie des langages formels étudie les aspects purement syntaxiques de tels langages, c'est-à-dire leur structure interne formelle. La théorie des langues est issue de la linguistique, comme moyen de comprendre les régularités syntaxiques de langues naturelles :
L'étude des langages formels comporte l'ensemble des moyens de description et d'analyse de ces langages, comme les grammaires formelles pour la génération et les automates pour la reconnaissance, mais elle s'intéresse aussi à l'apprentissage automatique et la traduction automatique des langages. Dans le domaine de la traduction, la théorie des langages s'applique aux compilateurs de langages de programmation.
On se donne un ensemble A {\displaystyle A} , appelé alphabet dont les éléments sont appelés des lettres.
Cette loi de composition interne est associative et admet le mot vide pour élément neutre (ce qui justifie la notation 1 {\displaystyle 1} ). Par conséquent l'ensemble A ∗ {\displaystyle A^{*}} , muni de cette loi, est un monoïde. C'est un monoïde libre au sens de l'algèbre.
Un langage formel est un ensemble de mots sur un alphabet fini, c'est-à-dire une partie du monoïde libre sur cet alphabet.
Quelques exemples de langages formels :
Un langage formel peut être spécifié par différents moyens. Ce qui est recherché, c'est une méthode ou un mécanisme fini, et explicite, qui permet de produire ou d'analyser un langage en général infini. Parmi ces méthodes, il y a :
Des questions typiques que l'on se pose à propos d'un langage formel sont les suivantes :
Ces questions ont des liens avec la calculabilité et de la théorie de la complexité.
Les langages sont regroupés en familles de langages. La Hiérarchie de Chomsky nous donne quatre types de grammaire, chaque type de grammaire générant une famille de langage.
Ces ensembles de langages sont tous inclus les uns dans les autres et sont ici donnés de l'ensemble le plus grand au plus petit. Donc, tout langage rationnel est algébrique, qui est lui-même contextuel, qui est lui-même récursivement énumérable.
Entre ces 4 familles de langages, on peut noter des familles qui ne font pas partie de la hiérarchie de Chomsky, mais qui restent remarquables par leurs définitions et leur propriétés.
Les langages algébriques déterministes sont les langages reconnaissables par les automates à pile déterministes, et sont donc strictement inclus dans la famille des langages algébriques.
Les langages récursifs sont les langages reconnus par une machine de Turing, et dont le complémentaire est aussi reconnu par une machine de Turing. Ils sont donc strictement inclus dans les langages récursivement énumérables.
Plusieurs opérations peuvent être utilisées pour fabriquer de nouveaux langages à partir de langages donnés. Supposons que L et M soient des langages sur un certain alphabet commun.
Les opérations ensemblistes intersection, union et complémentation sont définies comme pour tout ensemble.
La concaténation de L {\displaystyle L} et de M {\displaystyle M} , notée simplement L M {\displaystyle LM} est l'ensemble des mots de la forme x y {\displaystyle xy} où x {\displaystyle x} est un mot de L {\displaystyle L} et y {\displaystyle y} est un mot de M {\displaystyle M} .
Le quotient à gauche x − 1 L {\displaystyle x^{-1}L} de L {\displaystyle L} par un mot x {\displaystyle x} est l'ensemble des mots y {\displaystyle y} tels que x y {\displaystyle xy} appartient à L {\displaystyle L} . Le quotient à gauche est aussi appelé résiduel.
Le quotient à droite L x − 1 {\displaystyle Lx^{-1}} de L {\displaystyle L} par un mot x {\displaystyle x} est défini symétriquement comme l'ensemble des mots y {\displaystyle y} tels que y x {\displaystyle yx} appartient à L {\displaystyle L} .
Le quotient à gauche et le quotient à droite s'étendent aux langages. Ainsi, le quotient à gauche de L {\displaystyle L} par un langage M {\displaystyle M} , noté M − 1 L {\displaystyle M^{-1}L} , est la réunion des langages x − 1 L {\displaystyle x^{-1}L} pour x {\displaystyle x} dans M {\displaystyle M} .
L'étoile de Kleene de L est l'ensemble noté L ⋆ {\displaystyle L^{\star }} composé des mots de la forme u 1 . u 2 . … . u n {\displaystyle u_{1}.u_{2}.\dots .u_{n}} avec n ⩾ 0 {\displaystyle n\geqslant 0} et u 1 , u 2 , … , u n ∈ L {\displaystyle u_{1},u_{2},\dots ,u_{n}\in L} . Cet ensemble contient le mot vide.
Le renversé de L, noté L R {\displaystyle L^{R}} ou L ~ {\displaystyle {\tilde {L}}} contient les mots miroirs des mots de L, c'est-à-dire les mots de L lus de droite à gauche.
Le mélange de L et M, noté L Ш M, est l'ensemble des mots pouvant s'écrire u 1 v 1 u 2 v 2 … u n v n {\displaystyle u_{1}v_{1}u_{2}v_{2}\dots u_{n}v_{n}} où n ⩾ 0 {\displaystyle n\geqslant 0} et u 1 , … , u n , v 1 , … , v n {\displaystyle u_{1},\dots ,u_{n},v_{1},\dots ,v_{n}} sont des mots (éventuellement vides) tels que u 1 u 2 … u n {\displaystyle u_{1}u_{2}\dots u_{n}} soit un mot de L et v 1 v 2 … v n {\displaystyle v_{1}v_{2}\dots v_{n}} soit un mot de M. Par exemple { a b } {\displaystyle \{ab\}} Ш { b a } = { a b b a , b a a b , b a b a , a b a b } {\displaystyle \{ba\}=\{abba,baab,baba,abab\}} .
Une application f : A ∗ → B ∗ {\displaystyle f:A^{*}\to B^{*}} est un morphisme ou homomorphisme si f ( x y ) = f ( x ) f ( y ) {\displaystyle f(xy)=f(x)f(y)} pour tous mots x , y {\displaystyle x,y} de A ∗ {\displaystyle A^{*}} . L'image homomorphe d'un langage L {\displaystyle L} sur A {\displaystyle A} est l'ensemble
f ( L ) = { f ( x ) ∣ x ∈ L } {\displaystyle f(L)=\{f(x)\mid x\in L\}} .Par abus de langage, on appelle morphisme inverse l'inverse d'un morphisme. Le morphisme inverse de f : A ∗ → B ∗ {\displaystyle f:A^{*}\to B^{*}} est la fonction notée f − 1 {\displaystyle f^{-1}} de B ∗ {\displaystyle B^{*}} dans l'ensemble des parties de A ∗ {\displaystyle A^{*}} définie par
f − 1 ( y ) = { x ∈ A ∗ ∣ f ( x ) = y } {\displaystyle f^{-1}(y)=\{x\in A^{*}\mid f(x)=y\}} .Ce n'est en général pas un morphisme. L'image par un morphisme inverse d'un langage M {\displaystyle M} sur B {\displaystyle B} est le langage
f − 1 ( M ) = ⋃ y ∈ M f − 1 ( y ) {\displaystyle f^{-1}(M)=\bigcup _{y\in M}f^{-1}(y)} .Un morphisme est non effaçant ou croissant ou, par imitation de l'anglais, ε-free si l'image d'une lettre n'est jamais le mot vide. Dans ce cas, la longueur de l'image d'un mot est supérieure ou égale à celle du mot.
Une question commune sur ces opérations est de connaitre les propriétés de clôture de chaque famille de langage pour chacune de ces opérations, c'est-à-dire si le langage issu d'une opération reste dans la même famille de langages que les langages dont il est issu.
Langages rationnels |
Langages algébriques déterministes |
Langages algébriques |
Langages contextuels |
Langages récursifs |
Langages récursivement énumérables | |
---|---|---|---|---|---|---|
Union | Clos | Pas de clôture | Clos | Clos | Clos | Clos |
Intersection | Clos | Pas de clôture | Pas de clôture | Clos | Clos | Clos |
Complémentaire | Clos | Clos | Pas de clôture | Clos | Clos | Pas de clôture |
Concaténation | Clos | Pas de clôture | Clos | Clos | Clos | Clos |
Etoile de Kleene | Clos | Pas de clôture | Clos | Clos | Clos | Clos |
Miroir | Clos | Pas de clôture | Clos | Clos | Clos | Clos |
Mélange | Clos | Pas de clôture | Pas de clôture | Pas de clôture | Pas de clôture | Pas de clôture |
Morphisme | Clos | Pas de clôture | Clos | Pas de clôture | Pas de clôture | Clos |
Morphisme croissant | Clos | Pas de clôture | Clos | Clos | Clos | Clos |
Morphisme inverse | Clos | Clos | Clos | Clos | Clos | Clos |