Langage local

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.

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

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

• La famille des langage locaux sur un alphabet donné est fermée par intersection et étoile de Kleene, mais ni 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].

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 ${\displaystyle A}$ à ${\displaystyle s}$ lettres est un automate déterministe complet à ${\displaystyle 1+s}$ états ${\displaystyle 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 ${\displaystyle (p,a,q)}$ est une transition de l'automate, alors ${\displaystyle a=q}$. Aucune transition entre dans l'état initial.

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

1. ${\displaystyle a_{1}}$ est l'étiquette d'une transition depuis l'état 1 ;
2. ${\displaystyle a_{n}}$ est un état final ;
3. tous les facteurs ${\displaystyle 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.

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.

• (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

• Langage sans étoile
• Monoïde apériodique
• Construction de Glushkov