Langages formels et automates

Un langage formel est un ensemble de chaînes de caractères (ou "mots") construites à partir d'un ensemble fini de symboles appelé alphabet. Contrairement aux langages naturels (comme le français ou l'anglais) qui sont ambigus et évolutifs, les langages formels sont définis avec une précision mathématique rigoureuse. Ils sont le fondement de l'informatique théorique et ont des applications pratiques dans des domaines comme la compilation, la conception de circuits et l'analyse de texte.

• Alphabet ($\Sigma$) : C'est un ensemble fini et non vide de symboles ou de caractères.
  • Exemples :
    • $\Sigma = \{0, 1\}$ (alphabet binaire)
    • $\Sigma = \{a, b, c\}$
    • $\Sigma = \{\text{début}, \text{fin}\}$
• Mot (ou chaîne de caractères) : C'est une séquence finie de symboles de l'alphabet.
  • Exemples avec $\Sigma = \{0, 1\}$ : 010, 1111, 0, epsilon ($\epsilon$ ou $\lambda$) qui représente le mot vide (de longueur 0).
  • La longueur d'un mot $w$, notée $|w|$, est le nombre de symboles qu'il contient. Par exemple, $|010| = 3$, $|\epsilon| = 0$.
• Langage ($L$) : C'est un ensemble de mots sur un alphabet donné. Un langage est donc un sous-ensemble de $\Sigma^*$, où $\Sigma^*$ représente l'ensemble de tous les mots possibles (y compris le mot vide) que l'on peut former avec les symboles de $\Sigma$.
  • Exemples :
    • $L_1 = \{0, 00, 000, \dots\}$ (tous les mots composés uniquement de '0') sur $\Sigma = \{0\}$.
    • $L_2 = \{w \mid w \text{ est un mot binaire de longueur paire}\}$ sur $\Sigma = \{0, 1\}$.
    • $L_3 = \{\text{bonjour}, \text{salut}\}$ sur $\Sigma = \{a-z\}$.

Tout comme on peut effectuer des opérations sur des ensembles, on peut aussi manipuler les langages avec des opérations spécifiques.

• Union ($L_1 \cup L_2$) : L'ensemble de tous les mots qui appartiennent à $L_1$ ou à $L_2$ (ou aux deux).
  • Exemple : Si $L_1 = \{a, ab\}$ et $L_2 = \{ab, b\}$, alors $L_1 \cup L_2 = \{a, ab, b\}$.
• Intersection ($L_1 \cap L_2$) : L'ensemble de tous les mots qui appartiennent à la fois à $L_1$ et à $L_2$.
  • Exemple : Si $L_1 = \{a, ab\}$ et $L_2 = \{ab, b\}$, alors $L_1 \cap L_2 = \{ab\}$.
• Complémentaire ($\overline{L}$) : L'ensemble de tous les mots sur $\Sigma^*$ qui n'appartiennent pas à $L$.
  • Exemple : Si $\Sigma = \{a, b\}$ et $L = \{a, aa\}$, alors $\overline{L}$ contient tous les mots comme $b, ab, ba, aaa, \dots$ sauf $a$ et $aa$.
• Concaténation ($L_1 L_2$) : L'ensemble de tous les mots formés en prenant un mot de $L_1$ et en lui attachant un mot de $L_2$. Formellement, $L_1 L_2 = \{w_1 w_2 \mid w_1 \in L_1 \text{ et } w_2 \in L_2\}$.
  • Exemple : Si $L_1 = \{a, b\}$ et $L_2 = \{0, 1\}$, alors $L_1 L_2 = \{a0, a1, b0, b1\}$.
• Itération (Étoile de Kleene, $L^*$) : L'ensemble de tous les mots que l'on peut former en concaténant zéro ou plusieurs mots de $L$. Cela inclut le mot vide ($\epsilon$).
  • $L^* = \{\epsilon\} \cup L \cup LL \cup LLL \cup \dots$
  • Exemple : Si $L = \{a\}$, alors $L^* = \{\epsilon, a, aa, aaa, \dots\}$.
  • Si $L = \{ab\}$, alors $L^* = \{\epsilon, ab, abab, ababab, \dots\}$.
  • L'opérateur plus de Kleene ($L^+$) est similaire mais exclut le mot vide : $L^+ = L \cup LL \cup LLL \cup \dots$.

La Hiérarchie de Chomsky est une classification des langages formels selon leur complexité et le type d'automate nécessaire pour les reconnaître ou les générer. Elle a été proposée par Noam Chomsky en 1956. Cette hiérarchie est fondamentale en informatique théorique car elle permet de comprendre les limitations et les capacités des différents modèles de calcul.

Il existe quatre principaux types de langages, du plus simple au plus complexe :

1. Langages de Type 3 (Langages Réguliers) :
   • Ce sont les langages les plus simples.
   • Ils peuvent être reconnus par des automates finis (AFD ou AFN) et décrits par des expressions régulières.
   • Exemples : tout mot binaire qui commence par 0, une adresse e-mail valide (simplifiée), des nombres entiers.
2. Langages de Type 2 (Langages Hors Contexte ou Context-Free) :
   • Plus complexes que les langages réguliers.
   • Ils peuvent être reconnus par des automates à pile.
   • Ils sont décrits par des grammaires hors contexte (utilisées pour définir la syntaxe de la plupart des langages de programmation).
   • Exemples : les expressions arithmétiques bien parenthésées, le langage de programmation Python (sa syntaxe).
3. Langages de Type 1 (Langages Contextuels ou Context-Sensitive) :
   • Plus complexes que les langages hors contexte.
   • Ils peuvent être reconnus par des automates linéaires bornés.
   • Ils sont décrits par des grammaires contextuelles.
   • Moins utilisés en pratique directe que les précédents.
4. Langages de Type 0 (Langages Récursivement Énumérables) :
   • Les langages les plus généraux de la hiérarchie.
   • Ils peuvent être reconnus par des machines de Turing (le modèle de calcul le plus puissant).
   • Ces langages incluent tous les problèmes que l'on peut résoudre avec un algorithme.

Pour le programme de NSI, nous nous concentrerons principalement sur les langages réguliers et les outils pour les manipuler : les expressions régulières et les automates finis.

Une expression régulière (ER) est une séquence de caractères qui définit un modèle de recherche. C'est une notation concise pour décrire les langages réguliers. On les utilise pour trouver des motifs dans du texte, valider des entrées ou analyser des données.

Les expressions régulières sont construites à l'aide de symboles de base et d'opérateurs :

• Symboles de base :
  • Tout caractère de l'alphabet ($\Sigma$). Par exemple, a, 0, #.
  • Le mot vide ($\epsilon$ ou "" dans certaines syntaxes), qui représente un langage ne contenant que le mot vide.
• Opérateurs :
  • Concaténation (juxtaposition) : $R_1 R_2$ décrit le langage $L(R_1)L(R_2)$. Souvent implicite.
    • Exemple : L'ER ab décrit le langage $\{ab\}$.
  • Union (ou alternance) : $R_1 | R_2$ (ou $R_1 + R_2$) décrit le langage $L(R_1) \cup L(R_2)$.
    • Exemple : L'ER a|b décrit le langage $\{a, b\}$.
  • Étoile de Kleene (répétition zéro ou plus) : $R^*$ décrit le langage $L(R)^*$.
    • Exemple : L'ER a* décrit le langage $\{\epsilon, a, aa, aaa, \dots\}$.
  • Répétition une ou plus ($+$) : $R^+$ est un raccourci pour $R R^*$.
    • Exemple : L'ER a+ décrit le langage $\{a, aa, aaa, \dots\}$.
  • Optionnel (?) : $R?$ est un raccourci pour $R | \epsilon$.
    • Exemple : L'ER colou?r décrit les langages color et colour.
• Priorité des opérateurs :
  1. Étoile de Kleene (*, +, ?)
  2. Concaténation (implicite)
  3. Union (|)
  • Les parenthèses () peuvent être utilisées pour modifier la priorité ou pour grouper des expressions.
    • Exemple : (ab)* signifie "zéro ou plusieurs répétitions de ab" ($\{\epsilon, ab, abab, \dots\}$), tandis que ab* signifie "un a suivi de zéro ou plusieurs b" ($\{a, ab, abb, \dots\}$).

Construire une expression régulière consiste à combiner ces opérateurs et symboles pour décrire précisément l'ensemble des mots que l'on souhaite reconnaître.

Exemples simples de construction :

• Langage des mots sur $\{0, 1\}$ qui commencent par 0 :
  • L'ER serait 0(0|1)*.
  • Explication : un 0 obligatoire, suivi de n'importe quelle séquence de 0 ou 1 (zéro ou plusieurs fois).
• Langage des mots sur $\{a, b\}$ qui contiennent un nombre pair de a (simplifié) :
  • C'est plus complexe, mais pour un exemple simple : (b*ab*ab*)*.
  • Explication : zéro ou plusieurs répétitions de "n'importe quel nombre de b, suivi d'un a, suivi de n'importe quel nombre de b, suivi d'un a, suivi de n'importe quel nombre de b".
• Langage des nombres entiers positifs (sans signe) sur $\{0-9\}$ :
  • L'ER serait [1-9][0-9]* | 0.
  • Explication : un chiffre de 1 à 9 suivi de zéro ou plusieurs chiffres de 0 à 9, OU simplement le chiffre 0. (Note : [0-9] est un raccourci pour (0|1|2|3|4|5|6|7|8|9)).

Reconnaissance de motifs : Les expressions régulières sont très efficaces pour reconnaître des motifs spécifiques dans des chaînes de caractères.

• Pour trouver toutes les adresses e-mail (simplifié) : [a-zA-Z0-9.]+@[a-zA-Z0-9.]+\.[a-zA-Z]{2,}.
• Pour valider un numéro de téléphone (format XXX-XX-XX-XX-XX) : \d{3}-\d{2}-\d{2}-\d{2}-\d{2}. (\d est un raccourci pour [0-9]).

Utilisation de parenthèses : Les parenthèses sont cruciales pour grouper des sous-expressions et contrôler la portée des opérateurs.

• a(b|c) reconnaîtra ab ou ac.
• (ab)+ reconnaîtra ab, abab, ababab, etc. Si on avait ab+, cela reconnaîtrait ab, abb, abbb, etc.

Chaque expression régulière $R$ décrit un langage formel, noté $L(R)$. Ce langage est l'ensemble de tous les mots qui correspondent au modèle défini par $R$. Les expressions régulières sont un moyen puissant et concis de définir des langages réguliers.

• Langage engendré par une expression régulière : L'ER $R$ engendre (ou décrit) le langage $L(R)$.
  • Exemple : $L( (0|1)^* ) = \Sigma^*$ où $\Sigma = \{0, 1\}$, c'est-à-dire tous les mots binaires possibles.
• Équivalence entre expressions : Deux expressions régulières $R_1$ et $R_2$ sont équivalentes si elles décrivent le même langage : $L(R_1) = L(R_2)$.
  • Exemple : (a|b)* est équivalent à (a*b*)*.
• Applications pratiques (recherche de texte) :
  • Éditeurs de texte et IDE : Utilisation pour la recherche et le remplacement de texte (ex: Ctrl+F avec "regex").
  • Outils en ligne de commande (grep, sed, awk) : Filtrage de fichiers texte, extraction d'informations.
  • Validation de données : Vérifier si une entrée utilisateur (adresse e-mail, numéro de téléphone, date, mot de passe) respecte un format spécifique.
  • Analyse syntaxique (lexicale) dans les compilateurs : Les expressions régulières sont utilisées pour définir les "tokens" (mots-clés, identificateurs, opérateurs) d'un langage de programmation.

Un Automate Fini Déterministe (AFD) est un modèle de calcul abstrait qui permet de reconnaître des langages réguliers. C'est une machine simple qui peut se trouver dans un nombre fini d'états et qui passe d'un état à l'autre en fonction des symboles lus en entrée. Le terme "déterministe" signifie que pour chaque état et chaque symbole d'entrée, il y a toujours une et une seule transition possible vers un état suivant.

Un AFD est formellement défini par un quintuplet $(Q, \Sigma, \delta, q_0, F)$ où :

• $Q$ : Un ensemble fini d'états.
• $\Sigma$ : L'alphabet d'entrée, un ensemble fini de symboles.
• $\delta$ : La fonction de transition, une fonction qui prend un état et un symbole d'entrée et retourne un unique état suivant. $\delta: Q \times \Sigma \to Q$.
• $q_0$ : L'état initial, un état unique de $Q$ où l'automate commence son exécution.
• $F$ : L'ensemble des états finaux (ou acceptants), un sous-ensemble de $Q$. Si l'automate termine la lecture d'un mot dans un de ces états, le mot est accepté.

Représentation graphique (graphe d'états) : Les AFD sont souvent représentés par un graphe orienté :

• Les états sont des nœuds (cercles).
• L'état initial est indiqué par une flèche entrante sans origine.
• Les états finaux sont représentés par des doubles cercles.
• Les transitions sont des flèches étiquetées par les symboles de l'alphabet.

Exemple d'AFD : Reconnaître les mots binaires qui contiennent un nombre pair de '1'.

• $Q = \{q_0, q_1\}$ (où $q_0$ représente un nombre pair de '1', $q_1$ un nombre impair).
• $\Sigma = \{0, 1\}$.
• $q_0$ est l'état initial.
• $F = \{q_0\}$ (car on veut un nombre pair de '1').
• $\delta$ :
  • $\delta(q_0, 0) = q_0$ (lire '0' ne change pas la parité des '1')
  • $\delta(q_0, 1) = q_1$ (lire '1' passe de pair à impair)
  • $\delta(q_1, 0) = q_1$ (lire '0' ne change pas la parité)
  • $\delta(q_1, 1) = q_0$ (lire '1' passe d'impair à pair)

        0
    ┌─────┐
    │     │
  ┌─┴─┐   │   ┌─┴─┐
  │q0 │<──┼───>│q1 │
  └─┬─┘   │   └─┬─┘
    │     │     │
    └─────┘     │
        1       1

(Flèche entrante sur q0 pour indiquer l'état initial, double cercle sur q0 pour indiquer l'état final)

Le fonctionnement d'un AFD consiste à lire un mot symbole par symbole et à passer d'un état à l'autre selon la fonction de transition.

1. Initialisation : L'automate commence dans l'état initial $q_0$.
2. Lecture du mot : Pour chaque symbole $s$ du mot d'entrée $w$, de gauche à droite :
   • Si l'automate est dans l'état courant $q_c$ et lit le symbole $s$, il passe à l'état suivant $q_n = \delta(q_c, s)$. L'état courant devient $q_n$.
3. Décision (Acceptation ou rejet) : Une fois que tous les symboles du mot ont été lus :
   • Si l'état final de l'automate (l'état courant après lecture du dernier symbole) est un état de $F$ (un état final), alors le mot est accepté.
   • Sinon, le mot est rejeté.

Exemple avec l'AFD précédent (nombre pair de '1') :

• Mot 01010 :

  1. Commence en $q_0$.
  2. Lit 0 : $\delta(q_0, 0) = q_0$. (État courant $q_0$)
  3. Lit 1 : $\delta(q_0, 1) = q_1$. (État courant $q_1$)
  4. Lit 0 : $\delta(q_1, 0) = q_1$. (État courant $q_1$)
  5. Lit 1 : $\delta(q_1, 1) = q_0$. (État courant $q_0$)
  6. Lit 0 : $\delta(q_0, 0) = q_0$. (État courant $q_0$)
  • Fin du mot. L'état final est $q_0$, qui est un état acceptant. Donc, 01010 est accepté. (Il contient deux '1', ce qui est pair).

• Mot 1011 :

  1. Commence en $q_0$.
  2. Lit 1 : $\delta(q_0, 1) = q_1$.
  3. Lit 0 : $\delta(q_1, 0) = q_1$.
  4. Lit 1 : $\delta(q_1, 1) = q_0$.
  5. Lit 1 : $\delta(q_0, 1) = q_1$.
  • Fin du mot. L'état final est $q_1$, qui n'est pas un état acceptant. Donc, 1011 est rejeté. (Il contient trois '1', ce qui est impair).

Le langage reconnu par un AFD $M$, noté $L(M)$, est l'ensemble de tous les mots acceptés par $M$. Les langages reconnaissables par un AFD sont précisément les langages réguliers.

• Exemples de langages reconnaissables par des AFD :

  • Tous les mots binaires commençant par 0.
  • Tous les mots sur $\{a, b\}$ qui ne contiennent pas la sous-chaîne ab.
  • Tous les mots qui sont des identifiants valides en C (commencent par une lettre ou _, suivis de lettres, chiffres ou _).
  • Les nombres entiers (positifs, négatifs, ou zéro).

• Limites des AFD :

  • Malgré leur utilité, les AFD ont des limites. Ils ne peuvent pas reconnaître tous les langages.
  • Un AFD ne peut pas "compter" de manière arbitrairement grande. Par exemple, il ne peut pas reconnaître le langage des mots de la forme $a^n b^n$ (c'est-à-dire ab, aabb, aaabbb, etc., où il y a le même nombre de a que de b). En effet, pour cela, il faudrait mémoriser le nombre de a lus avant de lire les b, ce qui nécessiterait un nombre infini d'états si $n$ peut être arbitrairement grand.
  • Ils ne peuvent pas gérer des structures imbriquées de manière arbitrairement profonde (comme les parenthèses équilibrées dans une expression mathématique). Pour ces langages, on a besoin de modèles de calcul plus puissants, comme les automates à pile.

Un Automate Fini Non Déterministe (AFN) est une généralisation des AFD. La principale différence est qu'un AFN peut avoir plusieurs chemins possibles pour un état et un symbole d'entrée donné. Le terme "non déterministe" signifie qu'il n'y a pas toujours un unique état suivant défini.

Un AFN est formellement défini par un quintuplet $(Q, \Sigma, \delta, q_0, F)$ où :

• $Q$, $\Sigma$, $q_0$, $F$ sont définis comme pour un AFD.
• $\delta$ : La fonction de transition est différente. Elle prend un état et un symbole d'entrée ($\Sigma \cup \{\epsilon\}$) et retourne un ensemble d'états possibles. $\delta: Q \times (\Sigma \cup \{\epsilon\}) \to \mathcal{P}(Q)$, où $\mathcal{P}(Q)$ est l'ensemble des sous-ensembles de $Q$.

Principales différences et caractéristiques :

• Transitions multiples : Pour un état $q$ et un symbole $s$, $\delta(q, s)$ peut contenir zéro, un ou plusieurs états.
• Transitions epsilon ($\epsilon$-transitions) : Un AFN peut changer d'état sans lire de symbole d'entrée. Ces transitions sont étiquetées par $\epsilon$ (ou $\lambda$). Elles permettent de "sauter" d'un état à l'autre gratuitement.
• Plusieurs états initiaux possibles : Bien que la définition formelle utilise souvent un seul $q_0$, on peut facilement adapter la définition pour permettre plusieurs états initiaux, ou considérer qu'un état initial unique peut avoir des $\epsilon$-transitions vers d'autres états.
• Représentation graphique : Similaire à celle des AFD, mais les flèches peuvent se ramifier (plusieurs flèches sortant d'un état avec la même étiquette) et il peut y avoir des flèches étiquetées $\epsilon$.

Exemple d'AFN : Reconnaître les mots binaires qui contiennent la sous-chaîne 101.

• $Q = \{q_0, q_1, q_2, q_3\}$
• $\Sigma = \{0, 1\}$
• $q_0$ est l'état initial.
• $F = \{q_3\}$
• $\delta$ :
  • $\delta(q_0, 0) = \{q_0\}$
  • $\delta(q_0, 1) = \{q_0, q_1\}$ (non-déterminisme ici : on peut rester en $q_0$ ou commencer à chercher 101)
  • $\delta(q_1, 0) = \{q_2\}$
  • $\delta(q_1, 1) = \{q_1\}$ (On a trouvé un 1, on peut en trouver d'autres avant le 0)
  • $\delta(q_2, 0) = \{q_0\}$
  • $\delta(q_2, 1) = \{q_3\}$
  • $\delta(q_3, 0) = \{q_3\}$
  • $\delta(q_3, 1) = \{q_3\}$

      0,1
    ┌─────┐
    │     │
  ┌─┴─┐   │   ┌─┴─┐   ┌─┴─┐   ┌─┴─┐
  │q0 │<──┼───>│q1 │───>│q2 │───>│q3 │
  └─┬─┘   │   └─┬─┘   └─┬─┘   └─┬─┘
    │     │     │     0   1     │
    └─────┘     │                 │
        1       1               0,1

(Flèche entrante sur q0, double cercle sur q3)

Le fonctionnement d'un AFN est basé sur l'exploration de tous les chemins possibles. Un mot est accepté si au moins un des chemins possibles mène à un état final après lecture complète du mot.

1. Initialisation : L'automate commence dans l'état initial $q_0$.
2. Gestion des $\epsilon$-transitions : Avant de lire le premier symbole, et après chaque symbole lu, l'automate peut se déplacer vers n'importe quel état accessible via une ou plusieurs $\epsilon$-transitions. L'ensemble de tous les états accessibles à partir de l'état courant (y compris l'état courant lui-même) via des $\epsilon$-transitions est appelé la $\epsilon$-fermeture.
3. Lecture du mot : Pour chaque symbole $s$ du mot d'entrée $w$, de gauche à droite :
   • Si l'automate est dans un ensemble d'états $Q_{courant}$, et lit le symbole $s$, il passe à l'ensemble d'états $Q_{suivant}$ qui est l'union de tous les $\delta(q, s)$ pour chaque $q \in Q_{courant}$, puis applique la $\epsilon$-fermeture à cet ensemble. L'ensemble des états courants devient $Q_{suivant}$.
4. Décision (Acceptation ou rejet) : Une fois que tous les symboles du mot ont été lus :
   • Si l'ensemble des états courants contient au moins un état de $F$ (un état final), alors le mot est accepté.
   • Sinon, le mot est rejeté.

Exemple avec l'AFN précédent (contient 101) :

• Mot 01101 :
  1. Commence en $\{q_0\}$. $\epsilon$-fermeture de $\{q_0\}$ est $\{q_0\}$.
  2. Lit 0 :
     • De $q_0$ avec 0 va à $\delta(q_0, 0) = \{q_0\}$.
     • Ensemble d'états : $\{q_0\}$. $\epsilon$-fermeture de $\{q_0\}$ est $\{q_0\}$.
  3. Lit 1 :
     • De $q_0$ avec 1 va à $\delta(q_0, 1) = \{q_0, q_1\}$.
     • Ensemble d'états : $\{q_0, q_1\}$. $\epsilon$-fermeture de $\{q_0, q_1\}$ est $\{q_0, q_1\}$.
  4. Lit 1 :
     • De $q_0$ avec 1 va à $\{q_0, q_1\}$.
     • De $q_1$ avec 1 va à $\{q_1\}$.
     • Union : $\{q_0, q_1\}$. $\epsilon$-fermeture de $\{q_0, q_1\}$ est $\{q_0, q_1\}$.
  5. Lit 0 :
     • De $q_0$ avec 0 va à $\{q_0\}$.
     • De $q_1$ avec 0 va à $\{q_2\}$.
     • Union : $\{q_0, q_2\}$. $\epsilon$-fermeture de $\{q_0, q_2\}$ est $\{q_0, q_2\}$.
  6. Lit 1 :
     • De $q_0$ avec 1 va à $\{q_0, q_1\}$.
     • De $q_2$ avec 1 va à $\{q_3\}$.
     • Union : $\{q_0, q_1, q_3\}$. $\epsilon$-fermeture de $\{q_0, q_1, q_3\}$ est $\{q_0, q_1, q_3\}$.
  • Fin du mot. L'ensemble d'états $\{q_0, q_1, q_3\}$ contient $q_3$, qui est un état final. Donc, 01101 est accepté.

Le Théorème de Rabin et Scott (1959) est un résultat fondamental : tout langage reconnaissable par un AFN est aussi reconnaissable par un AFD, et vice-versa. En d'autres termes, les AFN et les AFD ont la même puissance de reconnaissance. Ils reconnaissent tous deux exactement la classe des langages réguliers.

• Intérêt des AFN :

  • Les AFN sont souvent plus simples à construire pour décrire un langage donné (surtout à partir d'expressions régulières). Le non-déterminisme permet une description plus compacte et intuitive.
  • Ils sont une étape intermédiaire cruciale dans la conversion d'une expression régulière vers un AFD.

• Construction de l'AFD équivalent (méthode des sous-ensembles) : Bien qu'un AFN puisse être plus simple à construire, les AFD sont plus faciles à implémenter dans la pratique (pas besoin d'explorer plusieurs chemins simultanément). Il existe un algorithme pour convertir tout AFN en un AFD équivalent :

  1. Les états du nouvel AFD sont des ensembles d'états de l'AFN original.
  2. L'état initial de l'AFD est l'$\epsilon$-fermeture de l'état initial de l'AFN.
  3. Pour chaque état de l'AFD (qui est un ensemble d'états de l'AFN) et chaque symbole de l'alphabet, on calcule la transition :
     • On prend tous les états de l'AFN dans l'ensemble courant.
     • Pour chaque état de l'AFN, on trouve tous les états accessibles via ce symbole.
     • On prend l'union de tous ces états et on applique l'$\epsilon$-fermeture. Cet ensemble résultant est le nouvel état de l'AFD.
  4. Un état de l'AFD est final si l'ensemble d'états de l'AFN qu'il représente contient au moins un état final de l'AFN original.

  Cette méthode garantit la construction d'un AFD équivalent. Le nombre d'états de l'AFD résultant peut être exponentiellement plus grand que celui de l'AFN ($2^{|Q_{AFN}|}$), mais il est toujours fini.

Le Théorème de Kleene est un pilier de l'informatique théorique. Il établit une équivalence fondamentale entre trois concepts distincts qui décrivent tous la même classe de langages : les langages réguliers.

Le théorème de Kleene stipule que les propositions suivantes sont équivalentes :

1. Un langage est régulier.
2. Un langage est reconnaissable par un Automate Fini Déterministe (AFD).
3. Un langage est reconnaissable par un Automate Fini Non Déterministe (AFN).
4. Un langage peut être décrit par une Expression Régulière (ER).

Ce théorème est crucial car il signifie que si vous pouvez décrire un motif avec une expression régulière, vous pouvez construire un automate fini pour le reconnaître, et vice-versa. Cela fournit une flexibilité énorme pour la conception d'outils de traitement de texte et de langages de programmation.

La conversion d'une expression régulière en un AFN est souvent la première étape pour obtenir un AFD, car elle est plus directe. L'algorithme de Thompson est une méthode standard pour cette conversion. Il est basé sur la construction par composition : pour chaque opérateur d'une ER, il existe une construction AFN correspondante.

Principes de l'algorithme de Thompson :

• Cas de base (symbole unique a) : Un AFN simple avec deux états, un initial et un final, et une transition a entre eux.

  (q_i) --a--> (q_f)
  

• Cas du mot vide ($\epsilon$) : Un AFN avec deux états, un initial et un final, et une transition $\epsilon$ entre eux.

  (q_i) --eps--> (q_f)
  

• Union ($R_1 | R_2$) : On crée un nouvel état initial et un nouvel état final. L'état initial a des $\epsilon$-transitions vers les états initiaux des AFN de $R_1$ et $R_2$. Les états finaux des AFN de $R_1$ et $R_2$ ont des $\epsilon$-transitions vers le nouvel état final.

         eps
       /-----\
  (q_i)--eps--> AFN(R1) --eps--> (q_f)
       \-----/
         eps
       \-----\
        AFN(R2)
  

• Concaténation ($R_1 R_2$) : On connecte l'état final de l'AFN de $R_1$ à l'état initial de l'AFN de $R_2$ avec une $\epsilon$-transition.

  AFN(R1) --eps--> AFN(R2)
  

• Étoile de Kleene ($R^*$) : On crée un nouvel état initial et un nouvel état final. L'état initial a une $\epsilon$-transition vers l'état final (pour le cas du mot vide). L'état initial a aussi une $\epsilon$-transition vers l'état initial de l'AFN de $R$. L'état final de l'AFN de $R$ a une $\epsilon$-transition vers son propre état initial (pour la répétition) et une autre $\epsilon$-transition vers le nouvel état final global.

       /--eps--\
  (q_i)--eps--> AFN(R) --eps--> (q_f)
        \--eps--/
  

En appliquant ces règles de manière récursive, on peut construire un AFN pour n'importe quelle expression régulière.

La conversion inverse, d'un AFD vers une expression régulière, est également possible, bien que souvent plus complexe à réaliser manuellement. L'algorithme de McNaughton-Yamada (ou la méthode de l'élimination des états) est la technique la plus courante.

Principes de l'algorithme de McNaughton-Yamada :

L'idée est d'éliminer les états un par un, en "absorbant" leurs transitions dans les étiquettes des transitions restantes, qui deviennent alors des expressions régulières.

1. Préparation : S'assurer qu'il n'y a qu'un seul état initial et un seul état final. Si ce n'est pas le cas, créer un nouvel état initial avec des $\epsilon$-transitions vers les anciens, et un nouvel état final avec des $\epsilon$-transitions depuis les anciens. Ajouter des $\epsilon$-transitions si nécessaire pour des boucles.
2. Itération : Tant qu'il y a plus de deux états (l'état initial et l'état final), choisir un état $q_{eliminer}$ à supprimer. Pour chaque paire d'états $(q_i, q_j)$ tels que $q_i \to q_{eliminer}$ et $q_{eliminer} \to q_j$ existent :
   • Modifier la transition directe de $q_i$ à $q_j$ (ou créer une si elle n'existe pas) en la remplaçant par une expression régulière qui représente tous les chemins possibles de $q_i$ à $q_j$ passant par $q_{eliminer}$.
   • La formule générale pour une transition $q_i \xrightarrow{R_{ik}} q_k \xrightarrow{R_{kk}^*} q_k \xrightarrow{R_{kj}} q_j$ est $R_{ik} (R_{kk})^* R_{kj}$.
3. Résultat : Une fois tous les états intermédiaires éliminés, il ne reste qu'une transition unique de l'état initial vers l'état final, étiquetée par l'expression régulière du langage reconnu.

Exemple simple d'élimination d'états (sans rentrer dans les détails calculatoires) : Si on a un AFD avec des états $q_1, q_2, q_3$ et des transitions $q_1 \xrightarrow{a} q_2$, $q_2 \xrightarrow{b} q_2$, $q_2 \xrightarrow{c} q_3$. Si on élimine $q_2$, la transition de $q_1$ à $q_3$ deviendrait $a b^* c$.

Ces conversions montrent la profonde interconnexion et l'équivalence pratique entre les différentes façons de décrire les langages réguliers.

L'analyse lexicale, souvent appelée tokenisation, est la première phase d'un compilateur ou d'un interpréteur. Son rôle est de lire le code source (une chaîne de caractères) et de le transformer en une séquence de tokens (unités lexicales). Chaque token représente une unité significative du langage de programmation, comme un mot-clé, un identifiant, un opérateur, un littéral numérique, etc.

• Rôle des expressions régulières : Les expressions régulières sont utilisées pour définir la structure de chaque type de token.
  • Exemple :
    • Un identifiant : [a-zA-Z_][a-zA-Z0-9_]* (commence par lettre ou _, suivi de lettres, chiffres ou _).
    • Un entier : [0-9]+ (une ou plusieurs occurrences d'un chiffre).
    • Un opérateur + : \+.
    • Un mot-clé if : if.
• Rôle des automates finis : Un automate fini (généralement un AFD, construit à partir des expressions régulières des tokens) est utilisé pour effectuer la reconnaissance des tokens. Le "lexeur" ou "scanner" du compilateur est essentiellement un automate fini. Il lit le code source et, à chaque fois qu'il reconnaît un motif correspondant à une ER de token, il émet ce token et continue.
• Exemples de lexèmes :
  • Code source : if (x == 0) { y = 1; }
  • Tokens générés :
    • IF (mot-clé)
    • ( (parenthèse ouvrante)
    • IDENTIFIER (x)
    • OPERATOR_EQUAL (==)
    • NUMBER (0)
    • ) (parenthèse fermante)
    • { (accolade ouvrante)
    • IDENTIFIER (y)
    • OPERATOR_ASSIGN (=)
    • NUMBER (1)
    • ; (point-virgule)
    • } (accolade fermante)

C'est l'une des applications les plus courantes et visibles des expressions régulières pour le grand public.

• Expressions régulières dans les éditeurs de texte : La fonction "rechercher et remplacer" avancée de la plupart des éditeurs de texte (VS Code, Sublime Text, Notepad++, etc.) utilise les expressions régulières. Cela permet de rechercher des motifs bien plus complexes qu'une simple chaîne de caractères.
  • Exemple : Rechercher toutes les lignes qui commencent par // (commentaires) : ^//.* (où ^ signifie début de ligne et . tout caractère, * zéro ou plus).
• Outils comme grep : grep (Global Regular Expression Print) est un utilitaire en ligne de commande puissant, présent sur les systèmes Unix/Linux, qui permet de rechercher des motifs (expressions régulières) dans des fichiers ou des flux de texte.
  • Exemple : grep -r "erreur" /var/log (recherche récursivement le mot "erreur" dans tous les fichiers sous /var/log).
• Validation de données (formulaires) : Les expressions régulières sont massivement utilisées pour valider les entrées utilisateur dans les formulaires web ou toute autre application.
  • Valider un format d'adresse e-mail.
  • Vérifier la force d'un mot de passe (doit contenir majuscule, minuscule, chiffre, symbole).
  • Valider un code postal, un numéro de sécurité sociale, un numéro de carte de crédit.
• Traitement de texte et extraction d'informations : Dans les scripts (Python, Perl, JavaScript, etc.), les ER sont utilisées pour analyser des logs, extraire des données spécifiques de documents non structurés, ou reformater du texte.

Les langages formels et les automates sont également utilisés pour modéliser le comportement de systèmes, notamment les protocoles de communication.

• Description d'états et transitions : Un protocole de communication peut être vu comme une séquence d'états et de transitions. Par exemple, un serveur web passe par différents états (attente de connexion, réception de requête, envoi de réponse, fermeture de connexion). Chaque événement (réception d'un paquet, timeout) déclenche une transition vers un nouvel état.
  • Un automate fini est un outil idéal pour modéliser ces séquences d'états et de transitions.
• Vérification de propriétés : En modélisant un protocole avec un automate, il est possible de vérifier formellement certaines propriétés, telles que :
  • Est-ce que le protocole peut atteindre un état bloqué ?
  • Est-ce que tous les messages sont traités correctement ?
  • Est-ce que le protocole peut se terminer correctement ?
  • Les techniques de model checking utilisent des automates pour vérifier la correction de systèmes critiques.
• Exemples simples de protocoles :
  • Protocole d'établissement de connexion TCP (Three-way handshake) : Peut être modélisé par un AFD simple avec des états comme CLOSED, SYN_SENT, ESTABLISHED, FIN_WAIT_1, etc., et des transitions basées sur l'envoi/réception de paquets SYN, ACK, FIN.
  • Commande d'un distributeur automatique : Les états pourraient être IDLE, COIN_INSERTED, PRODUCT_SELECTED, DELIVERED_CHANGE_RETURNED. Les transitions sont déclenchées par l'insertion de pièces, la sélection de produits, etc.

Ces applications démontrent la polyvalence et l'importance des langages formels et des automates, allant de la conception de langages de programmation à la sécurité des communications, en passant par le traitement quotidien des données.