Théorie des langages

aabbaabbaabb.

Propriétés : La concaténation est associative mais non commutative. La concaténation est une

loi de composition interne de A∗ et (cid:15) est son élément neutre. Par conséquent, (A∗, .) est un monoïde.

Exercice : Soit l’alphabet A = {a, b}.

1. Etant donnés les mots u = aa et v = bab, écrire les mots uv, (uv)2 et u3v.

2. Enoncer tous les mots de longueur 2 définis sur A.

3. Soient les ensembles

E1 = {u.v/u ∈ A+, v ∈ A+}

E2 = {u.v/u ∈ A+, v ∈ A∗}

E3 = {u.v/u ∈ A∗, v ∈ A∗}

A quoi correspondent ces ensembles ?

Correction :

1. uv = aabab, (uv)2 = aababaabab et u3v = aaaaaabab.

2. Mots de longueur 2 = {aa, ab, ba, bb}

3. E1 = {u ∈ A∗/|u| ≥ 2} = ensemble des mots d’au moins 2 symboles

E2 = A+

E3 = A∗

Définition (Préfixe, suffixe et facteur) : Soient deux mots u et v définis sur un alphabet A.

• u est un préfixe de v si et seulement si ∃w ∈ A∗ tel que uw = v ;
• u est un suffixe de v si et seulement si ∃w ∈ A∗ tel que wu = v ;
• u est un facteur de v si et seulement si ∃w1 ∈ A∗, ∃w2 ∈ A∗ tels que w1uw2 = v.

4

Exercice : Montrer que les relations “ètre-préfixe-de”, “être-suffixe-de” et “être-facteur-de” sont

des relations d’ordre partiel sur A∗, c’est-à-dire qu’elles sont transitives, antisymétriques et ré-

flexives.

Correction pour “être-préfixe-de” :

– Transitivité : soient trois mots u, v et w définis sur A tels que u est un préfixe de v et v est un

préfixe de w. Montrons que u est un préfixe de w :

– u est un préfixe de v ⇒ ∃u(cid:48) ∈ A∗ tel que uu(cid:48) = v

– v est un préfixe de w ⇒ ∃v(cid:48) ∈ A∗ tel que vv(cid:48) = w

Par conséquent, w = uu(cid:48)v(cid:48) et donc u est un préfixe de w.

– Antisymétrie : soient deux mots u et v définis sur A tels que u est un préfixe de v et v est un

préfixe de u. Montrons que u est égal à v :

– u est un préfixe de v ⇒ ∃u(cid:48) ∈ A∗ tel que uu(cid:48) = v

– v est un préfixe de u ⇒ ∃v(cid:48) ∈ A∗ tel que vv(cid:48) = u

Par conséquent, uu(cid:48)v(cid:48) = u et donc u(cid:48) = (cid:15) et v(cid:48) = (cid:15) et u = v.

– Réflexivité : pour tout mot u défini sur A, on a u est un préfixe de u car u = u.(cid:15) et (cid:15) ∈ A∗.

Exercice : On considère les ensembles de mots E1 et E2 définis sur l’alphabet A = {0, 1, 2} de

la façon suivante :

• E1 est l’ensemble des mots de longueur paire,
• E2 est l’ensemble des mots comportant autant de 0 que de 1 et autant de 1 que de 2.

Définir de façon plus formelle ces deux ensembles et déterminer pour chacun d’eux si la concaté-

nation est une loi interne et si le mot vide en est un élément.

Correction :

– E1 = {u ∈ A∗/∃l ∈ N, |u| = 2l}

– La concaténation est une loi interne pour E1 car pour tout couple de mots (u, v) ∈ E2

1 ,

|uv| = |u| + |v| = 2l + 2l(cid:48) = 2(l + l(cid:48)).

– (cid:15) ∈ E1 car |(cid:15)| = 2 ∗ 0

– Pour définir formellement l’ensemble E2, il est nécessaire d’introduire la notion de permutations

d’un mot. L’ensemble des permutations d’un mot u est l’ensemble de tous les mots que l’on

peut former en ré-arrangeant les symboles qui composent u de toutes les façons possibles. Plus

formellement, on peut définir cet ensemble récursivement de la façon suivante :

– permutations((cid:15)) = {(cid:15)}

– pour tout mot u ∈ A+ commençant par un symbole a ∈ A et se terminant par une suite de

symboles u(cid:48) ∈ A∗ (tel que u = a.u(cid:48)), permutations(u) = {v(cid:48).a.v(cid:48)(cid:48)/v(cid:48)v(cid:48)(cid:48) ∈ permutations(u(cid:48))}

On peut alors définir E2 de la façon suivante : E2 = {u/∃n ∈ N, u ∈ permutations(0n1n2n)}.

La concaténation est une loi interne pour E2 et (cid:15) ∈ E2.

2.2 Langages

Définition (Langage) : Un langage, défini sur un alphabet A, est un ensemble de mots définis

sur A. Autrement dit, un langage est un sous-ensemble de A∗.

Deux langages particuliers sont indépendants de l’alphabet A :

• le langage vide (L = ∅),
• le langage contenant le seul mot vide (L = {(cid:15)}).

5

Opérations ensemblistes définies sur les langages : Soient deux langages L1 et L2 respec-

tivement définis sur les alphabets A1 et A2 :

– L’union de L1 et L2 est le langage défini sur A1 ∪ A2 contenant tous les mots qui sont soit

contenus dans L1, soit contenus dans L2 :

L1 ∪ L2 = {u/u ∈ L1 ou u ∈ L2}

– L’intersection de L1 et L2 est le langage défini sur A1 ∩ A2 contenant tous les mots qui sont

contenus à la fois dans L1 et dans L2 :

L1 ∩ L2 = {u/u ∈ L1 et u ∈ L2}

– Le complément de L1 est le langage défini sur A1 contenant tous les mots qui ne sont pas dans

L1 :

C(L1) = {u/u ∈ A∗

1 et u (cid:54)∈ L1}

– La différence de L1 et L2 est le langage défini sur A1 contenant tous les mots de L1 qui ne sont

pas dans L2 :

L1 − L2 = {u/u ∈ L1 et u (cid:54)∈ L2}

Définition (Produit de deux langages) : Le produit ou concaténation de deux langages L1

et L2, respectivement définis sur les alphabets A1 et A2, est le langage défini sur A1 ∪A2 contenant

tous les mots formés d’un mot de L1 suivi d’un mot de L2 :

Le produit de langages est associatif, mais non commutatif.

L1.L2 = {uv/u ∈ L1 et v ∈ L2}

Considérons par exemple les deux langages L1 = {00, 11} et L2 = {0, 1, 01} définis sur

{0, 1}.

L1.L2 = {000, 001, 0001, 110, 111, 1101}

Définition (Puissances d’un langage) : Les puissances successives d’un langage L sont défi-

nies récursivement par

• L0 = {(cid:15)},
• Ln = L.Ln−1 pour n ≥ 1.

Par exemple, si L1 = {00, 11}, alors L2

1 = {0000, 0011, 1100, 1111}

Définition (Fermeture itérative d’un langage) : La fermeture itérative d’un langage L (ou

fermeture de Kleene ou itéré de L) est l’ensemble des mots formés par une concaténation de mots

de L :

L∗ = {u/∃k ≥ 0 et u1, ..., uk ∈ L tels que u = u1u2...uk}

Autrement dit, L∗ = ∪∞

De même, on définit L+ = ∪∞

i=0Li

i=1Li

6

Description d’un langage :

– Un langage fini peut être décrit par l’énumération des mots qui le composent.

– Certains langages infinis peuvent être décrits par l’application d’opérations à des langages plus

simples.

– Certains langages infinis peuvent être décrits par un ensemble de règles appelé grammaire (voir

la section suivante).

– Enfin, certains langages infinis ne peuvent pas être décrits, ni par l’application d’opérations,

ni par un ensemble de règles. On parle alors de langage indécidable. On peut noter que si un

langage est indécidable, alors il n’existe pas d’algorithme permettant de déterminer si un mot

donné appartient à ce langage. On dit alors que le problème est indécidable. Par exemple, le

langage des programmes C++ qui “terminent" (qui ne bouclent pas indéfiniment) ne peut être

décrit par des règles formelles : ce langage est indécidable et le problème consistant à déterminer

si un programme C++ donné termine est un problème indécidable, pour lequel il n’existe pas

d’algorithme (ce problème est plus connu sous le nom de “problème de l’arrêt de la machine de

Turing").

Exercice : Sur l’alphabet A = {0, 1}, on considère les langages L1 et L2 définis par

L1 = {01n/n ∈ N}

L2 = {0n1/n ∈ N}

Définir les langages L1L2, L1 ∩ L2 et L2

1.

Correction :

– L1L2 = {01n0m1/n ∈ N, m ∈ N}

– L1 ∩ L2 = {01}

– L2

1 = {01n01m/n ∈ N, m ∈ N}

Exercice : Sur l’alphabet A = {a, b}, on considère le langage L1 des mots formés de n fois la

lettre a suivi de n fois la lettre b, et le langage L2 des mots comportant autant de a que de b.

• Définir formellement ces deux langages.
• Que sont les langages suivants : L1 ∪ L2, L1 ∩ L2, L2

1 et L∗

• Que peut-on dire de L∗

2 par rapport à L1 et L2 ?

1, L2

2 ?

Correction :

– L1 = {anbn/n ∈ N}

– L2 = {u/∃n ∈ N, u ∈ permutations(anbn)}

– L1 ∪ L2 = L2 et L1 ∩ L2 = L1 car L1 ⊂ L2

1 = {anbnambm/n ∈ N, m ∈ N}

– L2

– L2

2 = L2

– L1 ⊂ L∗

– L∗

2 = L2

1 ⊂ L2

7

2.3 Grammaires

Un langage peut être décrit par un certain nombre de règles. Cette vue du concept de langage a son

origine dans des essais de formalisation du langage naturel. Le but était de donner une description

précise des règles permettant de construire les phrases correctes d’une langue.

Prenons par exemple le sous-ensemble suivant de la grammaire francaise :

– le vocabulaire est défini par l’ensemble :

T = { le, la, fille, jouet, regarde }

– les catégories syntaxiques sont :

la phrase, notée PH

le groupe nominal, noté GN

le verbe, noté V

le déterminant, noté D

le nom, noté N

– les règles permettant de combiner des éléments du vocabulaire et des catégories syntaxiques pour

construire des catégories syntaxiques sont les suivantes :

PH → GN V GN

GN → D N

D → le

D → la

N → fille

N → jouet

V → regarde

où le symbole → est une abréviation de “peut être composé de”.

– la catégorie syntaxique de départ est la phrase PH.

La phrase “la fille regarde le jouet” est une phrase correcte pour la grammaire envisagée, comme

le montre l’analyse suivante :

PH ⇒ GN V GN ⇒ D N V GN ⇒ la N V GN ⇒ la fille V GN ⇒ la fille regarde GN

⇒ la fille regarde D N ⇒ la fille regarde le N ⇒ la fille regarde le jouet

où le symbole ⇒ est une abréviation de “se dérive en”.

Notons que :

1. La grammaire considérée ne prend pas en compte certains aspects du francais, comme les

accords de genre.

2. “le jouet regarde la fille” est aussi une phrase syntaxiquement correcte, mais dont la séman-

tique n’est pas assurée.

La fonction d’une grammaire telle que celle que nous venons de donner est double : la grammaire

indique comment construire des phrases appartenant au langage (fonctionnement en production) ;

la grammaire permet également de décider si une phrase donnée appartient ou non au langage

(fonctionnement en reconnaissance).

Dans le cas d’un langage de programmation, on se sert d’une grammaire pour décrire les entités

du langage. La forme de Backus-Naur (BNF), souvent utilisée pour décrire la syntaxe des langages

de programmation, est en fait une grammaire au sens où nous allons le définir.

8

Définition (Grammaire) : Une grammaire est un quadruplet G = (T, N, S, R) tel que

– T est le vocabulaire terminal, c’est-à-dire l’alphabet sur lequel est défini le langage.

– N est le vocabulaire non terminal, c’est-à-dire l’ensemble des symboles qui n’apparaissent pas

dans les mots générés, mais qui sont utilisés au cours de la génération. Un symbole non terminal

désigne une “catégorie syntaxique”.

– R est un ensemble de règles dites de réécriture ou de production de la forme :

u1 → u2, avec u1 ∈ (N ∪ T )+ et u2 ∈ (N ∪ T )∗

La signification intuitive de ces règles est que la suite non vide de symboles terminaux ou non

terminaux u1 peut être remplacée par la suite éventuellement vide de symboles terminaux ou

non terminaux u2.

– S ∈ N est le symbole de départ ou axiome. C’est à partir de ce symbole non terminal que l’on

commencera la génération de mots au moyen des règles de la grammaire.

Terminologie :

– une suite de symboles terminaux et non terminaux (un élément de (N ∪ T )∗) est appelée une

forme.

– une règle u1 → u telle que u ∈ T ∗ est appelée une règle terminale.

Notation : Lorsque plusieurs règles de grammaire ont une même forme en partie gauche, on

pourra “factoriser” ces différentes règles en séparant les parties droites par des traits verticaux. Par

exemple, l’ensemble de règles S → ab, S → aSb, S → c pourra s’écrire S → ab | aSb | c.

Le langage défini, ou généré, par une grammaire est l’ensemble des mots qui peuvent être obtenus

à partir du symbole de départ par application des règles de la grammaire. Plus formellement, on

introduit les notions de dérivation entre formes, d’abord en une étape, ensuite en plusieurs étapes.

Enfin, on définit le langage généré par une grammaire comme étant l’ensemble des mots pouvant

être dérivés depuis l’axiome.

Définition (Dérivation en une étape) : Soient une grammaire G = (T, N, S, R), une forme

non vide u ∈ (N ∪ T )+ et une forme éventuellement vide v ∈ (N ∪ T )∗. La grammaire G permet

de dériver v de u en une étape (noté u ⇒ v) si et seulement si :

– u = xu(cid:48)y (u peut être décomposé en x, u(cid:48) et y ; x et y peuvent être vides),

– v = xv(cid:48)y (v peut être décomposé en x, v(cid:48) et y),

– u(cid:48) → v(cid:48) est une règle de R.

Définition (Dérivation en plusieurs étapes) : Une forme v peut être dérivée d’une forme u

en plusieurs étapes :

• u +⇒ v : si v peut être obtenue de u par une succession de 1 ou plusieurs dérivations en une étape,
• u ∗⇒ v : si v peut être obtenue de u par une succession de 0, 1 ou plusieurs dérivations en une

étape.

Définition (Langage généré par une grammaire) : Le langage généré par une grammaire

G = (T, N, S, R) est l’ensemble des mots sur T qui peuvent être dérivés à partir de S :

L(G) = {v ∈ T ∗/S +⇒ v}

9

Remarques :

• Une grammaire définit un seul langage.
• Par contre, un même langage peut être engendré par plusieurs grammaires différentes.

Exercice : On considère la grammaire G = (T, N, P h, R) où

T = { un, une, le, la, enfant, garcon, fille, cerise, haricot, cueille, mange }

N = { P h, Gn, Gv, Df, Dm, N f, N m, V }

R = { P h → Gn Gv

Gn → Df N f | Dm N m

Gv → V Gn

Df → une | la

Dm → un |

le

N f → fille | cerise

N m → enfant | garcon | haricot

V → cueille | mange }

• La phrase “une cerise cueille un enfant” appartient-elle au langage L(G) ?
• Déterminer le nombre de phrases du langage décrit par G.

Correction :

– Pour montrer qu’une phrase appartient au langage, on construit une dérivation de l’axiome P h

jusqu’à la phrase. On souligne à chaque fois le symbole non terminal qui est remplacé par la

dérivation.

P h ⇒ Gn Gv ⇒ Df N f Gv ⇒ Df N f V Gn ⇒ Df N f V Dm N m

⇒ une N f V Dm N m ⇒ une cerise V Dm N m ⇒ une cerise cueille Dm N m

⇒ une cerise cueille un N m ⇒ une cerise cueille un enfant

Notons qu’il existe plusieurs dérivations possibles.

– Partant de l’axiome, on ne peut appliquer qu’une règle, qui dérive « P h » en « Gn Gv », et on

ne peut appliquer qu’une seule règle pour ré-écrire Gv. Ainsi, l’ensemble des phrases que l’on

peut générer à partir de P h est égal à l’ensemble des phrases que l’on peut dériver à partir de

« Gn V Gn ». Chaque groupe nominal Gn peut être ré-écrit soit en « Df N f » soit en « Dm

N m », et comme chaque non terminal Df , N f , Dm, et N m peut se ré-écrire en 2 terminaux

différents, on peut générer 2 ∗ 2 + 2 ∗ 2 = 8 suites de symboles terminaux différentes à partir de

Gn. On peut par ailleurs ré-écrire V en 2 symboles terminaux, de sorte que le nombre total de

phrases différentes que l’on peut générer à partir de P h est égal à 8 ∗ 2 ∗ 8 = 128.

Exercice : On considère la grammaire G = (T, N, S, R) où

b, c }

T = {

N = { S }

R = { S → bS | cc }

Déterminer L(G).

Correction : L(G) = {bncc/n ∈ N}

En effet, partant de l’axiome S, toute dérivation commencera nécessairement par appliquer 0, 1 ou

plusieurs fois la première règle puis se terminera en appliquant la deuxième règle. On représentera

cela en écrivant le schéma de dérivation suivant :

10

n fois (1)

====⇒ bnS

S

(2)

=⇒ bncc

avec n ∈ N

Exercice : On considère la grammaire G = (T, N, S, R) où

0, 1 }

T = {

N = { S }

R = { S → 0S | 1S | 0 }

Déterminer L(G).

Correction : L(G) = {u0/u ∈ {0, 1}∗}

En effet, partant de l’axiome S, toute dérivation commencera nécessairement par appliquer 0, 1 ou

plusieurs fois la première ou la deuxième règle puis se terminera en appliquant la troisième règle.

On représentera cela en écrivant le schéma de dérivation suivant :

n fois (1 ou 2)

=======⇒ uS

S

(3)

=⇒ u0

avec n ∈ N, u ∈ {0, 1}∗ et |u| = n

Exercice : On considère la grammaire G = (T, N, S, R) où

T = { a, b, 0 }

N = { S, U }

R = { S → aSa | bSb | U

U → 0U | (cid:15) }

Déterminer L(G).

Correction : L(G) = {u0mv/u ∈ {a, b}∗, v = inverse(u), m ∈ N}

où inverse(u) est le mot inverse de u, défini récursivement par :

– inverse((cid:15)) = {(cid:15)}

– pour tout mot u ∈ A+ commençant par un symbole a ∈ A et se terminant par une suite de

symboles u(cid:48) ∈ A∗ (tel que u = a.u(cid:48)), inverse(u) = inverse(u(cid:48)).a

En effet, partant de l’axiome S, toute dérivation partant de S suivra nécessairement le schéma

suivant :

n fois (1 ou 2)

=======⇒ uSv

m fois (4)

====⇒ u0mU v

S

avec u ∈ {a, b}∗, v = inverse(u), n ∈ N, |u| = n, m ∈ N

(3)

=⇒ uU v

(5)

=⇒ u0mv

Exercice : Construire une grammaire pour le langage L = {abna/n ∈ N}.

Correction : On définit la grammaire G = (T, N, S, R) où

T = { a, b }

N = { S, U }

R = { S → aU a

U → bU | (cid:15) }

11

Exercice : Construire une grammaire pour le langage L = {02n1n/n ≥ 0}.

Correction : On définit la grammaire G = (T, N, S, R) où

0, 1 }

T = {

N = { S }

R = { S → 00S1 | (cid:15) }

2.4 Types de grammaires

En introduisant des critères plus ou moins restrictifs sur la forme des règles de grammaire, on ob-

tient des classes de grammaires hiérarchisées, ordonnées par inclusion. La classification des gram-

maires, définie en 1957 par Noam CHOMSKY, distingue les quatre classes suivantes :

Type 0 : pas de restriction sur les règles.

Type 1 : grammaires sensibles au contexte ou contextuelles. Les règles de R sont de la forme :

uAv → uwv avec A ∈ N, u, v ∈ (N ∪ T )∗ et w ∈ (N ∪ T )+

Autrement dit, le symbole non terminal A est remplacé par w si on a les contextes u à gauche

et v à droite.

Type 2 : grammaires hors-contexte. Les règles de R sont de la forme

A → w avec A ∈ N et w ∈ (N ∪ T )∗

Autrement dit, le membre de gauche de chaque règle est constitué d’un seul symbole non

terminal.

Type 3 : grammaires régulières

– à droite. Les règles de R sont de la forme

A → aB ou A → a avecA, B ∈ N et a ∈ T

– à gauche. Les règles de R sont de la forme

A → Ba ou A → a avecA, B ∈ N et a ∈ T

Autrement dit, le membre de gauche de chaque règle est constitué d’un seul symbole non

terminal, et le membre de droite est constitué d’un symbole terminal et éventuellement d’un

symbole non terminal. Pour les grammaires régulières à droite, le symbole non terminal doit

toujours se trouver à droite du symbole terminal tandis que pour les grammaires régulières

à gauche il doit se trouver à gauche.

A chaque type de grammaire est associé un type de langage :

– les grammaires de type 3 génèrent les langages réguliers,

– les grammaires de type 2 génèrent les langages hors-contexte,

– les grammaires de type 1 génèrent les langages contextuels,

– les grammaires de type 0 permettent de générer tous les langages “décidables”, autrement dit,

tous les langages qui peuvent être reconnus en un temps fini par une machine. Les langages qui

ne peuvent pas être générés par une grammaire de type 0 sont dits “indécidables”.

12

Ces langages sont ordonnés par inclusion : l’ensemble des langages générés par les grammaires de

type n est strictement inclus dans celui des grammaires de type n − 1 (pour n ∈ {1, 2, 3}).

Enfin, à chaque type de grammaire est associé un type d’automate qui permet de reconnaître

les langages de sa classe (c’est-à-dire de déterminer si un mot donné appartient au langage) : les

langages réguliers sont reconnus par des automates finis, les langages hors-contexte sont reconnus

par des automates à pile, et les autres langages, décrits par des grammaires de type 1 ou 0, sont

reconnus par des machines de Turing. Ainsi, la machine de Turing peut être considérée comme le

modèle de machine le plus puissant qu’il soit, dans la mesure où tout langage (ou plus généralement,

tout problème) qui ne peut pas être traité par une machine de Turing, ne pourra pas être traité

par une autre machine.

Exercice : On considère la grammaire G = (T, N, S, R) où

T = { a, b, c, d }

N = { S, U }

R = { S → aU | c

U → Sb | d }

Donner le type de G et déterminer L(G).

Correction : G est hors-contexte (car la partie gauche de chaque règle est un symbole non terminal).

G n’est pas régulière car la règle (1) est régulière à droite tandis que la règle (3) est régulière à

gauche. Notons qu’il n’existe pas de grammaire régulière permettant de générer L(G).

L(G) = {ancbn, an+1dbn/n ∈ N}

En effet, partant de l’axiome S, toute dérivation partant de S suivra nécessairement un des deux

schémas suivants :

n fois (1 suivie de 3)

==========⇒ anSbn

S

n fois (1 suivie de 3)

==========⇒ anSbn

S

avec n ∈ N

(2)

=⇒ ancbn

(1)

=⇒ anaU bn

(4)

=⇒ anadbn

Exercice : On considère le langage L des mots sur {a, b, c} qui contiennent au moins une fois la

chaine bac. Définir formellement L et construire une grammaire hors-contexte puis une grammaire

régulière décrivant L.

Correction : L = {u.bac.v/u ∈ {a, b, c}∗, v ∈ {a, b, c}∗}

On définit la grammaire hors-contexte G = (T, N, S, R) où

T = { a, b, c }

N = { S, U }

R = { S → U bacU

U → U a | U b | U c | (cid:15) }

et la grammaire régulière à droite G = (T, N, S, R) où

13

T = { a, b, c }

N = { S, U, V, W }

R = { S → aS | bS | cS | bU

U → aV

V → cW | c

W → aW | bW | cW | a | b | c }

ainsi que la grammaire régulière à gauche G = (T, N, S, R) où

T = { a, b, c }

N = { S, U, V, W }

R = { S → Sa | Sb | Sc | U c

U → V a

V → W b | b

W → W a | W b | W c | a | b | c }

Exercice : On considère le langage L des mots sur {0, 1} qui représentent des entiers pairs non

signés en base 2 (les mots de ce langage se terminent tous par 0 et ne commencent pas par 0, sauf

pour l’entier nul). Définir formellement L et construire une grammaire régulière décrivant L.

Correction : L = {0, 1u0/u ∈ {0, 1}∗}

On définit la grammaire régulière à droite G = (T, N, S, R) où

T = { a, b, c }

N = { S, U }

R = { S → 0 | 1U

U → 1U | 0U | 0 }

ainsi que la grammaire régulière à gauche G = (T, N, S, R) où

T = { a, b, c }

N = { S, U }

R = { S → 0 | U 0

U → U 1 | U 0 | 1 }

Exercice : On considère la grammaire G = (T, N, S, R) où

T = { a, b, c }

N = { S, D, E }

R = { S → aSDE | (cid:15)

aD → ab

bE → bc

cD → DE

bD → bb

cE → cc }

– Quel est le type de G ?

– Ecrire la dérivation qui, partant de l’axiome, applique deux fois la première règle et une fois la

seconde, et poursuivre la dérivation jusqu’à obtenir une chaine de terminaux.

14

– En raisonnant par récurrence, déterminer L(G).

Correction :

– G n’est pas hors-contexte car plusieurs règles comportent plusieurs symboles en partie gauche.

G n’est pas contextuelle non plus car dans la règle cD → DE, on ne retrouve pas le contexte

gauche (c) de D en partie droite de la règle. Ainsi, G est de type 0.

– S

(1)

=⇒ aSDE

(5)

=⇒ aabDEE

(1)

=⇒ aaSDEDE

(4)

(6)

=⇒ aabbcE

=⇒ aabbEE

(2)

=⇒ aaDEDE

(7)

=⇒ aabbcc

(3)

=⇒ aabEDE

(4)

=⇒ aabcDE

– L(G) = {anbncn/n ∈ N}.

En effet, toute dérivation partant de S suivra nécessairement le schéma suivant :

n fois (1)

====⇒ anS(DE)n

S

(2)

=⇒ an(DE)n avec n ∈ N

On vérifie facilement que an(DE)n = an−1aDE(DE)n−1 se dérive en an−1abc(DE)n−1. Mon-

trons maintenant par récurrence sur k que bkckDE se dérive en bk+1ck+1, ∀k > 0 :

– Montrons cela pour k = 1 :

bcDE

(5)

=⇒ bDEE

(6)

=⇒ bbEE

(4)

=⇒ bbcE

(7)

=⇒ bbcc

– Supposons que cela est vrai jusqu’au rang k :

bkckDE

Hyp

=⇒ bk+1ck+1

– Montrons que cela est vrai au rang k + 1 :

bk+1ck+1DE

(5)

=⇒ bbkckDEE

Hyp

=⇒ bbk+1ck+1E

(7)

=⇒ bbk+1ck+1c = bk+2ck+2

Par conséquent, en répétant ces dérivations n − 1 fois de suite, on dérivera an−1abc(DE)n−1 en

anbncn.

3 Langages réguliers et Automates finis

3.1 Grammaires régulières et langages réguliers

Définition (Grammaire régulière) : On rappelle qu’une grammaire G = (T, N, S, R) est

régulière

– à droite si les règles de R sont de la forme

– à gauche si les règles de R sont de la forme

A → aB ou A → a avecA, B ∈ N et a ∈ T

A → Ba ou A → a avecA, B ∈ N et a ∈ T

Exemple de grammaire régulière à droite : G1 = (T1, N1, S1, R1) avec

T1 = { a, b }

N1 = { S1, U1 }

R1 = { S1 → aS1 | aU1

U1 → bU1 | b }

15

Exemple de grammaire régulière à gauche : G2 = (T2, N2, S2, R2) avec

T2 = { a, b }

N2 = { S2, U2 }

R2 = { S2 → S2b | U2b

U2 → U2a | a }

G1 et G2 engendrent le même langage : L(G1) = L(G2) = {anbp/n > 0, p > 0}

Définition (Langage régulier) : Un langage est régulier si et seulement s’il existe une gram-

maire régulière générant ce langage.

Les grammaires et langages réguliers sont la base de la lexicographie. L’ensemble des mots-clés,

identificateurs, constantes numériques, ... d’un langage de programmation tel que le C++ est un

langage régulier et peut être décrit par une grammaire régulière.

L’intérêt de distinguer grammaires régulières à droite ou à gauche apparait lors de l’analyse : si on

lit les symboles du mot à analyser de la gauche vers la droite, alors

• une grammaire régulière à droite sera utilisée pour une analyse descendante, de l’axiome vers le

mot ;

• une grammaire régulière à gauche sera utilisée pour une analyse ascendante, du mot vers l’axiome.

Par exemple, pour analyser le mot aaabb avec la grammaire G1, on construira la déri-

vation

S1 ⇒ aS1 ⇒ aaS1 ⇒ aaaU1 ⇒ aaabU1 ⇒ aaabb

tandis que pour analyser ce mot avec la grammaire G2, on construira la dérivation

aaabb ⇐ U2aabb ⇐ U2abb ⇐ U2bb ⇐ S2b ⇐ S2

3.2 Automates Finis Indéterministes

Un automate est une procédure effective (un algorithme) permettant de déterminer si un mot

donné appartient à un langage. A la classe des langages réguliers correspond une classe particulière

d’automates (reconnaissant les langages réguliers et seulement ceux-ci) : la classe des automates

finis.

Définition (Automate Fini Indéterministe = AFI) : Un automate fini indéterministe est

défini par un quintuplet (K, T, M, I, F ) tel que

– K est un ensemble fini d’états.

– T est le vocabulaire terminal (correspondant à l’alphabet sur lequel est défini le langage).

– M est une relation dans K × T × K, appelée relation de transition (autrement dit, M est un

ensemble de triplets de la forme (Si, a, Sj) où Si et Sj sont des états de K et a est un symbole

du vocabulaire terminal T ). Intuitivement, un triplet (Si, a, Sj) ∈ M signifie que si l’automate

se trouve dans l’état Si et le mot à analyser commence par le symbole a, alors l’automate peut

aller dans l’état Sj.

– I ⊆ K est l’ensemble des états initiaux.

– F ⊆ K est l’ensemble des états finaux.

16

Représentation graphique d’un automate fini : On représente généralement un automate

fini par un graphe orienté dont les arcs sont étiquetés. Chaque état de l’automate est représenté

par un sommet du graphe. A chaque transition (Si, a, Sj) ∈ M on associe un arc du sommet Si

vers le sommet Sj étiqueté par a. Les sommets du graphe correspondant à des états initiaux de

l’automate sont repérés par une pointe de flêche. Les sommets du graphe correspondant à des états

finaux sont entourés de deux cercles.

Par exemple, l’AFI (K, T, M, I, F ) tel que

• K = {S, V, U },
• T = {a, b},
• M = {(S, a, S), (S, a, V ), (V, b, V ), (V, b, U )},
• I = {S},
• F = {U }

sera représenté graphiquement par le graphe :

Fonctionnement d’un AFI : De façon informelle, un mot u est accepté par un AFI s’il existe

un chemin d’un sommet initial vers un sommet final tel que la concaténation des étiquettes des

arcs empruntés par le chemin soit égale à u. Sur l’exemple précédent, le langage des mots acceptés

par l’automate est L = {anbp/n > 0, p > 0}.

De facon plus formelle, le fonctionnement d’un AFI A = (K, T, M, I, F ) est défini de la facon

suivante :

– Une configuration de l’automate est caractérisée par un couple...