séquence 209_4

Démonstration :

Posons d'abord deux lemmes importants :

Lemme 1

(1) ∅, (2) {ε} et (3) {a} avec a ∈ A sont des langages linéaires droits.

Démonstration du lemme 1

Lemme 2

Si L₁ et L₂ sont linéaires droits, alors (1) L₁ ∪ L₂, (2) L₁L₂ et (3) L₁* sont linéaires droits.

Démonstration du lemme 2

Nous pouvons alors démontrer notre théorème :

Si un langage est rationnel alors il est linéaire droit (par récurence sur le nombre d'application des opérations de base).
- Le lemme 1 nous indique que la relation est vraie pour les langages les plus simples, c'est-à-dire pour ∅, {ε} et {a}.
- Supposons la relation vraie après n applications des opérateurs. Soit L le langage obtenu, L est supposé rationnel et linéaire droit. En considérant la définition des langages rationnels et le lemme 2, on en déduit que L'=L ∪ ∅ ou L'=L ∪ ε ou L'=L ∪ {x} est rationnel et linéaire droit.
Si un langage est linéaire droit alors il est rationnel. Soit G={V_T, V_N, S, R} une grammaire linéaire droite avec V_N={A₁, ...,A_N}. On va essayer de construire un système d'équations linéaires associées à G de la façon suivante : les inconnues sont les A_i, l'équation qui correspond à A_i est A_i=a_i0 + a_i1A₁ + ... + a_inA_n où :
- a_i0 = w₁ + w₂ +... + w_n, avec A_i → w₁ | ... | w_n et w_j, j=1,...,n comme membre droit.
- a_ij, j>0 est x₁, x₂, ..., x_n où A_i → x₁A_j | ... | x_nA_j sont toutes les productions avec A_i à gauche et A_j à droite.
  
  On obtient donc un système d'équations rationnelles. Si n=0 alors a_ij=∅. L(G)=f(S) où f(S) est la solution du système s.

Remarque : De cette démonstration et de ce que l'on a vu à propos du passage d'une suite de définitions rationnelles à une expression rationnelle, il est possible de déduire une méthode pour trouver une expression rationnelle (et donc un langage rationnel) à partir d'une grammaire linéaire droite. Ce passage d'une grammaire linéaire droite G=(A, Q, S, R) à un système d'expressions rationnelles SR s'effectue par une conversion des règles : A → rA | sB | t ∈ R ⇔ X = rX + sY + t ∈ SR. L'expression du langage est l'expression de la variable du système associée à S.

Par conséquent, les expressions rationnelles sont aussi appelées "expression régulières" (plus souvent utilisé dans la littérature anglo-saxonne). De même, les langages rationnels sont aussi appelés les langages réguliers.

Exercices et tests :

Exercice 6.1. Soit les deux grammaires suivantes :

Gex6 = {{a,b,;},{S,A},S,R1} avec R1 tel que :
S → A | A ; S
A → aAb | ab
Gex7 = {{a,b,c},{S,A,B,C},S,R2} avec R2 tel que :
S → aAbBcC | ε
aA → aaA | aa
bB → bbB | bb
C → cC | c

Donner le type de ces grammaires.
Décrire le langage engendré par les grammaires Gex6 et Gex7.
Proposer si possible les grammaires linéaires (de type 3) équivalentes ainsi que les expressions rationnelles décrivant ces langages.

Exercice 6.2. Proposer les grammaires, avec les règles sous forme BNF, permettant d'engendrer les langages suivants :

Le langage L1 dont les mots sont des suites de symboles pris dans {a,b,c} séparés par le symbole # (qui ne peut donc pas être le dernier caractère).
Ex. : "abab#cbb#a" et "abccc" sont deux mots de ce langage.
Le langage L2 dont les mots sont des règles possibles d'une grammaire linéaire droite G_rd définie par le quadruplet {{a,b,c},{S,A,B,C},S,R} avec R ⊆ L2.
Ex. : "A → abA | c", "B → b" et "S → bA | ε" sont trois mots de ce langage.

Exercice 6.3. Donner une grammaire pour les langages suivants. Préciser son type.

A={a,b,c} et L1={w ∈ A* | w=a^mbⁿc^p; m,n,p > 0}

A={a,b,c} et L2={w ∈ A* | w=a^pb^qc^r; p,q,r > 0; (p=q ou q=r)}

A={a,b} et L3={w ∈ A* | w=a^pb^q; p,q ≥ 0; p ≠ q}

A={a,b,c} et L4={w ∈ A* | w=a^pb^qc^r; p,q > 0; r ≥ 0; p+q ≥ r}

Exercice 6.4. Soit le vocabulaire V={a,+,=}. Donner une grammaire hors-contexte pour le langage L dont chaque mot représente une addition correcte de deux suites de symboles a. Par exemple : "aa+aaa=aaaaa".

6. Cas des langages rationnels