Movatterモバイル変換

[0]ホーム
URL:

Aller au contenu
Wikipédial'encyclopédie libre
Rechercher

Langage formel

Un article de Wikipédia, l'encyclopédie libre.
Page d’aide sur l’homonymie

Cet article concerne les langages formels en informatique. Pour d'autres usages, voirFormalisation (mathématiques).

Structure de la phraseColorless green ideas sleep furiously qui est syntaxiquement bien formée, mais n'a pas de sens (exemple historique deNoam Chomsky, 1957).

Unlangage formel, enmathématiques, eninformatique et enlinguistique, est un ensemble demots[1]. L'alphabet d'un langage formel est l'ensemble des symboles, lettres oulexèmes qui servent à construire les mots du langage ; souvent, on suppose que cet alphabet est fini. Lathé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 ouformules bien formées. Un langage formel est souvent défini par unegrammaire formelle, telle que lesgrammaires algébriques et analysé par desautomates.

Objectifs

[modifier |modifier le code]

La théorie des langages formels étudie les aspects purementsyntaxiques de tels langages, c'est-à-dire leur structure interne formelle. La théorie des langues est issue de lalinguistique, comme moyen de comprendre les régularités syntaxiques delangues naturelles :

L'étude des langages formels comporte l'ensemble des moyens de description et d'analyse de ces langages, comme lesgrammaires formelles pour la génération et lesautomates pour la reconnaissance, mais elle s'intéresse aussi à l'apprentissage automatique et latraduction automatique des langages. Dans le domaine de la traduction, la théorie des langages s'applique auxcompilateurs de langages de programmation.

Mots et langages

[modifier |modifier le code]
Article détaillé :Mot (mathématiques).

Définitions

[modifier |modifier le code]

On se donne un ensembleA{\displaystyle A}, appeléalphabet dont les éléments sont appelés deslettres.

Cette loi de composition interne est associative et admet le mot vide pour élément neutre (ce qui justifie la notation1{\displaystyle 1}). Par conséquent l'ensembleA∗{\displaystyle A^{*}}, muni de cette loi, est unmonoïde. C'est unmonoïde libre au sens de l'algèbre.

Unlangage formel est un ensemble de mots sur un alphabet fini, c'est-à-dire une partie dumonoïde libre sur cet alphabet.

Exemples

[modifier |modifier le code]

Quelques exemples de langages formels :

Construction d'un langage formel

[modifier |modifier le code]

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 :

Appartenance, calculabilité et complexité

[modifier |modifier le code]

Des questions typiques que l'on se pose à propos d'un langage formel sont les suivantes :

  • Peut-on décider par algorithme si un mot donné appartient à ce langage ?
  • Si oui, quelle est la complexitéalgorithmique d'une telle réponse ?

Ces questions ont des liens avec lacalculabilité et de lathéorie de la complexité.

Familles de langages

[modifier |modifier le code]

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, toutlangage rationnel estalgébrique, qui est lui-mêmecontextuel, qui est lui-mêmeré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 leurs propriétés.

Leslangages algébriques déterministes sont les langages reconnaissables par lesautomates à pile déterministes, et sont donc strictement inclus dans la famille des langages algébriques.

Leslangages 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 leslangages récursivement énumérables.

Opérations sur les langages formels

[modifier |modifier le code]

Plusieurs opérations peuvent être utilisées pour fabriquer de nouveaux langages à partir de langages donnés. Supposons queL etM soient des langages sur un certain alphabet commun.

Opérations ensemblistes

[modifier |modifier le code]

Les opérations ensemblistesintersection,union etcomplémentation sont définies comme pour tout ensemble.

Concaténation ou produit

[modifier |modifier le code]

Laconcaténation deL{\displaystyle L} et deM{\displaystyle M}, notée simplementLM{\displaystyle LM} est l'ensemble des mots de la formexy{\displaystyle xy} oùx{\displaystyle x} est un mot deL{\displaystyle L} ety{\displaystyle y} est un mot deM{\displaystyle M}.

Quotients ou résiduels

[modifier |modifier le code]

Lequotient à gauchex−1L{\displaystyle x^{-1}L} deL{\displaystyle L} par un motx{\displaystyle x} est l'ensemble des motsy{\displaystyle y} tels quexy{\displaystyle xy} appartient àL{\displaystyle L}. Le quotient à gauche est aussi appelérésiduel.

Lequotient à droiteLx−1{\displaystyle Lx^{-1}} deL{\displaystyle L} par un motx{\displaystyle x} est défini symétriquement comme l'ensemble des motsy{\displaystyle y} tels queyx{\displaystyle yx} appartient àL{\displaystyle L}.

Lequotient à gauche et lequotient à droite s'étendent aux langages. Ainsi, le quotient à gauche deL{\displaystyle L} par un langageM{\displaystyle M}, notéM−1L{\displaystyle M^{-1}L}, est la réunion des langagesx−1L{\displaystyle x^{-1}L} pourx{\displaystyle x} dansM{\displaystyle M}.

Étoile de Kleene

[modifier |modifier le code]

L'étoile de Kleene deL est l'ensemble notéL⋆{\displaystyle L^{\star }} composé des mots de la formeu1.u2.….un{\displaystyle u_{1}.u_{2}.\dots .u_{n}} avecn⩾0{\displaystyle n\geqslant 0} etu1,u2,…,un∈L{\displaystyle u_{1},u_{2},\dots ,u_{n}\in L}. Cet ensemble contient lemot vide.

Retourné ou image miroir

[modifier |modifier le code]

Lerenversé deL, notéLR{\displaystyle L^{R}} ouL~{\displaystyle {\tilde {L}}} contient lesmots miroirs des mots deL, c'est-à-dire les mots deL lus de droite à gauche.

Mélange ou « shuffle »

[modifier |modifier le code]

Lemélange deL etM, notéL ШM, est l'ensemble des mots pouvant s'écrireu1v1u2v2…unvn{\displaystyle u_{1}v_{1}u_{2}v_{2}\dots u_{n}v_{n}} oùn⩾0{\displaystyle n\geqslant 0} etu1,…,un,v1,…,vn{\displaystyle u_{1},\dots ,u_{n},v_{1},\dots ,v_{n}} sont des mots (éventuellement vides) tels queu1u2…un{\displaystyle u_{1}u_{2}\dots u_{n}} soit un mot deL etv1v2…vn{\displaystyle v_{1}v_{2}\dots v_{n}} soit un mot deM. Par exemple[2]{ab}{\displaystyle \{ab\}} Ш{ba}={abba,baab,baba,abab}{\displaystyle \{ba\}=\{abba,baab,baba,abab\}}.

Morphisme et morphisme inverse

[modifier |modifier le code]

Une applicationf:A∗→B∗{\displaystyle f:A^{*}\to B^{*}} est unmorphisme ouhomomorphisme sif(xy)=f(x)f(y){\displaystyle f(xy)=f(x)f(y)} pour tous motsx,y{\displaystyle x,y} deA∗{\displaystyle A^{*}}. L'image homomorphe d'un langageL{\displaystyle L} surA{\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 appellemorphisme inverse l'inverse d'un morphisme. Le morphisme inverse def:A∗→B∗{\displaystyle f:A^{*}\to B^{*}} est la fonction notéef−1{\displaystyle f^{-1}} deB∗{\displaystyle B^{*}} dans l'ensemble des parties deA∗{\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 langageM{\displaystyle M} surB{\displaystyle B} est le langage

f−1(M)=⋃y∈Mf−1(y){\displaystyle f^{-1}(M)=\bigcup _{y\in M}f^{-1}(y)}.

Un morphisme estnon effaçant oucroissant 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.

Propriétés de clôture

[modifier |modifier le code]

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.

Tableau des propriétés de clôture[3] des familles de langages issus de lahiérarchie de Chomsky
Langages
rationnels		Langages algébriques
déterministes		Langages
algébriques		Langages
contextuels		Langages
récursifs		Langages récursivement
énumérables
UnionClosPas de clôtureClosClosClosClos
IntersectionClosPas de clôturePas de clôtureClosClosClos
ComplémentaireClosClosPas de clôtureClosClosPas de clôture
ConcaténationClosPas de clôtureClosClosClosClos
Etoile de KleeneClosPas de clôtureClosClosClosClos
MiroirClosPas de clôtureClosClosClosClos
Mélange[4]ClosPas de clôturePas de clôturePas de clôturePas de clôturePas de clôture
MorphismeClosPas de clôtureClosPas de clôturePas de clôtureClos
Morphisme croissantClosPas de clôtureClosClosClosClos
Morphisme inverseClosClosClosClosClosClos

Notes et références

[modifier |modifier le code]
  1. ↑Un« mot » au sens mathématique du terme est une suite de symboles pris dans un ensemble dit« alphabet ».
  2. ↑Pour bien comprendre cet exemple, on écrit les lettres du deuxième mot en majuscules. Alors on obtient :
    {ab}{\displaystyle \{ab\}} Ш{BA}={abBA,aBbA,BAab,BaAb,BabA,aBAb}{\displaystyle \{BA\}=\{abBA,aBbA,BAab,BaAb,BabA,aBAb\}}
    et quand on remplace les majuscules par les minuscules, on a bien les mots indiqués.
  3. ↑Preuves dansOlivierCarton,Langages formels, calculabilité et complexité,[détail de l’édition](lire en ligne)
  4. ↑Preuves dans(en)Zoltán Ésik etImre Simon, « Modeling literal morphisms by shuffle »,Semigroup Forum,vol. 56,‎,p. 225-227.

Voir aussi

[modifier |modifier le code]

Sur les autres projets Wikimedia :

Bibliographie

[modifier |modifier le code]

Articles connexes

[modifier |modifier le code]

Liens externes

[modifier |modifier le code]

v ·m
Théorie des automates, des langages formels et des grammaires formelles
Hiérarchie de ChomskyGrammaireLangageAutomate

Type-0

Machine de Turing
Machine de Turing qui s'arrête toujours

Type-1

Type-2

Type-3

Grammaire régulière ou grammaire rationnelle

Chaque classe de langages est strictement contenue dans la classe immédiatement au-dessus d'elle.
Chaque automate et chaque grammaire d'une classe ont un équivalent dans la classe immédiatement au-dessus.
v ·m
Codage
Modèles de calcul
Algorithmique
Syntaxe
Sémantique
Logique mathématique
Mathématiques discrètes
Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Langage_formel&oldid=218580757 ».
Catégories :
Catégories cachées :
[8]ページ先頭
©2009-2025 Movatter.jp