Langage local

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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é 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.

Définition[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 A2 telles que w est un mot de L si et seulement si[3] :

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

Ceci correspond, pour le langage L, à l'expression rationnelle (étendue)[1],[4] :

.

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

  1. tous les facteurs de longueur 2 de w sont dans l'ensemble A2 \ F,

mais celle-ci se prête moins bien à l'écriture formelle.

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 [4], les langages suivants sont locaux :

  • , car  ;
  •  ;
  •  ;

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

Automate local[modifier | modifier le code]

Exemple d'un automate local comme il intervient dans la construction de Glushkov.

Un automate local, aussi appelé automate de Glushkov[4], sur un alphabet à lettres est un automate déterministe complet à états ; les états sont en bijection avec les lettres, avec un état supplémentaire noté 1 qui et 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 est une transition de l'automate, alors . Aucune transition entre dans l'état initial.

Un chemin d'étiquette issu de l'état 1 passe donc successivement par les états . Le chemin est réussi et le mot est accepté si et seulement si

  1. est l'étiquette d'une transition depuis l'état 1 ;
  2. est un état final ;
  3. tous les facteurs 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]

Un langage formel est k-testable si appartenance d'un mot au langage peut être vérifiée et regardant seulement les préfixes, suffixes et la 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 langage strictement localement testable[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]

  1. a, b, c et d Salomaa 1981, p. 9.
  2. Lawson 2004, p. 130.
  3. Lawson 2004, p. 129.
  4. a, b, c et d Sakarovitch 2009, p. 228.
  5. ne contenant pas le mot vide, dans la version stricte de la définition
  6. Lawson 2004, p. 132.
  7. McNaughton et Papert 1971, p. 18.
  8. McNaughton et Papert 1971, p. 14.
  9. 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]

Articles connexes[modifier | modifier le code]