Langage local

En informatique théorique, et notamment en théorie des langages rationnels, un langage local est un langage formel pour lequel l'appartenance d'un mot au langage peut être testée en considérant les blocs de deux lettres consécutives ou, de manière plus imagée, en faisant glisser sur le mot une « fenêtre » de largeur 2^[1]. De manière équivalente, c'est un langage rationnel qui peut être reconnu par un automate fini déterministe d'un type particulier, appelé automate local^[2]. Ces automates et langages interviennent notamment dans la construction de Glushkov. Un langage local est un langage sans étoile.

Premier exemple[modifier | modifier le code]

Le langage des mots obtenus en concaténant le motif ab est un langage local. En effet, en faisant glisser une fenêtre de largeur 2 sur un mot, il suffit de vérifier :

que le mot commence par un a
que toute fenêtre de deux lettres n'est pas aa ou bb
que le mot termine par b.

Le mot abababab est dans ce langage. Le mot abababbab ne l'est pas car il y a une fenêtre de deux lettres qui est bb : abababbab.

Définition[modifier | modifier le code]

Définition formelle[modifier | modifier le code]

Un langage L sur un alphabet A est local s'il existe deux parties R et S de A et une partie F de A × A telles que w est un mot de L si et seulement si^[3] :

la première lettre de w est dans R ;
la dernière lettre de w est dans S ;
et aucun facteur de longueur 2 de w n'est dans F.

La dernière des conditions peut être remplacée par :

tous les facteurs de longueur 2 de w sont dans l'ensemble (A × A) \ F,

mais celle-ci se prête moins bien à l'écriture formelle^[pas clair].

Définition formelle avec expression rationnelle[modifier | modifier le code]

Autrement dit, un langage L est local s'il est décrit par une expression rationnelle (étendue)^[1]^,^[4] de la forme :

L=(RA^{*}\cap A^{*}S)\setminus A^{*}FA^{*}

.

où R, S sont des ensembles de lettres, et F est un ensemble de mots de longueur 2.

On retrouve aussi une version plus générale de la définition qui autorise l'adjonction du mot vide. L'expression régulière étendue d'un langage local montre qu'il est sans étoile.

Exemples[modifier | modifier le code]

Sur l'alphabet $A=\{a,b\}$ ^[4], les langages suivants sont locaux :

$ab$ , car $ab=aA^{*}\cap A^{*}b\setminus A^{*}\{aa,bb,ba\}A^{*}$ ;
$(ab)^{+}=(aA^{*}\cap A^{*}b)\setminus A^{*}\{aa,bb\}A^{*}$ ;
$a^{+}=(aA^{*}\cap A^{*}a)\setminus A^{*}\{ab\}A^{*}$ .

Propriétés[modifier | modifier le code]

La famille des langage locaux sur un alphabet donné est fermée par intersection et étoile de Kleene, mais pas par complément, union ou concaténation^[4].
Tout langage rationnel^[5] est l'image d'un langage local par un morphisme littéral^[1]^,^[6]^,^[7].

Automate local[modifier | modifier le code]

Un automate local, aussi appelé automate de Glushkov^[4], sur un alphabet $A$ à $s$ lettres est un automate déterministe complet à $1+s$ états $Q=\{1\}\cup A$ ; les états sont en bijection avec les lettres, avec un état supplémentaire noté 1 qui est aussi l'état initial. La propriété caractéristique de l’automate est que toutes les transitions aboutissant à un état a donné sont étiquetées par la lettre qui est l'état d'arrivée : si $(p,a,q)$ est une transition de l'automate, alors $a=q$ . Aucune transition entre dans l'état initial.

Un chemin d'étiquette $w=a_{1}a_{2}\cdots a_{n}$ issu de l'état 1 passe donc successivement par les états $a_{1},a_{2},\ldots ,a_{n}$ . Le chemin est réussi et le mot est accepté si et seulement si

$a_{1}$ est l'étiquette d'une transition depuis l'état 1 ;
$a_{n}$ est un état final ;
tous les facteurs $a_{i}a_{i+1}$ sont les étiquettes de transitions consécutives dans l'automate.

Ceci montre qu'un automate local reconnait un langage local et que, réciproquement, un langage local est reconnu par un automate local.

Langage localement testable[modifier | modifier le code]

On peut étendre la définition de langage local. Un langage formel est dit k-testable si l'appartenance d'un mot au langage peut être vérifiée en regardant seulement les préfixes, les suffixes et les facteurs de longueur k du mot. Un langage est dit localement testable s'il est k-testable pour un entier k^[8]. Un langage local est 2-testable^[1]. Il existe une distinction entre langages localement testables et langages strictement localement testables^[9]. Les premiers sont fermés pour les opérations booléennes, les deuxièmes ne le sont pas. La famille des langages localement testables forme une variété de langages formels.

Notes et références[modifier | modifier le code]

↑ ^{a b c et d} Salomaa 1981, p. 9.
↑ Lawson 2004, p. 130.
↑ Lawson 2004, p. 129.
↑ ^{a b c et d} Sakarovitch 2009, p. 228.
↑ ne contenant pas le mot vide, dans la version stricte de la définition
↑ Lawson 2004, p. 132.
↑ McNaughton et Papert 1971, p. 18.
↑ McNaughton et Papert 1971, p. 14.
↑ Yu 1997, p. 79-80.

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « local language (formal language) » (voir la liste des auteurs).

Bibliographie[modifier | modifier le code]

(en) Mark V. Lawson, Finite automata, Boca Raton/London/New York etc., Chapman and Hall/CRC, 2004, 307 p. (ISBN 1-58488-255-7, zbMATH 1086.68074, lire en ligne)
Robert McNaughton et Seymour Papert (avec un appendice de William Henneman), Counter-free Automata, MIT Press, coll. « Research Monograph » (n^o 65), 1971, 163 p. (ISBN 0-262-13076-9, zbMATH 0232.94024)
(en) Jacques Sakarovitch (traduit du français par Reuben Thomas), Elements of automata theory, Cambridge, Cambridge University Press, 2009, 758 p. (ISBN 978-0-521-84425-3, zbMATH 1188.68177)
Arto Salomaa, Jewels of Formal Language Theory, Pitman Publishing, 1981 (ISBN 0-273-08522-0, zbMATH 0487.68064)
Sheng Yu, « Regular Languages », dans G. Rozenberg, A. Salomaa (éditeurs), Handbook of Formal Languages, vol. 1 : Word, Language, Grammar, Springer Verlag, 1997 (ISBN 978-3-540-60420-4, DOI 10.1007/978-3-642-59136-5), p. 41-110

Articles connexes[modifier | modifier le code]

Portail de l'informatique théorique

[Sal97-1] {a b c et d} Salomaa 1981, p. 9.

[Law130-2] Lawson 2004, p. 130.

[Law129-3] Lawson 2004, p. 129.

[Sak228-4] {a b c et d} Sakarovitch 2009, p. 228.

[5] tenant pas le mot vide, dans la version stricte de la définition

[Law132-6] Lawson 2004, p. 132.

[MP18-7] McNaughton et Papert 1971, p. 18.

[8] McNaughton et Papert 1971, p. 14.

[Yu-9] Yu 1997, p. 79-80.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

v · m Automates finis et langages réguliers
Articles généraux	Théorie des automates Automate fini Machine abstraite
Automates finis	Automate fini déterministe Automate fini inambigu Automate fini non déterministe Construction par sous-ensembles Automate sur les mots infinis
Automates finis particuliers	Automate alternant Automate bidirectionnel Automate pondéré Automate probabiliste Automate quantique Automate temporisé Automate de Büchi Automate de Muller Modèle de Markov caché Système de transition d'états Structure de Kripke Machine à états abstraits Machine de Mealy Machine de Moore Transducteur fini Automate séquentiel
Langages réguliers	Langage rationnel Langage sans étoile Langage local Langage congruentiel Langage stochastique Lemme de l'étoile Lemme d'Arden ω-langage rationnel
Des automates aux langages	Expression régulière Algorithme de Conway Algorithme de McNaughton et Yamada Méthode de Brzozowski et McCluskey
Des langages aux automates	Dérivée de Brzozowski Algorithme de Thompson Construction de Glushkov Complexité en états
Minimisation	Théorème de Myhill-Nerode Équivalence de Nerode Minimisation d'un automate fini déterministe Algorithme de Moore Algorithme de Brzozowski Algorithme de Hopcroft
Équivalences	Théorème de Kleene Étoile de Kleene Monoïde syntaxique Théorème des variétés d'Eilenberg