Langage de caractères

 

    1. Introduction
    2. La production
    3. Les règles de réécriture
    4. L' extension élémentaire
    5. Le codage des mots
    6. Les grammaires
    7. Les machines de Turing
    8. Les 4 types de grammaires (Hiérarchie de Chomsky)
    9. Les automates finis
    10. Compilation des grammaires régulières
    11. Programmation des automates finis déterministes
    12. La construction des langages réguliers

     

1) Introduction

Les langues écrites utilisent un alphabet fini et leurs mots sont des séquences de caractères appartenants à cet alphabet. C'est ainsi que l'on définie les langages de caractères, dits langages formels. Etant donné un alphabet A = {a,b,c}. Le langage mère qui inclus tous les langages de caractères d'alphabet A, est l'ensemble de toutes les séquences finies de caractères appartenants à A. On le note A** est l'opérateur de Kleene. A* est appelé la fermeture de Kleene de l'ensemble A.

A = {a, b, c}
A* = {ε, a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, aab,...}

Les mots du langage mère sont les séquences finies de caractères appartenants à A, et il existe un mot particulier, noté ε, qu'est la séquence vide de caractère.

Les langages de caractères semblent d'apparence plus simple que les langages d'opérateurs, les mots étant simplement des séquences de caractères.

Mais les structures se définissent en termes d'opérateurs, rendant explicite l'opération de construction. La structure du langage de caractères comprend des opérateurs zéro-aire que sont les caractères de l'alphabet, un opérateur zéro-aire particulier qu'est ε, et un opérateur binaire qu'est la concaténation et que l'on note *. Pourtant le symbôle * n'apparait pas dans les expressions des mots. En effet c'est une opération abstraite qui apparait dans notre façon de voir, selon un paradigme constructif et opérationnel binaire. L'opération de concaténation existe et elle est nécessaire pour construire les éléments de la structures appelés mots du langage de caractères. Si nous la rendons explicite, nous obtenons :

A* = {ε, a, b, c, a*a, a*b, a*c, b*a, b*b, b*c, c*a, c*b, c*c, a*a*a, a*a*b,...}

Mais il est plus pratique de convenir que l'opération de concaténation est notée par absence de symbôle entre deux caractères ou mots. Cela constitue une règle syntaxique. Dans ce cas une expression telle que aεbε sera interprétée comme a*ε*b*ε, et sera égale à a*b et finalement à ab.

La structure se présente alors ainsi avec ses générateurs et sa théorie :

A* = <ε, a, b, *> / {* est associatif, ε est l'élément neutre de *}

{* est associatif} <=> {∀x,∀y,∀z, (x*y)*z = x*(y*z)}
{ε est l'élément neutre de *} <=> {∀x, ε*x = x, x*ε=x}

Si on enlève l'élément ε, on obtient une structure constructivement un peu plus simple :

A*-{ε} = <a, b, *> /{* est associatif}

Mais d'un point de vue catégoriel, il s'agit de la même structure, l'élément neutre ε pouvant être ajouté sans modifier la théorie antérieur relative à l'ensemble sous-jacent initiale, c'est à dire sans changer les propriétés des autres opérateurs relativement à l'ensemble sous-jacent tel qu'il était avant l'ajout de l'élément ε.

En s'inspirant du point de vue intuitioniste (voir structures), le patron de cette structure est "Monoïde de type fini". La notation programmative est : Monoïde de type fini (*,A)A est l'alphabet, c'est à dire un ensemble fini d'éléments qui vont engendrer le monoïde. La notation linguistique est : <*, @A> / {* est associatif} où il faut remplacer @A par l'énumération des éléments de A. Dans la pratique on préfère énumérer précisément les caractères de l'alphabet, et le nom du patron change alors selon le nombre de caractères contenus dans l'alphabet. On parlera de Monoïde bigène (*,a,b), de Monoïde trigène (*, a,b,c), etc.. Et si on ajoute l'élément neutre, on enrichie la structure, le patron devient Monoïde unitaire de type fini (*,ε,A), ou Monoïde unitaire bigène (*,ε,a,b), etc.. Noter que dans la notation linguistique les éléments entre crochets < > peuvent être mis dans n'importe quel ordre. Parcontre, dans la notation programmative le patron assigne un sens précis à chaque élément de la présentation. Ainsi Monoïde unitaire bigène (*,ε,a,b) assigne un premier élément qui est l'opération associative *, un second élément qui est l'élément neutre ε, un troisième élément qui est le premier générateur et un quatrième élément qui est le deuxième générateur.

Monoïde unitaire bigène (*, ε, a,b) = <*, ε, a,b> / {* est associatif, ε est l'élément neutre de *}

Mais il existe une autre façon de définir les monoïdes, jugée plus simple, puisque n'utilisant que des opérateurs unaires et aucun opérateur binaire. Au lieu de considérer une opération d'assemblage binaire *(.,.), on considère les caractères comme des fonctions unaires, formant ainsi des objects enfichables les uns dans les autres pour former des mots. La structure se présente alors comme l'ensemble des fonctions unaires constructibles à partir des deux fonctions unaires a(.) et b(.) ce qui se note par <a(.), b(.)>1 où le chiffre 1 indique que l'on s'intéresse à l'ensemble des opérateurs unaires constructibles. L'ajout de ε revient à ajouter l'identité ε = (x-->x).

Comme il n'y a pas de règle d'égalité supplémentaire ces structures sont qualifiées de libre. Le langage libre d'alphabet A est le monoïde libre engendré par A.

2) La production

Dans le cas général, une règle de production va pouvoir utiliser les connaissances introspectives déjà acquises, c'est à dire tous les mots déjà produits, pour produire d'autres mots selon un processus calculatoire.

Une règle de production peut donc prendre en argument une liste de mots de taille quelconque mais finie, et produire une énumération de mots non nécessairement finie mais évidemment énumérable. L'object dynamique ainsi défini s'apparente à un programme d'arité d'entré variable pouvant produire une énumération infinie de résultats.

Dans toute sa généralité, une règle de démonstration correspond à une telle règle de production. C'est pourquoi on choisie comme symbôle de production le symbôle de démonstration .

Un ensemble finie de règles forme alors une théorie.

Il est déjà possible de généraliser la notion de production à celle d'un processus calculatoire pouvant opérer sur une liste finie ou infinie de mots et produire une liste finie ou infinie de mots. Ces processsus se composent ente-eux, comme les processus d'un système UNIX à l'aide de tubes (pipeline), de la même façon que les fonctions se composent entres-elles. La différence tient dans l'arité des entrés et des sorties qui sont variables et peuvent être infinies.

Le programme ou le processus est beaucoup plus souple que la fonction. La fonction est trop rigide. Aussi ce n'est pas la fonction qu'il faut définir en premier mais bien le programme ou le processus. La formalisation du programme nécessite de choisire un langage de données pour coder les entrées et les sorties, et un langage de programmation pour coder le programme. Le langage de programmation peut être perçu comme une extension du langage de données, il comprend donc le langage de données.

Mais nous n'allons pas étudier la programmation tout de suite. Nous allons d'abord nous restreindre à des règles de productions simples jugés pertinentes sur les langages de caractères c'est à dire sur les structures de monoïde libre de type fini, et s'appliquant à un mot à la fois, et qui retourne un nombre fini de résultats.

3) Les règles de réécriture

Nous nous intéressons à un type de règle de production utilisée en linguistique que sont les règles de réécriture s'appliquant à un mot et procédant par recherche d'occurence de séquence et par substitution de séquence.

Le langage libre d'alphabet A est le monoide libre engendré par A. Une règle de réécriture va appliquer une égalité entre deux portions de mot et les substituer dans un sens donné. Ces règles vont nous permettre de mieux appréhender la structure du monoïde que constitue le langage libre.

On cherche toujours à réunir les trois pans du langage que sont le langage de données, le langage de programmation, et le langage de propriétés, d'une manière plus fonctionnelle et utile que le codage des formules proposées par Godel pour démontrer l'incomplétude de l'Arithmétique.

Une règle est constituée de deux mots séparés par le symbôle -->. Par exemple la règle ab-->ba signifie que l'on peut remplacer dans chaque mot le sous-mot ab par le sous-mot ba. Si le premier mot est le mot vide ε tel que par exemple ε-->ab alors cela signifie que l'on peut insérer la séquence ab en tout endroit du mot.

Un lien étroit s'opère entre la grammaire qui regroupe l'ensemble des règles choisies, et la présentation de la structure de monoïde qui regroupe l'ensemble des règles d'égalités choisies, à ceci près que l'égalité fonctionne dans les deux sens alors que la règle de réécriture ne fonctionne que dans un sens. Voyez par exemple :

Présentation de monoïde
Grammaire
<a,b,c> / {ab=ba, abc=c, cc=1}
ab-->ba
ba-->ab
abc-->c
c-->abc
ε-->cc
cc-->ε

(Un monoïde non commutatif est présenté habituellement en notation multiplicative, et le 1 désigne l'élément neutre).

La règle de réécriture correspond à une sorte de demi-règle d'égalité. Toutes deux sont des éléments d'une théories et font donc partie d'un langage de propriétés. Les règles de réécritures enrichissent le langage de propriétés. Nous avons :

{ab-->ba, ba-->ab} <=> {ab=ba}

Le langage de propriétés est une extension du langage de données, donc il le contient. Un mot peut être considéré comme une règle particulièrement simple. Il traduit en terme programmatif la production de ce mot à partir uniquement de cette règle. Et il traduit en terme de propriété l'affirmation que ce mot est dans le noyaux de la théorie. Ce noyaux, également appellé langage de la grammaire, est l'intersection entre la théorie et le langage libre concerné.

Ainsi {abc, ab-->ba} bac signifie que la théorie {abc, ab-->ba} démontre bac et donc que abc et bac appartiennent au noyaux de la théorie {abc, ab-->ba}. La théorie constitue un pédicat défini sur les mots du langage de données, c'est à dire sur les mots du langage libre A*. Pour tout mot de A* tel que par exemple abc nous avons soit T ⊢ abc ou soit T ⊬ abc. De même la théorie constitue un pédicat défini sur les mots du langage de propriété que sont les règles appartenant à A*2. Pour tout couple de mots tel que par exemple ab-->ba nous avons soit T ⊢ ab-->ba ou soit T ⊬ ab-->ba.

L'ensemble des règles démontrables par T est énumérable mais en général son complémentaire ne l'est pas. C'est à dire que nous avons un procédé qui énumère toutes les règles démontrables par T, parcontre nous n'avons pas de procédé qui énumère toutes les règles non démontrables par T.

Il est possible de composer deux règles directement mais cela entraine une perte d'information par rapport à l'application successive de ces deux règles. La composition de deux règles r1 et r2 se note r1•r2 en notation française, et consiste à substituer une sous-séquence de la sortie de la règle r1 coïncidant avec l'entré de la règle r2 par la sortie de la règle r2. Cela produit la règle composées de l'entrée de la règle r1 et de la sorties de la règle r1 dans laquel ont a remplaçé une occurence du mot d'entré de la règle r2 par le mot de sortie de la règle r2. Parcontre les règles composées d'un seul mot ne peuvent se composer que dans un sens, car elle n'ont pas de mot d'entré, juste un mot de sortie. La perte d'information occasionnelle produit par la composition de deux règles r1 et r2 se traduit par l'inclusion suivante :

∀m∈A* ∀r1∈A*2 ∀r2∈A*2   m•(r1•r2) ⊂ (m•r1)•r2

On utilise la notation ensembliste, faisant que pour tout mot m et toute règle r, l'expression m•r est identique à {m}•r et à m•{r} et à {m}•{r} et est égale à l'ensemble des mots obtenus en appliquant au mot m la règle r. Pour tout ensemble de mots E, et pour tout ensemble de règles R, l'expression E•R désigne l'ensemble des mots produits en prenant chaque mot de E et en appliquant chaque règle de R.

4) L'extension élémentaire

Les règles ainsi programmées ne sont pas assez puissantes, mais il existe un moyen simple d'augmenter leur puissance sans modifier les principes précédement décrits, qui consiste à procéder à une extension élémentaire de la structure de monoïde. On ajoute à l'alphabet des caractères supplémentaires B,C,D. Ces symbôles ne sont pas des variables mais des caractères rajoutés dans l'alphabet. Et il existe alors deux noyaux, un noyaux étendu comprenant tous les mots d'alphabet A⋃{B,C,D} démontrables par T et qui constitue le langage étendu de la grammaire, et le noyaux proprement dit comprenant tous les mots d'alphabet A démontrables par T et qui constitue le langage de la grammaire.

Démontrable veut dire qui peut être construit. C'est pourquoi les intuitionistes ont un point d'avance sur les autres écoles. Et en unifiant de façon pertinente les trois pans du langages que sont le langage de données, le langage de programmation et le langage de propriétés, la construction d'une propriété, autrement dit sa démonstration, signifiera la même chose que la construction d'un programme ou d'une structure.

Les règles de réécritures s'appliquent à un mot à la fois en le réécrivant et en remplaçant une sous-séquence au choix qui doit coïncider exactement au premier membre de la règle, par le second membre de la règle. Par exemple la règle ab-->c appliquée au mot abc produit le mot cc. Pour augmenter la capacité d'expression des grammaires, on ajoute des caractères en majuscules B,C,D, appelés caractères non terminaux. W={B,C,D}. Cela correspond à une extension élémentaire de la structure de monoïde libre, passant de A* à (A⋃{B,C,D})*.

Les caractères a,b,c..., sont appelés caractères terminaux. Le mot vide ε est appellé un mot terminal. Les mots de (AW)* qui contiennent au moins un caractère non terminal sont appelés mots non terminaux, et les mot de A* sont appellés mots terminaux. Ainsi le noyau de la théorie contient les mot terminaux démontrables par la théorie, et le noyau étendu de la théorie contient tous les mots (terminaux et non terminaux) démontrables par la théorie.

Une règle de construction est composée de deux mots de (AW)*, un mot d'entré, et un mot de sortie. Par exemple la règle aB --> b s'applique au mot caB pour produire le mot cb. Lorsque plusieurs règles ont le même premier membre, on les réunie en une seul règle produisant autant de mots séparées par le symbôle | qui dénote l'alternative. Par exemple la règle : aB --> C|aa appliquée à la séquence caB produit le mot cC et le mot caa. Quant une règle peut s'appliquer de différentes façons, il faut considérer tous les résultats possibles. Par exemple la règle aB --> C appliquée une fois à la séquence aBaBa produit les mots CaBa et aBCa.

5) Le codage des mots

Prenons quelques caractères : a, b, c, et regroupons-les dans un ensemble A={a,b,c} appelé alphabet. L'univers de Kleene A* = {ε, a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, aab, aac, aba....} est l'ensemble de tous les mots composés de caractère de l'alphabet A auquel on a ajouté le mot vide noté ε. Le signe unaire * désigne l'opération unaire de Kleene, la cloture par concatenation avec ajout de l'élément neutre ε, c'est à dire l'ensemble de tous les éléments atteinds par le procédé de construction que constitue la concatenation de mots, au quel on ajoute le mot vide. Le mot vide n'est constitué par aucun caractère. C'est une séquence vide représentée par le symbôle ε. Noter alors que ε est un mot et n'est pas un caractère, il ne fait pas parti de l'alphabet A. Un langage L d'alphabet A est un sous ensemble de l'univers de Kleene A*. La seul contrainte que nous avons sur l'alphabet A est qu'il soit fini, et sur le langage L, qu'il soit dénombrable.

On peut coder les n caractères de l'alphabet A par les entiers de 1 à n, et coder les mots de A* par un développement en base n qui respecte l'ordre de complexité usuel :

L'univers de Kleen A* peut être énuméré en respectant l'ordre de complexité usuel. Le mot vide ε a un code égale à zéro. Le mot d'un seul caractère a un code égale à celui du caractère. Si l'alphabet est composé de 3 cararctères a,b,c, codés comme suivant : a=1, b=2, c=3, le code d'un mot correspond alors à un développement en base 3. Le mot abc possède comme code 1 + 2*3 + 3*32 = 34, et le mot aaaa possède comme code 1*30 + 1*31 + 1*32 + 1*33 = 40. Ce codage respecte l'ordre des mots selon leur taille, c'est à dire respecte l'ordre de complexité usuel. Et ce codage est une bijection entre A* et N. Autrement dit il constitue un algorithme de compression totale, on ne peut pas comprimer d'avantage.

6) Les grammaires

Une grammaire est un moteur énumérant les mots d'un langage. La grammaire se présente sous forme d'un quadruplet comprenant un alphabet A, une extension W, un ensemble M de mots appartenant à (AW)*, et un ensemble G de règles appartenant à ((AW)* - {ε})X(AW)*. Considérons par exemple la grammaire suivante :

(A,W,M,G) = ({a,b}, {B,C}, {C,aB}, {aB-->Cb, C-->aC|BB|ε})

L'alphabet est A={a,b}, l'ensemble des caractères non terminaux est W={B,C}, l'ensemble des mots initiaux est M={C,aB}, et l'ensemble des règles est G={aB-->Cb, C-->aC|BB|ε}. La grammaire est un processus de construction de mots. A partir de quelques mots initiaux, ici C et aB, la grammaire engendre deux langages ; un langage étendu d'alphabet A⋃W c'est à dire contenant tous les mots terminaux et tous les mots non terminaux, et un langage d'alphabet A c'est à dire contenant seulement les mots terminaux.

Par défaut, l'ordre des productions d'une règle appliquée à un mot correspond à l'ordre de rencontre de chaque occurence dans le mot de gauche à droite, en ne remplaçant à chaque fois qu'une seul occurence. Pour remplacer 2 occurences il faudra appliquer successivement 2 fois la règle.

Les grammaires sont des moteurs énumérant les mots d'un langage. Et il existe un ordre d'énumération correspondant à la complexité des démonstrations. La liste des productions de niveau 0 contient tous les mots initiaux. Le moteur applique toutes les règles à tous les mots de la liste de production, et produit ainsi touts les mots démontrables par l'application d'une règle une seul fois. Ces mots sont en nombre fini. Si le mot n'a pas déja été produit ou présent, il est ajouté à une nouvelle liste de production dite de niveau 1. Si une règle produit un mot déja existant dans une des liste de production, celui-ci n'est pas ajouté, de tel sorte que l'union des listes de production regroupent toujours des mots distincts. Puis une fois toutes les règles appliquées sur tous les mots d'une liste de production de niveau n-1, une liste de production de niveau n s'est alors consruite. Le moteur recommence en appliquant toutes les règles sur tous les mots de la liste de niveau n pour produire une liste de niveau n+1, et ceci indéfiniment. En procédant ainsi on énumère tous les mots du langage de la grammaire avec pour chacun leurs complexité démonstrative minimale. Reprenons notre exemple. La grammaire ({a,b},{U,V},{C,aB}, {aB-->Cb, C-->aC|BB|ε}) va produire les listes suivantes :

{C, aB}0, {Cb, aC, BB, ε}1, {aCb, BBb, b}2, {aaCb, aBBb, ab}3, {CbBb, aaaCb, aaBBb, aab}4...

qui réunie correspond au langage étendu engendré par la grammaire :

{C, aB, Cb, aC, BB, ε, aCb, BBb, b, aaCb, aBBb, ab, CbBb, aaaCb, aaBBb, aab...}.

Et le langage est obtenue en retirant les mots non terminaux :

{ε, b, ab, aab...}.

7) Les machines de Turing

Un langage est dit énumérable si et seulement si il est énuméré par une machine du Turing M, c'est à dire que la machine appliquer à tous les entiers va produire tous les mots du langage {M(0), M(1), M(2)...}. Il est également énumérable si et seulement si il est accepté par une machine de Turing, c'est à dire qu'appliqué à un mot du langage, la machine s'arrète au bout d'un temps fini et retourne true, et appliqué à un mot hors du langage, la machine soit retourne false ou bien soit ne s'arrète jamais ce qui correspond à l'infini de Turing. Voir Les fondements de l'informatique, et l'énumérabilité, La calculabilité des ensembles.

On peut en effet construire une machine K qui accepte le langage L à partir d'une machine M qui énumère le langage L : La machine K appliqué à un mot m va utiliser la machine M pour produire tous les mots du langage et comparer à chaque fois avec le mot m, et si l'égalité se produit, se terminer en retournant true. De même on peut construire une machine M qui énumère le langage L d'alphabet A à partir d'une machine K qui accepte le langage L : La machine M énumère les mots m du langage libre A* et pour chaque m produit, elle crée un processus de calcul parallèle qui applique la machine K sur ce mot m. Dès qu'un m est accepté, la machine retourne m en continuant en parallèle sa recherche pour les autres mots m.

Si on retir algorithme de calcul parallèle, on obtient une machine qui semi-énumère le langage, c'est à dire que la machine appliquer à tous les entiers va produire tous les mots du langage, mais pour certain entiers le calcul ne s'arrètera jamais et donnera l'infini de Turing. La différence qui existe entre la semi-énumération et l'énumération tient en ce que le calcul en cours de route peut ne pas s'arréter et donner l'infini de Turing. Pour procéder à l'énumération, il faut alors ne pas attendre la réponse et effectuer les calculs suivants en paralèlles, ce qui est procéduralement possible. Donc du point de vue de la calculabilité, la semi-énumérabilité est équivalente à l'énumérabilité.

A chaque grammaire correspond une machine de Turing énumérant son langage, et il existe une machine de Turing acceptant son langage.

Les grammaires comme les programmes sont décrits avec le même langage que celui des données mais enrichie de quelques méta-opérateurs tel que ε, |, -->.... Il existe des types de machines programmabes plus simples que la machine de Turing tel que l'automate fini ainsi que l'automate à pile. La machine de Turing dans sa généralité correspond à l'automate à ruban ou à l'automate à deux piles. Lorsque les grammaires sont plus simples elles engendrent des langages plus simples capables d'être acceptés par des machines programmables plus simples.

8) Les 4 types de grammaires (Hiérarchie de Chomsky)

La hiérarchie de Chomsky est une classification des langages formels et des grammaires formelles, découverte par Noam Chomsky en 1956. Noam Chomsky est linguiste et philosophe américain, né en 1928 à Philadelphie en Pennsylvanie.

On classifie les grammaires en 4 types selon des restrictions posées sur la formes des règles utilisées, et qui correspondent à 4 types de machines pogrammables pouvant accepter le langage engendré par la grammaire.

Type de grammaire
Type de machine programmable

Type 0 : Grammaire générale
Pas de restriction sur les règles.

Automate à ruban
C'est une machine de Turing

Type 1 : Grammaire sensible au contexte
Les règles sont de la forme suivante :

u --> v

u et v désignent deux mots terminaux ou non,
de longeur |u| ≤ |v|

Automate à ruban à borne linéaire
A borne linéaire signifie que la complexité en ressource de ruban est linéaire, c'est à dire qu'il existe deux nombres a et b tel que pour tout mots d'entré w occupant |w| cases sur le ruban, la taille de rubans utilisé lors du calcul, l'excursion maximum de la tête de lecture de la machine de Turing, ne dépasse pas a*|w| + b cases.

Type 2 : Grammaire hors-contexte
Les règles sont de la forme suivante :

A --> u

A désigne un caractère non terminal, et u désigne un mot terminal ou non.

Langage hors-contexte : Les caractères terminaux peuvent être substitué par un mot terminal ou non, indépendament des caractères autours. Grace à cela, on peut représenter une dérivation en faisant abstraction de l'ordre d'application des règles de production, à l'aide d'un arbre de dérivation.

Automate à pile
Automate possédant une pile non bornée.

Type 3 : Grammaire régulière
La grammaire régulière droite : Les règles sont de la forme suivante :

A-->wB
A-->w

La grammaire régulière gauche : Les règles sont de la forme suivante :

A-->Bw
A-->w

A et B désignent deux caractères non terminaux, et w désigne un mot terminal.

Langage régulier : construit à partire des langages singletons contenant tous les mots composés d'un seul caractère de l'alphabet et contenant le mot vide, et en utilisant les 3 opérations que sont l'union "|", la concatenation notée par absence de symbole, et la fermeture de Kleene "*".

Automate fini

Si nous désignons par type n, l'ensembles des langages engendrés par des grammaires de type n, alors nous pouvons écrire la suite d'inclusions strictes suivantes :

type 3 < type 2 < type 1 < type 0

9) Les automates finis

A chaque grammaire régulière correspond canoniquement un automate fini qui accepte le langage engendré par la grammaire. Voici par exemple une grammaire régulière droite utilisant l'alphabet A = {a,b,c} et les caractères non terminaux {B,C}, et son automate correspondant :

Grammaire
Automate
B --> abB | aC
C --> cB | cC | baB | ε

Les états de l'automate sont les caractères non terminaux de la grammaire, B et C. Les états finaux coloriés en gris sont ceux pour lesquels il existe une règle produisant le mot vide.

On suppose un mot initial quelconque tel que aBabCc. La grammaire appliqué à ce mot va engendrer un langage. L'automate générique qui doit reconnaitre ce langage se décompose en plusieurs automates. Il commence par reconnaitre a puis B puis ab puis C puis c. La reconnaissance de B et de C correspond à l'automate de la grammaire en partant de l'état initiale correspondant B ou C. Une difficulté provient du fait que lors d'une étape plusieur changements d'état sont possibles. L'automate est non déterministe. Chaque possibilité d'avancement de l'automate ouvre une nouvelle voie qui doit être analysé, et le nombre de possibilités à explorer se multiplie à chaque fois et devient vite trés grand.

Il existe un moyen de contourner cette difficultée et d'amméliorer considérablement l'efficacité. Cela consiste à rendre l'automate déterministe, c'est à dire qu'à chaque lecture d'un caractère l'automate n'ait qu'un seul choix de changement d'état possible.

10) Compilation des grammaires régulières

La grammaire constitue le programme de l'automate. Une grammaire régulière peut être compilée afin que son automate soit déterministe.

Reprenons notre exemple de grammaire :

B --> abB | aC
C --> cB | cC | baB | ε

A chaque étape, l'automate se trouve dans un état B ou C, puis lit le caractère suivant. Il peut alors emprunter l'arrète qui porte le caractère en label. On scinde les arrètes ayant un label de plusieurs lettres consécutives en créant autant de nouveaux états intermédiaires désignés par des lettres supplémentaires (non terminales) :

B --> aD | aC
C --> cB | cC | bE | ε
D --> bB
E --> aB

Pour chaque règle, lorsqu'il existe plusieurs choix possibles de changement d'état, on crée un nouvel état que l'on nomme par la réunion des états atteignables. Le comportement de ce nouvel état cummule les possibilités de changement d'état de chacun de ses états membres :

B --> a{C,D}
C --> c{B,C} | bE | ε
D --> bB
E --> aB
{C,D} --> c{B,C} | bE | ε | bB
{B,C} --> a{C,D} | c{B,C} | bE | ε

Puis on répète l'opération sur les 2 nouveaux états créés {C,D} et {B,C} :

B --> a{C,D}
C --> c{B,C} | bE | ε
D --> bB
E --> aB
{C,D} --> c{B,C} | b{B,E} | ε
{B,C} --> a{C,D} | c{B,C} | bE | ε
{B,E} --> a{C,D} | aB

Puis on répète l'opération sur le nouvel état créé {B,E} :

B --> a{C,D}
C --> c{B,C} | bE | ε
D --> bB
E --> aB
{C,D} --> c{B,C} | b{B,E} | ε
{B,C} --> a{C,D} | c{B,C} | bE | ε
{B,E} --> a{B,C,D}
{B,C,D} --> a{C,D} | c{B,C} | bE | ε | bB

Puis on répète l'opération sur le nouvel état créé {B,C,D} :

B --> a{C,D}
C --> c{B,C} | bE | ε
D --> bB
E --> aB
{C,D} --> c{B,C} | b{B,E} | ε
{B,C} --> a{C,D} | c{B,C} | bE | ε
{B,E} --> a{B,C,D}
{B,C,D} --> a{C,D} | c{B,C} | b{B,E} | ε

On obtient ainsi un automate déterministe :

Grammaire compilée
Automate déterministe
B --> a{C,D}
C --> c{B,C} | bE | ε
D --> bB
E --> aB
{C,D} --> c{B,C} | b{B,E} | ε
{B,C} --> a{C,D} | c{B,C} | bE | ε
{B,E} --> a{B,C,D}
{B,C,D} --> a{C,D} | c{B,C} | b{B,E} | ε

La reconnaissance d'un mot d'un langage régulier est donc de complexité linéaire. A chaque étape l'automate lit le caractère suivant dans le mot, et il y a au plus qu'une seul possibilité de changement d'état. Si il n'y a pas de possibilié l'automate s'arrête en retournant "false", sinon il applique l'unique possibilité, effectue le changement d'état et lit le caractère suivant. Lorsqu'il n'y a plus de caractère à lire, selon qu'il se trouve sur un état final ou non, il s'arrête et retourne respectivement "true"ou "false".

Cette compilation de la grammaire permet de la rendre déterministe.

L'état initial parmi B, C, D, E, {B,C}, {C,D}, {B,E}, {B,C,D} doit être choisi avant de lancer l'exécution de l'automate.

11) Programmation des automates finis déterministes

Puisqu'une grammaire régulière déterministe, telle qu'elle est écrite, détermine exactement un algorithme, nous pouvons formaliser un langage de programmation de telle sorte que l'algorithme se transcrive à l'identique de la grammaire.

On reprend notre exemple de grammaire : On code les caractères par 1,2...,n  et on ajoute un caractère, le caractère de fin de mot ε que l'on code par 0. Les états B, C, D, E, {B,C}, {C,D}, {B,E}, {B,C,D} sont codés de 0 à m-1, les codes m et m+1 sont réservés pour arrêter le programme et retourner respectivement false ou true.

Le mot vide et le caractère de fin de mot sont désigner par le même symbole ε, mais ils diffèrent conceptuellement, le mot vide est l'élément neutre de l'opération de concaténation, alors que le caractère de fin de mot relève du protocole de bas niveau. Selon ce protocole que nous mettons en place, le caractère de fin de mot ε apparait obligatoirement après le dernier caractère de chaque mot, ou comme premier caractère du mot vide. le mot vide est utilisé pour désigner les transitions sans lecture de caractère faites par un automate non-déterministe. Le caractère de fin de mot est utilisé pour désigner les transitions faites par un automate déterministe sur l'absence de caractère à lire qui arrête l'automate en retournant "true" ou "false" selon que son état est final ou non.

On considère le sous-programme de base qui consiste à lire séquenciellement le caractère suivant et à retourner son code. En fin de mot il lit le caractère de fin de mot ε de code 0.

Les caractère jouent à la fois un rôle passif, de constituant des mots, et un rôle actif comme composant du programme. On regroupe ainsi le coté objectuel et le coté dynamique dans la même notation. La grammaire est mémorisée dans un tableau G[.,.] à 2 dimensions. Le premier indice varie de 0 à m-1 et correspond aux états possibles B, C, D, E, {B,C}, {C,D}, {B,E}, {B,C,D}, les deux valeurs suivantes F = m et V =m+1 correspondent aux arrêts du programme avec une valeur de retour respectivement false et true. Le second incice varie de 0 à n et correspond aux lettres de l'alphabet, la valeur 0 correspond au caractère fin de mots ε :

G = [B, C, D, E, {B,C}, {C,D}, {B,E}, {B,C,D}]

B = [F,{C,D},F,F]
C = [T,F,E,{B,C}]
D = [F,F,B,F]
E = [F,B,F,F]
{C,D} = [T,F,{B,E},{B,C}]
{B,C} = [T,{C,D},E,{B,C}]
{B,E} = [F,{B,C,D},F,F]
{B,C,D} = [T,{C,D},{B,E},{B,C}]

Ainsi la grammaire est mémorisée dans un tableau de (n+1)*m cases contenant des entiers compris entre 0 et m+1, où n est le nombre de lettres de l'alphabet, et m le nombre d'états de l'automate.

Le programme prends, comme entré, l'état initial X et le mot Y à tester. X et Y sont des variables globales du programme. Le programme consiste à répéter indéfiniment la lecture du caractère suivant, et a effectuer le changement d'état correspondant :

Algorithme
        Répéter indéfiniment
        |     Lire le caractère suivant : c=lit(Y)
        |     changer d'état en conséquence : X=G[X,c]
        |     si X = F retourne false
        |     si X = T retourne true
        Fin

Le mot est mémorisé dans une file Y. L'instruction c=lit(Y) retire le premier caractère de la file Y et le met dans la variable c. Si la file est vide, l'instruction c=lit(Y) met 0 dans c.

L'instruction X=G[X,c] change l'état X de l'auromate selon ; la grammaire G, l'état présent X et le caractère lu c.

12) La construction des langages réguliers

On définie les langages suivants : Les langages singleton ne contenant qu'un mot égale à un caractère et le langage singleton contenant le mot vide {a}, {b}, {c}, {ε}. Par abus de notation on les note aussi par a, b, c, ε.

On définie dans l'ensemble des langages les opérateurs suivants :

  1. L'opérateur binaire union, noté "|", qui consiste à fair la réunion de deux langages.
  2. L'opérateur binaire concaténation noté par absence de symbôle. La concaténation de deux langage est l'ensemble des mots composée d'un mot du premier langage et d'un mot du second langage.
  3. L'opérateur unaire gauche de Kleene, noté "*" , qui consiste à prendre la femeture de Kleene du langage, c'est l'ensemble des mots composés d'un nombre quelconque de mots du langage.

L'ensemble des langages réguliers R d'alphabet {a,b,c} est engendré par {Ø, a, b, c, ε, (x,y)-->x|y, (x,y)-->xy, x-->x*}

R = < Ø, a, b, c, ε (x,y)-->x|y, (x,y)-->xy, x-->x* >

On attribue habituellement une priorité syntaxique de la plus élevé à la plus basse suivantes : cloture de Kleene, concatenation, union.

Pierre Wolpert, Introduction à la calculabilité, Dunod, Paris 2006
Site web, université de Brest http://fastnet.univ-brest.fr/~gire/cours