Aller au contenu
Théorie des langages et compilation · L3

Leçon 1 sur 5

Alphabets, mots, langages et expressions régulières

Je sais manipuler mots et langages sur un alphabet, calculer les opérations sur les langages (concaténation, étoile de Kleene) et décrire un langage par une expression régulière.

  • 1 h 15
  • 7 exercices corrigés
  • QCM de 7 questions

À la fin de la leçon, vous saurez :

  • Définir alphabet, mot, longueur, mot vide, préfixe, suffixe, facteur et miroir
  • Calculer union, concaténation, puissances et étoile de Kleene de langages
  • Lire et écrire des expressions régulières et décrire en français le langage qu'elles dénotent
  • Démontrer ou réfuter une égalité entre expressions régulières
  • Utiliser les expressions régulières du module re de Python pour valider des chaînes

Avant de commencer : Mathématiques discrètes (ensembles, logique, récurrence), Algorithmique avancée et structures de données.

1Je découvre

Ibrahima, étudiant en L3 de génie informatique à Conakry, écrit un petit traducteur de mots entre le pular, le soussou et le malinké. Première difficulté : avant même de traduire, son programme doit reconnaître ce qu'est un mot valide. Le pular s'écrit avec des lettres qui n'existent pas en français, comme ɓ, ɗ, ŋ ou ƴ. Son programme découpait « ɓiɗɗo » en morceaux incohérents, car il ne connaissait que les 26 lettres de l'anglais.

Au même moment, sa camarade Kadiatou écrit l'interface d'inscription d'une application de Mobile Money : elle doit vérifier qu'un numéro saisi « ressemble » à un numéro mobile guinéen, sans écrire des dizaines de tests.

Dans les deux cas, il faut décrire précisément un ensemble de chaînes de caractères. C'est l'objet de la théorie des langages, la base de tout compilateur, de tout moteur de recherche et de tout outil de validation.

Comment définir rigoureusement des mots et des ensembles de mots, et comment décrire de façon compacte un ensemble infini de mots ?

2Je comprends

1. Alphabets et mots

Un alphabet Σ est un ensemble fini et non vide de symboles (lettres). Exemples : Σ = {a, b} ; Σ = {0, 1} ; l'ensemble des caractères Unicode ; l'alphabet pular, qui contient ɓ, ɗ, ŋ, ɲ et ƴ.

Un mot sur Σ est une suite finie de lettres de Σ. On note :

  • |w| la longueur de w ; |w|a le nombre d'occurrences de la lettre a dans w ;
  • ε le mot vide, de longueur 0 ;
  • Σ^* l'ensemble de tous les mots sur Σ (y compris ε) et Σ^+ = Σ^* ∖ {ε} ;
  • Σn l'ensemble des mots de longueur n ; si |Σ| = k, alors |Σn| = kn.

La concaténation de u et v, notée uv, est le mot obtenu en écrivant u puis v. Elle est associative, a pour élément neutre ε (ε w = w ε = w), mais n'est pas commutative (ab ≠ ba). On a |uv| = |u| + |v|. On note wn la concaténation de n copies de w, avec w0 = ε.

NotionDéfinitionExemple avec w = abba
Préfixeu tel que w = uvε, a, ab, abb, abba
Suffixev tel que w = uvε, a, ba, bba, abba
Facteurv tel que w = uvxbb, bba…
Miroir wRw lu de droite à gaucheabba (c'est un palindrome)
Sous-motlettres prises dans l'ordre, pas forcément consécutivesaa est un sous-mot, pas un facteur

Un mot de longueur n a exactement n + 1 préfixes et n + 1 suffixes. Le miroir vérifie (uv)R = vR uR.

2. Langages et opérations

Un langage sur Σ est une partie de Σ^*, finie ou infinie. Exemples : {ab, ba} ; l'ensemble des identificateurs Python ; {an bn | n ≥ 0}.

Les langages étant des ensembles, on dispose de l'union, de l'intersection et du complémentaire L = Σ^* ∖ L. On définit en plus :

  • la concaténation : L1 L2 = {uv | u ∈ L1, v ∈ L2} ;
  • les puissances : L0 = {ε} et Ln+1 = Ln L ;
  • l'étoile de Kleene : L^* = ⋃n ≥ 0 Ln et L^+ = ⋃n ≥ 1 Ln = L L^*.

Pièges classiques : ∅ et {ε} sont différents. L∅ = ∅, alors que L{ε} = L. Et ∅^* = {ε}.

Exemple

Soit L₁ = {a, ab} et L₂ = {b, ε}. Calculez L₁L₂ et L₂L₁.

Étape 1 - L₁L₂ : a·b = ab ; a·ε = a ; ab·b = abb ; ab·ε = ab.

Étape 2 - On supprime les doublons : L₁L₂ = {a, ab, abb} (3 mots, et non 4).

Étape 3 - L₂L₁ : b·a = ba ; b·ab = bab ; ε·a = a ; ε·ab = ab, d'où L₂L₁ = {a, ab, ba, bab}.

Conclusion : L₁L₂ ≠ L₂L₁ ; la concaténation des langages n'est pas commutative, et |L₁L₂| ≤ |L₁| × |L₂|.

3. Les expressions régulières

Les expressions régulières (ou rationnelles) sur Σ sont définies par récurrence :

Expression rLangage dénoté L(r)
∅∅
ε{ε}
a (pour a ∈ Σ){a}
r + s (union, notée aussi r | s)L(r) ∪ L(s)
rs (concaténation)L(r)L(s)
r^* (étoile)L(r)^*

Priorités : l'étoile, puis la concaténation, puis l'union. Ainsi ab^* + c se lit (a(b^*)) + c.

Exemples sur Σ = {a, b} :

(a+b)*            tous les mots
(a+b)*ab          les mots qui se terminent par ab
b*ab*ab*          les mots qui contiennent exactement deux a
(a+b)aa(a+b)    les mots qui contiennent le facteur aa
((a+b)(a+b))*     les mots de longueur paire
b*(ab*ab*)*       les mots qui contiennent un nombre pair de a

Égalités utiles (r, s expressions quelconques) : r + s = s + r ; rε = ε r = r ; r∅ = ∅ ; (r^)^ = r^* ; r^* r^* = r^* ; (r + s)^* = (r^* s^)^ ; r(sr)^* = (rs)^*r ; r^* = ε + r r^*. En revanche, (r + s)^* ≠ r^* + s^* en général.

Méthode

Pour démontrer ou réfuter une égalité L(r) = L(s) :

  1. Je teste les mots courts (ε, puis longueur 1, 2, 3) pour chercher un contre-exemple.
  2. Si je trouve un mot dans un langage et pas dans l'autre, l'égalité est fausse : je donne ce mot.
  3. Sinon, je montre L(r) ⊆ L(s) en décomposant un mot quelconque de L(r).
  4. Puis je montre L(s) ⊆ L(r) de la même façon (ou j'utilise des égalités connues).
  5. Je conclus par double inclusion.

4. Les langages réguliers

Un langage est régulier (ou rationnel) s'il est dénoté par une expression régulière. De façon équivalente, la classe des langages réguliers est la plus petite classe qui contient ∅, {ε} et les {a}, et qui est fermée par union, concaténation et étoile. Tout langage fini est régulier (c'est l'union de ses mots).

À la leçon 2, nous verrons que les langages réguliers sont exactement ceux que reconnaît un automate fini (théorème de Kleene) et qu'ils sont aussi fermés par intersection et complémentaire. Certains langages ne sont pas réguliers, comme {an bn | n ≥ 0} : une expression régulière ne peut pas « compter » sans limite. Pour des expressions bien parenthésées comme ((x+1)*2), il faudra des grammaires (leçon 3).

5. Les expressions régulières en pratique : le module re

Les langages de programmation proposent des expressions régulières étendues. Le module re de Python utilise une syntaxe proche de celle des outils Unix (grep, sed) :

SyntaxeSensÉquivalent théorique
a‖ba ou ba + b
a*, a+, a?0 ou plus, 1 ou plus, 0 ou 1a^*, aa^*, a + ε
[abc], [a-z], [^0-9]une lettre de l'ensemble, d'un intervalle, ou hors ensembleunion de lettres
.n'importe quel caractère sauf le saut de ligneunion de toutes les lettres
\d, \s, \wchiffre, espace, caractère de motunions de lettres
a{3}, a{2,4}exactement 3, de 2 à 4 répétitionsaaa, aa + aaa + aaaa
^, $début, fin de la chaîne(ancrages)
import re

# Numéro mobile guinéen (format simplifié) : 9 chiffres commençant par 6,
# éventuellement précédé de +224
motif_tel = re.compile(r"^(\+224)?6\d{8}$")
print(bool(motif_tel.match("+224621234567")))   # True
print(bool(motif_tel.match("721234567")))       # False : ne commence pas par 6

# Identificateur : une lettre ou _, puis lettres, chiffres ou _
ident = re.compile(r"^[A-Za-z_][A-Za-z0-9_]*$")
print(bool(ident.match("prix_riz2")), bool(ident.match("2prix")))   # True False

# Mots pular contenant les lettres spéciales (Unicode)
print(re.findall(r"[a-zɓɗŋɲƴ]+", "ɓiɗɗo ɗemngal"))   # ['ɓiɗɗo', 'ɗemngal']

On écrit les motifs dans des chaînes brutes r"..." pour que \d ne soit pas interprété par Python. Attention : certaines extensions (références arrière comme (a+)\1) sortent de la théorie et décrivent des langages non réguliers.

3Je retiens

Je retiens

Un alphabet est fini et non vide ; Σ* contient tous les mots, y compris le mot vide ε.

La concaténation est associative, de neutre ε, mais pas commutative ; |uv| = |u| + |v|.

Un mot de longueur n a n + 1 préfixes ; sur un alphabet de k lettres, il y a kⁿ mots de longueur n.

L₁L₂ = {uv | u ∈ L₁, v ∈ L₂} ; L* = ∪ Lⁿ avec L⁰ = {ε} ; ∅* = {ε} et L∅ = ∅.

Expression régulière : ∅, ε, a, r + s, rs, r* ; priorité : étoile, concaténation, union.

Un langage régulier est dénoté par une expression régulière ; tout langage fini est régulier.

(r + s)* = (r*s*)* mais (r + s)* ≠ r* + s* ; on réfute une égalité par un contre-exemple.

{aⁿbⁿ} n'est pas régulier.

4Erreurs fréquentes

  • Confondre ∅ (aucun mot) et {ε} (un mot, le mot vide).
  • Croire que |L₁L₂| = |L₁| × |L₂| : des produits différents peuvent donner le même mot.
  • Lire ab* comme (ab)* : l'étoile ne porte que sur b.
  • Écrire (a+b)* = a* + b* : le mot ab est dans le premier langage, pas dans le second.
  • Confondre facteur (lettres consécutives) et sous-mot (lettres dans l'ordre, pas forcément consécutives).
  • Oublier les ancrages de début et de fin (^ et dollar) en Python : re.search trouve un motif n'importe où dans la chaîne.

5Je m’exerce

1Exercice 1

(Questions de cours) a) Qu'est-ce qu'un alphabet ? Pourquoi ℕ n'en est-il pas un ? b) Que valent L∅, L{ε} et ∅^* ? c) Combien y a-t-il de mots de longueur 4 sur {0, 1} ? de longueur au plus 4 ?

Voir le corrigéCacher le corrigé

a) Un ensemble fini et non vide de symboles. ℕ est infini : ce n'est pas un alphabet (on peut en revanche écrire les entiers sur l'alphabet {0, …, 9}). b) L∅ = ∅ ; L{ε} = L ; ∅^* = {ε}. c) 24 = 16 mots de longueur 4 ; de longueur au plus 4 : 1 + 2 + 4 + 8 + 16 = 31.

2Exercice 2

Soit w = abba sur {a, b}. a) Donnez |w|, |w|b et wR. b) Listez les préfixes et les suffixes de w. c) Listez tous les facteurs distincts de w et comptez-les.

Voir le corrigéCacher le corrigé

a) |w| = 4, |w|b = 2, wR = abba (palindrome). b) Préfixes : ε, a, ab, abb, abba. Suffixes : ε, a, ba, bba, abba. c) Facteurs : longueur 0 : ε ; longueur 1 : a, b ; longueur 2 : ab, bb, ba ; longueur 3 : abb, bba ; longueur 4 : abba. Total : 1 + 2 + 3 + 2 + 1 = 9 facteurs distincts.

3Exercice 3

Soit L1 = {a, ab} et L2 = {b, ε}. a) Calculez L12. b) Calculez L2^*. c) Le mot abab appartient-il à L1^* ? et le mot abba ? Justifiez.

Voir le corrigéCacher le corrigé

a) L12 = L1 L1 = {aa, aab, aba, abab} (4 mots distincts). b) L2^* = {b, ε}^* = {bn | n ≥ 0}, soit le langage de b^*. c) abab = (ab)(ab) avec ab ∈ L1 : oui. Pour abba : tout mot de L1^* est une suite de blocs a ou ab ; chaque b y est immédiatement précédé d'un a. Dans abba, le second b est précédé d'un b : abba ∉ L1^*.

4Exercice 4

Décrivez en français le langage dénoté par chaque expression sur {a, b} : a) a(a + b)^*b ; b) (ab)^* ; c) (a + b)^aa(a + b)^ ; d) b^(abb^)^*(a + ε).

Voir le corrigéCacher le corrigé

a) Les mots qui commencent par a et se terminent par b. b) Les mots ε, ab, abab, …, c'est-à-dire les répétitions du bloc ab. c) Les mots qui contiennent au moins une fois le facteur aa. d) Les mots qui ne contiennent pas le facteur aa : chaque a est suivi d'au moins un b, sauf éventuellement un a final.

5Exercice 5

Écrivez une expression régulière sur {a, b} pour : a) les mots qui contiennent au moins un a ; b) les mots dont le nombre de a est un multiple de 3 ; c) les mots qui ne se terminent pas par b ; d) les mots de longueur au plus 2.

Voir le corrigéCacher le corrigé

a) b^a(a + b)^ (on repère le premier a). b) b^*(ab^*ab^ab^)^*. c) ε + (a + b)^*a : le mot vide, ou un mot terminé par a. d) ε + a + b + (a + b)(a + b), ou encore (a + b + ε)(a + b + ε).

6Exercice 6

a) Écrivez une expression régulière Python qui reconnaît un matricule étudiant d'exemple de la forme « GI-2026-0457 » : les lettres GI, un tiret, une année de quatre chiffres commençant par 20, un tiret, quatre chiffres. b) Parmi « GI-2026-0457 », « GI-1999-0457 », « gi-2026-0457 » et « GI-2026-457 », lesquels sont reconnus ?

Voir le corrigéCacher le corrigé

a)

import re
matricule = re.compile(r"^GI-20\d{2}-\d{4}$")
for s in ["GI-2026-0457", "GI-1999-0457", "gi-2026-0457", "GI-2026-457"]:
    print(s, bool(matricule.match(s)))

b) Seul « GI-2026-0457 » est reconnu. « GI-1999-0457 » : l'année ne commence pas par 20. « gi-2026-0457 » : les minuscules ne correspondent pas à GI (sauf avec l'option re.IGNORECASE). « GI-2026-457 » : trois chiffres au lieu de quatre.

7Exercice 7

(Type examen) a) Démontrez ou réfutez : (i) (a + b)^* = a^* + b^* ; (ii) (ab)^a = a(ba)^ ; (iii) (a + b)^* = (a^b^)^*. b) Sur l'alphabet {0, 1}, écrivez une expression régulière des écritures binaires, sans zéro inutile en tête, des entiers pairs (0 compris). c) Montrez par récurrence sur |v| que (uv)R = vR uR.

Voir le corrigéCacher le corrigé

a) (i) Faux : ab ∈ L((a + b)^*), mais ab ∉ L(a^*) et ab ∉ L(b^*). (ii) Vrai : un mot de (ab)^*a s'écrit (ab)n a = abab ⋯ ab a avec n blocs ; c'est la suite alternée a b a ⋯ a de 2n + 1 lettres commençant et finissant par a, qui s'écrit aussi a(ba)n. Les deux langages sont égaux à {(ab)n a | n ≥ 0}. (iii) Vrai : L(a^b^) ⊆ L((a + b)^*), donc (a^b^)^* ⊆ ((a + b)^)^ = (a + b)^*. Réciproquement, tout mot x1 ⋯ xn de (a + b)^* est une concaténation de lettres, et chaque lettre a ou b appartient à L(a^b^) : le mot appartient à (a^b^)^*. b) 0 + 1(0 + 1)^*0 : soit le mot 0, soit un mot commençant par 1 (pas de zéro en tête) et se terminant par 0 (nombre pair). c) Pour |v| = 0 : v = ε et (uε)R = uR = εR uR. Supposons la propriété vraie pour les mots de longueur n, et soit v = v'c avec |v'| = n et c une lettre. Par définition du miroir, (xc)R = c xR. Alors (uv)R = (uv'c)R = c (uv')R = c v'R uR = (v'c)R uR = vR uR. La propriété est vraie pour tout v.

Cherchez d’abord seul, sur votre cahier, puis ouvrez le corrigé pour comparer.

6Je vérifie

Choisissez une réponse pour chaque question : la correction s’affiche aussitôt.

1Combien de mots de longueur 3 y a-t-il sur un alphabet de 4 lettres ?
Voir la réponse

Réponse B : 64. 4³ = 64.

2Que vaut ∅^* ?
Voir la réponse

Réponse B : {ε}. L⁰ = {ε} pour tout langage, même vide.

3Combien de préfixes a le mot kharandi ?
Voir la réponse

Réponse B : 9. Un mot de longueur n a n + 1 préfixes, ε et le mot lui-même compris.

4L'expression ab^* dénote :
Voir la réponse

Réponse B : {a, ab, abb, …}. L'étoile porte seulement sur b.

5Quel mot appartient à L((a + b)^aa(a + b)^) ?
Voir la réponse

Réponse B : baab. baab contient le facteur aa.

6Le langage {an bn | n ≥ 0} :
Voir la réponse

Réponse C : n'est pas régulier. a*b* contient aussi aab ; aucune expression régulière ne dénote {aⁿbⁿ}.

7En Python, quel motif reconnaît exactement une chaîne de 3 chiffres ?
Voir la réponse

Réponse B : r"^\d{3}$". Sans ancrages, re.search accepte aussi « 12345 ».

Karamö, votre enseignant

Il a lu cette leçon. Posez-lui votre question : il vous répond ici.

Connectez-vous pour poser vos questions à Karamö.

Vous avez fini la leçon ?

Avec un compte Kharandi gratuit, vous cochez les leçons terminées et vous suivez votre progression, cours par cours.

Karamö
Un point pas clair ? Dites à Karamö ce qui vous bloque dans cette leçon : il vous l’explique autrement, pas à pas, sans faire le travail à votre place. Demander à Karamö
Signaler une erreur dans cette leçon

Toutes les leçons de Théorie des langages et compilation

Pose ta question à Karamö