Skip to main content Informatique en prépa - Lycée Malherbe 

2- Expressions régulières

Les expressions régulières sont un outil pour décrire certains langages, sans avoir recours à des énumérations ou à un paramétrage.

On pose sur cette page .

I. Définitions

Définition inductive : expression régulière

Une expression régulière est :

  • (cas de base)
    • soit une lettre
    • soit le mot vide
    • soit l'ensemble vide
  • (cas inductifs)
    • soit la concaténation de deux expressions régulières
    • soit l'union de deux expressions régulières , parfois écrit
    • soit l'étoile d'une expression régulière

Par exemple, est une expression régulière.

Définition inductive : langage associé à une expression régulière

On défini inductivement le langage associé à une expression régulière , noté :

  • (cas de base)
    • si , alors
    • si , alors
    • si , alors
  • (cas inductifs, si e est une expression régulière)
    • si , alors
    • si , alors
    • si , alors

Par exemple, pour , on a .

L'outil ci-dessous liste les mots d'un langage , jusqu'à une certaine longueur. Il permet aussi de comparer deux expressions régulières : utilisez-le pour vérifier vos réponses aux exercices suivants !

(union : | ou +, étoile : *, concaténation : rien)

L(e) sur Σ = {a, b}, mots de longueur ≤ 4 (9 mots) :

εabaabbaaabbbaaaabbbb

Donnez une description en langage naturel de pour l'expression régulière .

contient les mots contenant un nombre pair de a.

Donnez une description en langage naturel de pour l'expression régulière .

contient les mots contenant au moins un a.

Donnez une expression régulière telle que contient les mots contenant exactement un a.

Donnez une expression régulière telle que contient les mots ne contenant jamais deux a consécutifs.

Définition : langages réguliers

Un langage régulier est un langage tel qu'il existe une expression régulière avec .

Est ce que tous les langages sont réguliers ?

Non, il existe des langages qui ne sont pas réguliers. Un premier argument est celui du dénombrement : il existe un nombre dénombrable d'expressions régulières, mais les langages sont des parties d'un ensemble dénombrable (), donc il existe un nombre indénombrable de langages.

On pourra construire des exemples de langages non réguliers plus tard dans le cours.