Langages réguliers et automates finis

Ce document présente les notions fondamentales des langages réguliers et des automates finis, destinées aux étudiants en informatique ou en mathématiques théoriques. Il couvre la définition des langages réguliers, la construction d'automates finis déterministes et non déterministes, ainsi que des exercices illustrant ces concepts.

Langages réguliers

Soit un alphabet fini !.

Les cas de base des langages réguliers sont :

• Ø (le langage vide) est régulier.
• {""} (le langage contenant uniquement le mot vide) est régulier.
• {a} avec a ∈ ! est régulier.

Soient L et K des langages réguliers, alors :

• La concaténation L#K = { l#k | l ∈ L et k ∈ K } est régulière.
• L'union L $ K est régulière.
• La fermeture de Kleene L* = {""} $ {www…w | w ∈ L} est régulière.

Exemple

Soit l'alphabet ! = {0, 1} :

• {1} et {0} sont des langages réguliers.
• La fermeture de Kleene {1}* et {0}* sont régulières.
• La concaténation {1}* # {0} # {1} # {0}* est régulière.

Ce langage correspond à l'ensemble des mots composés d'un nombre arbitraire de 1, suivis de 01, puis d'un nombre arbitraire de 0.

Automates finis

Un automate fini M est défini par la structure M = (Q, !, $, q0, F) où :

• Q est un ensemble fini d'états.
• ! est l'alphabet des symboles d'entrée.
• $ est la relation de transition : Q × ! → Q.
• q0 ∈ Q est l'état initial.
• F ⊆ Q est l'ensemble des états accepteurs.

Propriété importante : si R est un langage régulier, alors il existe un automate fini M tel que L(M) = R.

Exemple : Langage des nombres binaires impairs

Considérons l'alphabet ! = {0, 1} :

• {1} et {0} sont réguliers.
• {1} $ {0} est régulier.
• ({1} $ {0})* est régulier.
• ({1} $ {0})* # {1} est régulier.

Ce langage correspond à l'ensemble des nombres binaires impairs, qui se terminent nécessairement par 1.

Langages finis et non réguliers

1. Tout langage fini est régulier :

• Soit L = {w1, w2, …, wn} un langage fini.
• Chaque mot wi étant une concaténation finie de caractères de !, {wi} est régulier.
• Donc, L = {w1} $ {w2} $ … $ {wn} est régulier.

2. Le langage L = {0n1n | n ≥ 0} n'est pas régulier :

• Supposons par contradiction que L soit régulier.
• Alors il existe un automate fini A = (Q, !, $, q0, F).
• Comme Q est fini, il existe un mot w ∈ L accepté en passant deux fois par le même état q.
• On peut décomposer w en trois parties : 0^k1^k1^2|Q|.
• En "pompant" la boucle, on accepte aussi des mots hors de L, ce qui est une contradiction.

Types d'automates finis

• DFA (Deterministic Finite Automaton) : automate fini déterministe.
• NFA (Nondeterministic Finite Automaton) : automate fini non déterministe.
• "-NFA : NFA avec transitions epsilon (ε-transitions).

Exemple d'automate non déterministe

Construire un NFA acceptant les chaînes qui se terminent par 00 sur l'alphabet ! = {0, 1} :

• États : q0 (initial), q1, q2 (acceptant).
• Transitions :
• q0 --0--> q1
• q1 --0--> q2
• q0 --1--> q0
• q1 --1--> q0
• q2 --0,1--> q2 (boucle)

Conversion entre automates

Déterminisation d'un NFA

Technique : construction par sous-ensembles (subset construction).

Soit un NFA N = (QN, !, $N, q0, FN), on construit un DFA D = (QD, !, $D, {q0}, FD) où :

• QD = ensemble des sous-ensembles de QN.
• FD = {S ⊆ QN | S ∩ FN ≠ Ø}.
• Pour S ⊆ QN et a ∈ !, $D(S, a) = ∪ { $N(p, a) | p ∈ S }.

Suppression des ε-transitions

Soit un "-NFA E = (Q, !, $E, q0, F), on construit un NFA N = (Q, !, $N, q0, F) tel que :

• Pour chaque transition (q, ε, q') dans E, on ajoute (q, ε, q') dans N.
• Si un chemin de q à q' passe uniquement par des ε-transitions, alors on ajoute directement une transition (q, a, q') dans N pour chaque a accessible via ce chemin.

Exemple de déterminisation

Soit un NFA avec états {p, q, r, s} et transitions :

• p --0--> p
• p --0--> q
• q --1--> r
• r --0--> s
• s --1--> p

La construction du DFA donne des états sous forme de sous-ensembles, par exemple :

• {p}
• {p, q}
• {p, q, r, s}
• {p, s}

Les transitions sont déterminées par l'union des transitions des états composants.

Implémentation d'un automate en langage C

Exemple d'automate acceptant des chaînes sur l'alphabet ! = {A, B, C, ..., Z} :

char buffer; // Initialise au 1er caractère de l’input

char next_char() {
  return buffer;
}

void read_next() {
  buffer = getchar();
}

bool alpha(char c) {
  return (c >= 'A' && c <= 'Z');
}

int automate() {
  int state = 8;
  char c;
  while (true) {
    switch (state) {
      case 8:
        if (next_char() == 'W') state = 4;
        else if (next_char() == 'I') state = 9;
        else if (alpha(c)) state = 3;
        else state = 8;
        read_next();
        break;
      case 4:
        // ...
      case 2:
        if (alpha(c)) state = 3;
        else return 2; // Pas de read_next!
        read_next();
        break;
    }
  }
}

Glossaire des termes clés

• Alphabet (!) : ensemble fini de symboles utilisés pour construire des mots.
• Langage régulier : langage construit à partir de l'alphabet par les opérations de base (vide, mot vide, singleton) et fermé par concaténation, union et fermeture de Kleene.
• Automate fini (M) : modèle computationnel défini par un ensemble fini d'états, un alphabet, une fonction de transition, un état initial et des états accepteurs.
• DFA (Deterministic Finite Automaton) : automate fini où pour chaque état et symbole, il existe une unique transition.
• NFA (Nondeterministic Finite Automaton) : automate fini où plusieurs transitions sont possibles pour un état et un symbole.
• ε-transition : transition pouvant être franchie sans lire de symbole d'entrée.
• Fermeture de Kleene (L*) : ensemble de toutes les concaténations finies de mots de L, incluant le mot vide.
• Déterminisation : processus de transformation d'un NFA en DFA équivalent.

Points clés à retenir

• Les langages réguliers sont construits à partir de langages de base par concaténation, union et fermeture de Kleene.
• Tout langage régulier peut être reconnu par un automate fini.
• Les automates finis peuvent être déterministes (DFA) ou non déterministes (NFA), avec ou sans ε-transitions.
• La déterminisation d'un NFA est possible via la construction par sous-ensembles.
• Les langages non réguliers, comme {0n1n | n ≥ 0}, ne peuvent pas être reconnus par un automate fini.
• Les automates peuvent être implémentés en langage C en utilisant une machine à états et un traitement des caractères d'entrée.