Vocabulaires, mots, langages

1.1 Définitions de base

Vocabulaire

Mot

Langage

Codage

Algorithme

1.2 Opérations sur les mots

Préfixe

Suffixe

Infixe

. Image miroir

1.3 Opérations sur les langages

Opérations ensemblistes

Concaténation

Opération puissance

Opération * (étoile de Kleene)

1.4 Expressions régulières

Définition en intention et définition en extension

Définition récursive

Exemples

Lois algébriques sur les expressions régulières

Quelques propriétés intéressantes

Définition arborescente

1.5 Conclusion

Dans ce chapitre, nous présentons les concepts de base nécessaire à la compréhension du reste du cours. Les notions de vocabulaire, de mots et de langages sont introduits. Nous illustrons comment tout traitement informatique est précédé et suivi de phases de décodage et de codage dont la nature est un traitement sur un (ou plusieurs) langages.

Les opérations de base sur les langages seront présentées ainsi que la classe des langages réguliers. Les manipulations sur les expressions régulières seront illustrées.

Nous supposons connues les définitions de base de la théorie des ensembles et de celle des nombres.

1. Définitions de base

1.1. Vocabulaire

Un vocabulaire est un ensemble fini de signes. Par exemple, il peut s’agir d’un alphabet (latin, cyrillique, arabe), d’un syllabaire (japonais), etc.

> Par exemple, on notera : V = {a, b, c} le vocabulaire V composé des lettre a, b et c. On peut aussi avoir :

V_romain= {A, B, C, D, E, F, …Z}

V_{nombre romain}= {I, V, X, L, C, D, M}

V_thai = {°, ¢, £, §, •, ¶, ß, ®, ©, ™, …´}

V_morse= {·, - }

V_chat= {le, petit, chat, boit, du, lait }

1.2. Mot

Sur cet alphabet, on construit des mots à l’aide de l’opération de concaténation. Cette opération est notée par le signe : “.“ Soient u, v des mots, alors u . v est un mot.

> Par exemple : a.b ® ab

ab . c ® abc a . bc ® abc <

La longueur d’un mot est le nombre d’éléments du vocabulaire le composant. e est le mot vide. Sa longueur est nulle, car il n’est composé d’aucun élément du vocabulaire.

> Par exemple, le mot « ab » a une longueur égale à 2. « e » a une longueur égale à 0. « abcdefabcdef » a une longueur de 12.

Soient u et v deux mots de longueur l_u et l_v alors la longueur de « u . v » est l_u+ l_v. On peut définir la fonction « longueur » par récurrence :

1.3. Langage

Soit V un vocabulaire. L’ensemble des mots possibles sur V est noté V*.

> Soit V = {a, b} alors :

V* = {e, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, …} <

On note Æ le langage vide (il ne contient aucun mot). Le mot vide e est bien un mot à ne pas confondre avec Æ.

V* est un monoïde. Un monoïde est un ensemble muni d’une opération associative et possédant un élément neutre. Ici, l’opération associative est la concaténation “.“ et l’élément neutre est e.

> Par exemple : V = {a, b}

a.(a.b) = (a.a).b et d’une façon générale :

si u Î V* et x Î V alors x.u = u.x et appartient à V*

si u, v, w Î V* alors u.(v.w) = (u.v). w et appartient à V*

de plus :

a.e = e.a = a et d’une façon générale :

si u Î V* alors u.e = e.u = u <

On notera V⁺, l’ensemble V* privé de e. Autrement dit, nous avons V* = V+ È {e}. Intuitivement, V⁺ est l’ensemble de tous les mots possibles sur V et dont la taille est supérieure ou égale à 1.

Un langage est défini sur un vocabulaire V et constitue un sous-ensemble de V*.

> Par exemple, une langue utilisant l’alphabet latin, comme le Français, est un sous-ensemble des mots possibles sur le vocabulaire V = {a, …, z, A, …, Z, …, ?, …}.

L’ensemble des entiers L est représenté par le langage défini sur V = {0, …9} où aucun mot de commence par 0 à part 0 lui-même. De façon plus formelle, L = {0} È ensemble des mots de V⁺ ne commençant pas par 0. <

1.4. Codage

Soit deux vocabulaires V₁ et V₂. Un codage est une fonction de V₁* dans V₂*. Le codage peut s’appliquer sur le vocabulaire et être étendu au langage. Dans ce cas, il s’agit d’un codage fixe.

Un codage f est décodable que si f est une fonction injective. Une fonction f est injective si tout élément de l’image de f a un antécédent unique.

> Par exemple, soit V₁ = {a, b, c} et V₂= {1, 2, 3} et les règles de codage suivantes :

a ® 0 b ® 1 c ® 2

Alors le mot « bab » est codé « 101 ». Il est facile de voir que tout mot de V₁est codé de façon unique. Ce codage est donc décodable.

On remarquera que dans ce cas f étant bijective, la fonction inverse f^-1 est aussi un codage décodable. <

Il existe des fonctions de codage à partir desquelles on ne peut pas déduire facilement la fonction de décodage. Cette fonction de décodage n’est en fait connue que par les personnes autorisée à décoder les messages. Par contre, toute personne peut coder un message. De telles fonctions sont utilisées pour le cryptage de données.

D’une façon générale, le codage et le décodage constituent des opérations fondamentales du traitement de l’information.

> Par exemple, l’opération à réaliser est la somme de deux nombres a l’aide d’un additionneur binaire. Le vocabulaire est V = {0, …, 9, +}.

Le mot à traité est par exemple : « 12+4 ». Le code de 12 est 1100. Le code de + est 111111. Le code de 4 est 0100.

Le résultat du traitement (que nous n’explicitons pas ici) est 10000. Le décodage de 10000 donne 16. <

Exercice Codage Morse

La table ci-dessous décrit un codage de V₁* sur V₂*. En Morse, un message se termine toujours par le symbole de fin de message « # ». Une pause (notée /) est toujours insérée entre chaque caractère transmis sous forme codée.

c	Code	Son	c	Code	Son
A	. _	didah	U	. . _	dididah
B	_ . . .	dahdididit	V	. . . _	didididah
C	_ . _ .	dahdidahdit	W	. _ _	didahdah
D	_ . .	dahdidit	X	_ . . _	dahdididah
E	.	dit	Y	_ . _ _	dahdidahdah
F	. . _ .	dididahdit	Z	_ _ . .	dahdahdidit
G	_ _ .	dahdahdit	1	. _ _ _ _	didahdahdahdah
H	. . . .	didididit	2	. . _ _ _	dididahdahdah
I	. .	didit	3	. . . _ _	didididahdah
J	. _ _ _	didahdahdah	4	. . . . _	dididididah
K	_ . _	dahdidah	5	. . . . .	dididididit
L	. _ . .	didahdidit	6	_ . . . .	dahdidididit
M	_ _	dahdah	7	_ _ . . .	dahdahdididit
N	_ .	dahdit	8	_ _ _ . .	dahdahdahdidit
O	_ _ _	dahdahdah	9	_ _ _ _ .	dahdahdahdahdit
P	. _ _ .	didahdahdit	0	_ _ _ _ _	dahdahdahdahdah
Q	_ _ . _	dahdahdidah	.	. _ . _ . _	didahdidahdidah
R	. _ .	didahdit	,	_ _ . . _ _	dahdahdididahdah
S	. . .	dididit	?	. . _ _ . .	dididahdahdidit
T	_	dah	#	. _ . _ .	Didahdidahdit

Explicitez V₁ et V₂.

Que peut-on dire des mots de V₁* et des mots de V₂* ? Ce codage est-il décodable ? Justifier votre réponse.

Un apprenti télégraphiste à relevé le message suivant, en oubliant d’indiquer les pauses :

. . . _ _ _ . . . _ . . _ . _ _ . . . _ . _ . _ . _ . _ _ _ . . _ . _ . . . . _ . _ .

Pouvez-vous l’aider à le transcrire ? Comment s’y prendrait-on avec une machine ? n

D’une façon générale, un traitement informatique consiste à résoudre les points suivants :

a) Reconnaissance des mots (c’est-à-dire encore codage des mots) ;

b) Traitement de ces mots sous forme codée ;

c) Décodage du résultat.

Ici, nous avons pris le point de vue « humain ». Du point de vue de la machine nous aurions :

a’) Reconnaissance des mots (c’est-à-dire décodage des mots) ;

b’) Traitement de ces mots sous forme décodée ;

c’) Encodage du résultat.

Retenons simplement que l’informatique constitue essentiellement une question de :

Codage — Traitement — Décodage

1.5. Algorithme

Un algorithme est une suite finie d’opérations permettant de résoudre un problème (c’est-à-dire de répondre à une question).

Exercice Algorithme d’Euclide permettant de trouver le pgcd (plus grand dénominateur commun) de deux nombres.

Réponses

Les propriétés du pgcd de u et v sont :

Si u ³ v alors u = vq + r avec r >0

Si r = 0 alors pgcd(u, v) = v

Sinon (c’est-à-dire si u < v), pgcd (u, v) = pgcd(v, r) car un diviseur de u doit être un diviseur de qv et de r. Comme un diviseur de v est un diviseur de qv, un diviseur de u et v doit être une diviseur de v et r.

Algorithme d’Euclide

Soit u et v deux entiers, calculer le pgcd(u, v)

Si u ³ v alors

Si u est divisible par v (reste(u, v) = 0) alors

résultat = v

Sinon résultat = pgcd(v, reste(u, v))

Sinon résultat = pgcd(v, u).

Calculons le pgcd de 120 et 462 :

u = 120 et v = 462

u < v donc résultat = pgcd(462, 120)

u > v et reste(462, 120) = 102 donc résultat = pgcd(120, 102)

u > v et reste(120, 102) = 18 donc résultat = pgcd(102, 18)

u > v et reste(102, 18) = 12 donc résultat = pgcd(18, 12)

u > v et reste(18, 12) = 6 donc résultat = pgcd(12, 6)

u > v et reste(12, 6) = 0 donc résultat = 6

On peut aussi concevoir des algorithmes sur des mots.

Exercice Codes de César

Considérons le vocabulaire V = {A, B, C, … Z} et les fonctions de codage :

h_i : V ® V avec 0 £ i £ 25

associant à chaque élément de V, l’élément de V situé i positions plus loin dans le vocabulaire. La fin de V est continué cycliquement par le début.

Par exemple : h₂(A) = C, h₇(Y) = F, h₂₅(Z) = Z.

La table ci-dessous (appelée table de Vigenère) donne la définition de h_i pour son i^ème rang :

	A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0	A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
1	B C D E F G H I J K L M N O P Q R S T U V W X Y Z A
2	C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
3	D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
4	E F G H I J K L M N O P Q R S T U V W X Y Z A B C D
5	F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
6	G H I J K L M N O P Q R S T U V W X Y Z A B C D E F
7	H I J K L M N O P Q R S T U V W X Y Z A B C D E F G
8	I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
9	J K L M N O P Q R S T U V W X Y Z A B C D E F G H I
10	K L M N O P Q R S T U V W X Y Z A B C D E F G H I J
11	L M N O P Q R S T U V W X Y Z A B C D E F G H I J K
12	M N O P Q R S T U V W X Y Z A B C D E F G H I J K L
13	N O P Q R S T U V W X Y Z A B C D E F G H I J K L M
14	O P Q R S T U V W X Y Z A B C D E F G H I J K L M N
15	P Q R S T U V W X Y Z A B C D E F G H I J K L M N O
16	Q R S T U V W X Y Z A B C D E F G H I J K L M N O P
17	R S T U V W X Y Z A B C D E F G H I J K L M N O P Q
18	S T U V W X Y Z A B C D E F G H I J K L M N O P Q R
19	T U V W X Y Z A B C D E F G H I J K L M N O P Q R S
20	U V W X Y Z A B C D E F G H I J K L M N O P Q R S T
21	V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
22	W X Y Z A B C D E F G H I J K L M N O P Q R S T U V
23	X Y Z A B C D E F G H I J K L M N O P Q R S T U V W
24	Y Z A B C D E F G H I J K L M N O P Q R S T U V W X
25	Z A B C D E F G H I J K L M N O P Q R S T U V W X Y

On considère l’extension de h_i sur V* : H_i : V* ® V* avec 0 £ i £ 25

Par exemple : H_i(ABC) = CDE

Algorithme de codage d’un mot selon le code de César : soit w Î V* et i un entier. Par ailleurs, on considère que tableV contient la table ci-dessus.

But : calculer H_i(w)

Si longueur(w) > 0 alors

Soit c = premier(w)

Résultat = tableV [rang(c), i] . H_i(sauf-premier(w))

Sinon résultat = e

· La fonction premier(w) retourne le premier caractère du mot w. Par exemple : premier(abc) = a

· La fonction sauf-premier(w) retourne le mot w privé du premier caractère. Par exemple : sauf-premier(abc) = bc

· TableV[i, j] retourne l’élément de la table se trouvant à la i^ème colonne et à la j^ième ligne. Par exemple : TableV[3, 4] = F

· La fonction rang(c) retourne la position du caractère c dans le mot « ABCDEFGHIJKLMNOPQRSTUVWXYZ ». Il s’agit donc de la position de ce caractère dans l’alphabet. Par exemple : rang(E) = 5

On peut aussi concevoir des algorithmes travaillant à la fois sur des nombres et sur des mots.

Exercice Passage d’un entier codé en base décimale à un codage en base binaire.

Soit n l’entier à coder. L’idée est de diviser successivement n par 2. À chaque tour, on concatène le reste (0 ou 1) à gauche de la forme codée courante. On s’arrête quand n vaut 0.

Soit n = 57.

57 / 2 = 28 reste 1 donc résultat = 1

28 / 2 = 14 reste 0 donc résultat = 0 . 1 = 01

14 / 2 = 7 reste 0 donc résultat = 0 . 01 = 001

7 / 2 = 3 reste 1 donc résultat = 1 . 001 = 1001

3 / 2 = 1 reste 1 donc résultat = 1 . 1001 = 11001

1 / 2 = 0 reste 1 donc résultat = 1 . 11001 = 111001

n = 0 donc la forme binaire de 57 est 111001.

Algorithme de conversion d’un entier en base décimale à une forme en base binaire : soit n un entier.

But : calculer codage10vers2(n)

Si n > 0 alors

Soit r = reste (n, 2)

Soit q = quotient (n, 2)

Si r = 1 alors

résultat = codage10vers2(q) . 1

Sinon (r = 0) résultat = codage10vers2(q) . 0

Sinon résultat = e

Un algorithme doit être constitué d’un nombre fini d’opérations. Ceci ne signifie pas que l’algorithme se termine nécessairement.

> Exemple : énumération de tous les nombres premiers.

Il est clair qu’étant donné qu’il y a une infinité de nombres premiers, un algorithme résolvant ce problème ne se terminera jamais. <

Selon le problème posé, un algorithme peut ou non se terminer.

> Exemple : savoir s’il existe trois décimales consécutives de π dont la somme vaut un n entier fixé. <

2. Opérations sur les mots

2.1. Préfixe

Un mot w₁ est préfixe d’un mot w₂, s’il existe un mot w₃ tel que w₁.w₃ = w₂. Un mot est toujours son propre préfixe (dans ce cas w₃= e). e est préfixe de tout mot (e.w₂ = w₂).

2.2. Suffixe

Un mot w₁ est suffixe d’un mot w₂, s’il existe un mot w₃ tel que w₃.w₁ = w₂. Un mot est toujours son propre suffixe (dans ce cas w₃= e). e est suffixe de tout mot (w₂.e = w₂).

2.3. Infixe

Un mot w₁ est infixe d’un mot w₂, s’il existe deux mots w₃ et w₄tels que w₃.w₁.w₄ = w₂. Un mot est toujours son propre infixe (dans ce cas w₃= w₄= e). e est infixe de tout mot (w₃. e.w₄ = w₂).

> Par exemple : Pour le mot abbba, nous avons :

Préfixes	Infixes	Suffixes
e	e	e
a	a	a
ab	b	ba
abb	ab	bba
abbb	bb	bbba
abbba	ba	abbba
	abb
	bbb
	bba
	abbb
	bbba
	abbba

2.4. Image miroir

L’image miroir w~ d’un mot w est la lecture de droite à gauche du mot w.

> (abc)~ = cba e~ = e a~(bc)~ = acb

On a toujours : w~~ = w

Exercice : Définissez l’opérateur ~ par récurrence.

Réponse :

Un mot w est un palindrome si w~= w.

> (aba)~ = aba (abccba)~ = abccba

Exercice : Soit V = {a, b}. Soit L le langage tels que w Î L puisse être décomposé comme w = u . u~ avec u Î V*.

Que peut-on dire sur L ? et sur ¬L ?

Soit L’ = {w | w = u . x . u~ avec x Î {a, b} et u Î V*}.

Que représente L’ ?

Que peut-on dire sur l’intersection entre L et L’ ? Que se passe-t-il si x Î {e, a, b} ?

3. Opérations sur les langages

Nous rappelons ici que l’opération de concaténation est associative. L’élément neutre pour la concaténation est e.

> On a donc : (ab . (ac . bd)) = ((ab . ac) . bd) = abacbd

u . e = e . u = u <

3.1. Opérations ensemblistes

Un langage est une partie de V*, il s’agit d’un ensemble de mots. Les opérations suivantes sont donc définies :

Union

Intersection

Complémentation

On gardera à l’esprit que L Í V* et que :

L Ç V* = L

L È V* = V*

L Ç Æ = Æ

L È Æ = L

On notera ØL le complémentaire de L : ØL = V* - L

On se rappellera que :

ØØL = L

L Ç ¬L = ¬L Ç L = Æ

L È ¬L = ¬L È L = V*

¬(L₁ È L₂)

¬(L₁ Ç L₂)

D’autre part, nous avons :

¬L₁ È ¬L₂ ≠ ¬(L₁ È L₂)

Mais, nous avons :

¬L₁ È ¬L₂ = ¬(L₁ Ç L₂)

¬L₁ Ç ¬L₂ = ¬(L₁ È L₂)

Remarquons que l’intersection peut être exprimée à l’aide de l’union et du complémentaire :

L₁ Ç L_{2 =}¬(¬L₁ È ¬L₂)

3.2. Concaténation

On peut étendre l’opération de concaténation aux ensembles en général et donc aux langages en particulier.

Si L₁ et L₂ Ì V* et a Î V alors :

a . L₁= {a . w | w Î V}

L₁ . L₂= { w₁ . w₂ | w₁ Î L₁, w₂ Î L₂}

Exercice : Soit Lle langage sur V = {a, b} dont les mots contiennent un nombre pair de a.

1) Que peut-on dire sur a . L? Sur L . a?

2) Que peut-on dire sur ¬L? Sur L²? Sur ¬(L²) ? Et sur (¬L)²?

3) Avons nous ¬(L²) = (¬L)² ?

Réponses :

Tout d’abord, jouons un peu avec L. On peut commencer à énumérer les mots de L par taille croissante (et par nombre de a décroissant). On a donc L= {e, b, aa, bb, baa, aba, aab, bbb, aaaa, aaaab, aaaba, aabaa, abaaa, baaaa, bbaa, baba, baab, abab, aabb, …}.

On remarquera que toutes les tailles de mots sont représentées (on peut construire des mots de toutes les tailles avec uniquement des b)

1) (a . L) contient tous les mots de L où un « a » a été concaténé à gauche. Le nombre de a est donc impair. Il s’agit donc des mots ayant un nombre impair de a et commençant par a.

Idem pour (L . a), si ce n’est que les mots contiennent un nombre impair de a se terminent par a.

2) ¬L est le langage dont les mots contiennent un nombre impair de a. ¬L = {a, ab, ba, aaa , abb, bab, bba, aaab, aaba, abaa, baaa, …}. Comme précédemment toutes les tailles de mot (sauf 0) sont représentées.

L² est l’ensemble des mots w₁w₂ ou w₁, w₂ Î L. Clairement, le nombre de a des mots de L² est pair (l’addition de deux nombres pairs donne un nombre pair).

Donc L²Í L.

Si on essaye d’énumérer les mots de L², on peut, pour chaque mot de L₁, concaténer l’ensemble L :

L² = (e . L) È (b . L)È (aa _,L) È (bb . L) È (baa . L) È (aba . L) È (aab . L) È …

On remarque alors que le premier terme (e . L) = L. Donc, a :

L² = L È (b . L)È (aa _,L) È (bb . L) È (baa . L) È (aba . L) È (aab . L) È …

Donc L Í L².

Si L²Í L et L Í L² alors L = L²

Par suite ¬(L²) = ¬(L) = ¬L

3) Nous avons : ¬(L²) = ¬L et (¬L)²= (¬L) . (¬L)

La concaténation de deux mots dont le nombre de a est impair forme un mot dont le nombre de a est pair (mais non nul). Un tel ensemble est clairement L privé du mot vide. Donc :

(¬L)²= ¬(L) . ¬(L) = L - e

A-t-on L - e = ¬L ?

Clairement aa Î L - e, mais aa Ï ¬L.

Donc ¬(L²) ¹ ¬(L)²

On remarquera que, dans le cas général, on ne peut rien dire sur :

¬(L²) = (¬L)(¬L) ?

Exercice : Vérifier l’assertion ci-dessus.

Cherchons un langage simple qui ne vérifie pas la propriété.

Choisissons L = {a}. Alors ¬L = V* - {a}.

Donc L² = {aa}.

Donc ¬(L²) = V* - {aa}.

Or ¬L = V* - {a}, donc (¬L)(¬L) = (V* - {a})(V* - {a})

Or aa Î (V* - {a})(V* - {a}). En effet : aa = e.aa

On a trouve un mot qui appartient à ¬(L²) et pas à (¬L)(¬L)

Donc dans ce cas ¬(L²) ≠ (¬L)(¬L).

Cherchons un langage qui vérifie la propriété.

Choisissons L = Æ. Alors ¬L = V*

Donc L² = Æ . Æ = Æ.

Donc ¬(L²) = V*

Or ¬L = V*, donc (¬L)(¬L) = V* . V* = V*

Donc dans ce cas ¬(L²) = (¬L)(¬L).

3.3. Opération puissance

Soit U un ensemble quelconque, nous avons par définition :

U⁰ = {e}

Uⁿ = U . U^n-1= U^n-1 . U

Donc en particulier sur un langage L, nous avons :

L⁰ = {e}

Lⁿ = L . L^n-1= L^n-1 . L

> Ainsi pour un langage L nous avons : L³ = L . L . L = LLL.

Si L est le langage sur V = {a, b} dont les mots contiennent un nombre impair de a, alors L²= LL ne contient que des mots ayant un nombre pair de a. <

Donc en particulier sur un mot w, nous avons :

w⁰ = e

wⁿ = w . w^n-1= w^n-1 . w

> Ainsi : w³ = www (abc)⁴ = abcabcabcabc

3.4. Opération * (étoile de Kleene)

Par définition, pour tout ensemble U, nous avons :

Cette définition est donc valable pour tout langage L. En particulier sur un vocabulaire V, nous avons :

V⁰ = {e}

V¹ = V . {e} = V = mots de longueur 1

V² = V . V = mots de longueur 2

…

Vⁿ = V . V^n-1 = V^n-1 . V = mots de longueur n

C’est-à-dire :

V* est l’ensemble des mots de toutes les longueurs possibles, c’est donc l’ensemble de tous les mots possibles.

4. Expressions régulières

4.1. Définition en intention et définition en extension

Pour définir un langage, il est nécessaire de disposer d’un moyen de description des mots de ce langage. La première méthode consiste à énumérer les mots de ce langage. C’est ce qu’on appelle une définition en extension.

Cette méthode est très lourde et ne permet pas de définir des ensembles infinis.

On peut aussi définir un langage par la description des propriétés (ou du comportement) que doivent avoir les mots de ce langage. C’est ce qu’on appelle une définition en intention.

Il est possible de décrire certains types de propriétés à l’aide d’un autre langage. Ce métalangage est d’abord décrit puis une interprétation des mots de ce métalangage sera donnée.

4.2. Définition récursive

Soit V un vocabulaire dans lequel les symboles de M = {+, ., *, (, ), Æ, e} n’apparaissent pas. Une expression régulière sur V sera définie comme un mot sur V’ = V È M.

Ces mots sont définis récursivement de la façon suivante :

· Æ est une expression régulière et représente le langage vide ;

· e est une expression régulière et représente le langage contenant le mot vide ;

· w Î V* est une expression régulière et représente le langage {w}

· si A et B sont deux expressions régulières représentant les langage L_A et L_B alors (A + B) est une expressions régulière représentant le langage L_A È L_B.

· si A et B sont deux expressions régulières représentant les langages L_A et L_B alors (A . B) est une expression régulière représentant le langage L_A . L_B.

· A* est une expression régulière représentant le langage L_Aavec :

· Lorsqu’il n’y a pas d’ambiguïté, les parenthèses ou les points peuvent être supprimés.

Un langage qui peut être décrit par une expression régulière est appelé langage régulier. On remarquera que tous les langages possibles ne sont pas réguliers.

Exercices

Essayez de trouver quelques langages qui n’ont pas l’air réguliers.

Réponse

L sur V = {a, b} où il y a le même nombre de a que de b.

La démonstration (un peu compliquée) consiste à montrer qu’il faudrait une union infinie d’expressions régulières pour décrire L.

Exercices

Trouver une classe de langages incluse dans celle des langages réguliers.

Réponse

La classe des langages finis (c’est-à-dire ayant un nombre fini de mots) est incluse dans celle des langages réguliers.

4.3. Exemples

> Les nombres entiers sont représentés par les mots du langage définis par l’expression régulière :

0 + (1+2+3+4+5+6+7+8+9).(1+2+3+4+5+6+7+8+9)* <

Une extension des expressions régulières est parfois définie avec une définition de plage de caractères (entre crochets).

> Par exemple : 0 + [1-9].[0-9]*

Le langage composé alternativement de a et de b peut être décrit par l’expression régulière :

(ab)*

Le langage composé alternativement d’un a et d’un nombre quelconque de b peut être décrit par l’expression régulière :

a(b)* = ab* <

En général, on préférera réserver l’utilisation du symbole + pour l’union. On écrira donc plutôt aa* (ou a*a) que a⁺.

aa* = a*a correspond au langage dont les mots ne sont composés que de a.

(a*b*)* = (a + b)* = V* si V = {a, b}

Exercice Démontrer l’égalité précédente

Réponse

Clairement nous avons (1) a*b* Ê a + b.

En effet, avec l’expression régulière a*b* on décrit (entre autres) les mots a et b.

De (1), on déduit (2) (a*b*)* Ê (a + b)*

Or (a + b)* = V* est l’ensemble de tous les mots possibles, donc il ne peut pas exister de mots non inclus dans V*, donc (a*b*)* = (a + b)*

Exercice Démontrer que L₁ Í L₂Þ L₁* Í L₂*

Éléments de réponse :

La démonstration peut se faire en plusieurs étapes.

(1) Démontrer que si L₁ Í L₂et L₃ Í L₄alors L₁ . L₃ Í L₂ . L₄

(2) Déduire par récurrence de ce qui précède que si L₁ Í L₂alors (L₁)ⁿ Í (L₂)ⁿ

(3) Déduire de ce qui précède en identifiant terme à terme que si L₁ Í L₂alors

( (L₁)⁰+ (L₁)¹ + (L₁)² + (L₁)³ + … ) Í ( (L₂)⁰+ (L₂)¹ + (L₂)² + (L₂)³ + … )

(4) Conclure que si L₁ Í L₂alors L₁* Í L₂*

Exercice avons-nous L₁ Í L₂Ü L₁* Í L₂* ?

Réponse

On peut exhiber un contre-exemple, par exemple

a* Í e* Þ a Í e ce qui est clairement faux.

Donc dans le cas général, nous n’avons pas L₁ Í L₂Ü L₁* Í L₂*

Est-ce pour autant toujours faux ? Non, car on peut exhiber un exemple :

a* Í (a*)* Þ a Í a* ce qui est clairement vrai.

4.4. Lois algébriques sur les expressions régulières

· (Æ + R) º (R + Æ) º R élément neutre de l’union

· (e . R) º (R . e) º R élément neutre de la concaténation

· (Æ . R) º (R . Æ) º Æ élément absorbant de la concaténation

· R + S º S + R

· R + (S + T) º (R + S) + T

· R . ( S . T) º (R . S) . T

· R . (S + T) º (R . S) + (R . T)

· ( S + T) . R º (S . R) + (T . R)

· R + R º R

· Æ* º e

· R . R* º R* . R º R+

· R . R* + e º R*

Exercice Justification de 7

Réponse Par la méthode de la double inclusion.

Soit x Î L(R.(S+T)) Þ x est de la forme : x = ry avec x Î L(R) et y Î L(S+T).

y Î L(S+T) Þ soit y Î L(S), soit y Î L(T), soit y Î L(S) et y Î L(T)

y Î L(S) Þ x = ry Î L(RS) Þ x Î L(RS+RT)

y Î L(T) Þ x = ry Î L(RT) Þ x Î L(RS+RT)

Donc x Î L(R.(S+T)) Þ x Î L(RS+RT)) et L(R.(S+T)) Í L(RS+RT))

Réciproque

x Î L(RS+RT)) Þ soit x Î L(RS), soit x Î L(RT), soit x Î L(RS) et x Î L(RT)

x Î L(RS) Þ x = ry et r Î L(R) et y Î L(S) Þ y Î L(S+T) Þ x = ry Î L(R.(S+T))

x Î L(RT) Þ x = ry et r Î L(R) et y Î L(T) Þ y Î L(S+T) Þ x = ry Î L(R.(S+T))

Donc x Î L(RS+RT)) Þ x Î L(R.(S+T)) et L(RS+RT)) Í L(R.(S+T))

(L(R.(S+T)) Í L(RS+RT)) et L(RS+RT)) Í L(R.(S+T)) )

Þ L(RS+RT)) = L(R.(S+T))

Exercice Démontrer que a* = e + aa*

Réponse

a* = a⁰ + a¹ + a² + a³ + a⁴ + …

= e + a¹ + a² + a³ + a⁴ + …

= e + a(a⁰ + a¹ + a² + a³ + a⁴ + …)

= e + a(a*)

= e + aa*

Cette démonstration est valable pour toutes expressions régulières (point 12) :

R* = e + RR*

On remarquera que l’on peut aussi bien factoriser a à droite ce qui donne :

a* = a⁰ + a¹ + a² + a³ + a⁴ + …

= e + a¹ + a² + a³ + a⁴ + …

= e + (a⁰ + a¹ + a² + a³ + a⁴ + …)a

= e + (a*)a

= e + a*a

On en déduit que aa* = a*a

D’une façon générale R* = e + RR* = e + R*R

Exercice : Justification de Æ* º e

Réponse :

Æ* = Æ0 + Æ¹ + Æ² + Æ³ + …

e + Æ + Æ² + Æ³ + …

Démontrons par récurrence que Æⁿ= Æ pour n>0.

Cas de base : Æ¹ = Æ

Récurrence : Supposons Æⁿ= Æ vraie. Nous avons Æⁿ⁺¹= Æⁿ . Æ = Æ . Æ = Æ. cqfd

Donc Æ* = e + Æ + Æ + Æ + …= e + Æ = e

4.5. Quelques propriétés intéressantes

Dans ce qui suit X et Y sont des expressions régulières.

X(YX)* = (XY)*X

Démonstration : à faire en exercice

(XY)* = e + X(YX)*Y

Démonstration : à faire en exercice

(X+Y)* = X*(YX*)*

Démonstration par double inclusion

a) (X+Y)* Í X*(YX*)*

Soit w Î (X+Y)*

Donc $ n ³ 0 et z₁ … z_n Î (X+Y) tq w = z₁.….z_n

Or z_i = xy tq xi Î X* et y Î Y.

Donc w = x₀ . y₁ . x₁ . … . y_n. x_navec x_i Î X* et y_i Î Y

Donc w Î X*(YX*)*

Donc (X+Y)* Í X*(YX*)*

b) Réciproque (X+Y)* Ê X*(YX*)* à faire en exercice

(X+Y)* = (X*Y)*X*

Démonstration :

(X+Y)* = X*(YX*)* et x(yx)* = (xy)*x

donc si x = X* et y = Y nous avons X*(YX*)* = (X*Y)*X* = (X+Y)*

X* = (e + X + … + X^n-1)(Xⁿ)* pour n > 1

Démonstration : à faire en exercice

(a*)* = a*

Démonstration : par double inclusion

1) Démontrons (a*)* Ê a*

(a*)* = a*⁰ + a*¹ + a*² + a*³ + a*⁴ + …

= e + a* + a*² + a*³ + a*⁴ + … Ê a*

2) (a*)* Í a*

Démontrons par récurrence que (e + a¹ + a² + …) Í (e + a¹ + a² + …)ⁿpour n>0

Pour n=1, la propriété est vraie (e + a¹ + a² + …) Í (e + a¹ + a² + …)¹

Supposons, le propriété vraie pour n, l’est-elle pour n+1 ?

(e + a¹ + a² + …) Í (e + a¹ + a² + …)ⁿ.(e + a¹ + a² + …) est vrai car

L₁ Í L₃ et L₂ Í L₄ alors L₁L₂ Í L₃L₄

or ici L₁ = (e + a¹ + a² + …) Í L₃ = (e + a¹ + a² + …)ⁿ

L₂ = e Í L₄ = (e + a¹ + a² + …)

Donc nous avons (e + a¹ + a² + …) Í (e + a¹ + a² + …)ⁿ⁺¹pour n>0 cqfd

(a*)* = (a⁰ + a¹ + a² + …)*

= (e + a¹ + a² + …)⁰+ (e + a¹ + a² + …)¹+ (e + a¹ + a² + …)²+ …

= e + a¹ + a² + …

4.6. Définition arborescente

Une arborescence est un graphe orienté, où chaque point différent du point nommé « racine » a un et un seul antécédent. La racine n’a aucun antécédent. Un point est en général appelé « nœud ».

La structure syntaxique d’une expression régulière sur V est une arborescence définie par récurrence de la façon suivante :

Cas de base : Si l’expression régulière est définie soit par un caractère x (x Î V), soit par les symboles e ou f, alors l’expression constitue la structure syntaxique.

x e f

Récurrence : Si l’expression régulière est un opérateur (unaire) portant sur une expression régulière A ou un opérateur (binaire) portant sur deux expressions régulières A et B. Soit respectivement :

A* A . B A + B

Alors, les structures syntaxiques de l’expression régulière sont respectivement :

> Par exemple, l’expression régulière (0 + 1)* . 11(1 + 01)* . (e + 0) a pour structure syntaxique :

En prenant comme précédence des opérateurs :

(((0 + 1)*) . (1.1.(((1 + (0.1))*) . (e + 0)))) <

Nous appellerons occurrences d’opérateurs le nombre d’opérateurs présents dans la structure syntaxique. Nous appellerons occurrences d’atomes, le nombre d’éléments de V È {f, e} présents dans la structure syntaxique. Nous appellerons occurrences de symboles la somme des occurrences d’opérateurs et d’occurrence d’atomes.

> Dans l’expression régulière précédente, il y a 10 occurrences d’opérateurs et 9 occurrences d’atomes. <

On remarquera que les atomes sont les feuilles (nœuds terminaux) de la structure arborescente et que les opérateurs sont les autres nœuds.

5. Conclusion

Ce chapitre a introduit les notions fondamentales de base que sont les mots, les vocabulaires, les langages. Nous avons illustré comment tout traitement informatique est précédé par une phase de codage et se termine par une phase de décodage. Ces deux phases constituent un traitement sur des langages. Un algorithme est une suite finie d’instructions permettant d’effectuer un traitement. Parmi, les traitements envisagés on aura bien sur les phases de codage et décodage.

Les langages sont des ensembles (potentiellement infinis) de mots et à ce titre acceptent les opérations ensemblistes. La description d’ensemble de cardinalité infini ne peut se faire qu’en intention.

Les expressions régulières constituent un formalisme intéressant pour décrire en intention la classe des langages réguliers. Nous avons introduit certains des propriétés et des opérateurs associés aux expressions régulières.