Concepts Fondamentaux des Automates et Langages Formels

Concepts Clés en Théorie des Automates et Langages

Automate Fini Non Déterministe (AFND)

Un automate fini non déterministe est un ensemble d'états et de transitions d'un état à un autre, basées sur des symboles pris à partir d'un alphabet. Il peut avoir plusieurs transitions possibles pour un même symbole d'entrée depuis un état donné, ou aucune.

Langage Formel

Un langage formel est un ensemble de mots (ou chaînes de caractères) de longueur finie, formés à partir d'un alphabet fini. Chaque mot du langage est une séquence valide de symboles selon des règles spécifiques.

Expression Régulière

Une expression régulière est une méthode concise pour représenter les langages réguliers en utilisant les caractères de l'alphabet qui définissent le langage. Elles sont largement utilisées pour la recherche de motifs et la validation de texte.

Concaténation

La concaténation est l'opération qui consiste à combiner des caractères ou des chaînes de caractères. Elle permet de former une nouvelle chaîne en plaçant une chaîne à la suite d'une autre.

Exemples de concaténation :

• 'Z' concaténé avec '132' donne "Z132"
• '456' concaténé avec 'AB' donne "456AB"
• 'Z' concaténé avec 'A' donne "ZA"

Alphabet

Un alphabet est un ensemble fini et ordonné de symboles ou de caractères. Il représente le regroupement des graphèmes utilisés pour former les mots d'un langage et sert de système de communication dans divers domaines, notamment en mathématiques et en informatique.

Chaîne de Caractères (String)

Une chaîne de caractères, un mot ou une phrase (string) est une séquence ordonnée d'éléments (symboles) de longueur arbitraire (mais finie) appartenant à un alphabet donné.

Fermeture de Kleene (Étoile de Kleene)

Si A est un langage, la fermeture de Kleene (ou étoile de Kleene) est définie comme suit :

A* = U n = 0 An

Cela signifie qu'un caractère ou une séquence peut apparaître 0, 1, ou un nombre infini de fois dans une chaîne. C'est un opérateur fondamental en théorie des langages formels.

Fermeture Positive

La fermeture positive est définie comme suit :

A+ = U n = 1 An

Cela indique qu'un caractère ou une séquence doit apparaître au moins une fois. Elle est similaire à la fermeture de Kleene mais exclut la chaîne vide.

Exemple :

Pour l'expression "ho la+", les chaînes générées peuvent être : "hola", "hoola", "hooola", etc.

Machine à États Finis (Automate Fini)

Une machine à états finis, ou automate fini, est un modèle mathématique d'un système discret d'entrées et de sorties. Elle est utilisée pour modéliser des comportements séquentiels et reconnaître des langages réguliers.

Grammaire Formelle et Langages

Définition d'un Langage L(G)

Un langage L(G) peut être défini comme l'ensemble des chaînes x telles que :

L(G) = {x | x est (w, z)^n pour n de 1 à l'infini}

Règles de Production (Exemple) :

• X -> séquence
• Stream -> wyz
• Stream -> séquence wyz

Structure d'une Grammaire Formelle G

Une grammaire formelle G est généralement définie par un quadruplet (V, N, V0, P) où :

• V : Ensemble des symboles terminaux (vocabulaire terminal)
• N : Ensemble des symboles non-terminaux (vocabulaire non-terminal)
• V0 : Symbole de départ (axiome)
• P : Ensemble des règles de production (ici représenté par |-> ou ?)

Exemple de Composants de Grammaire :

• V = {dim} (ou d'autres symboles terminaux)
• S = {w, z} (peut être un sous-ensemble de V ou N, ou un alphabet)
• N = {V0, séquences}
• V0 = V0 (le symbole de départ)

Exemple de Grammaire pour Nombres Décimaux

Voici un exemple de règles de production pour définir des nombres décimaux :

• V0 -> nombre décimal
• nombre décimal -> Unsigned
• nombre décimal -> fraction décimale
• nombre décimal -> décimal non signé
• fraction décimale -> Unsigned
• Unsigned -> Chiffre
• Unsigned -> Chiffres Unsigned
• Chiffres -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Composants de la Grammaire G :

• V = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} (Symboles terminaux)
• N = {V0, nombre décimal, fraction décimale, Unsigned, Chiffres} (Symboles non-terminaux)
• V0 = V0 (Symbole de départ)

Exemples de nombres générés : 950, 0.85, 830.20, 0.79, 1.5...