^{PDFprof.com Search Engine}

Chapitre 3 Évaluation des expressions régulières et automates finis

Qu'est-ce que les expressions régulières ?
Les expressions régulières sont un moyen de définir et de traiter des ensembles de suites decaractères. des suites de caractères définies explicitement, des répétitions de suites de caractères, des choix entre plusieurs suites de caractères. des états, des transitions qui vont d’un état à un autre quand on lit un caractère,
Comment déduire une expression régulière ?
De cette manière, il sera aisé d’en déduire une expression régulière du langage accepté. Le pivotage (élimination des états qui ne sont ni initial, ni final). Soit A = (Q, q0, F, Σ, ) un AFE. Pour tout p, q Q, on note rpq l’expression régulière (p, q).
Qu'est-ce que l'expression rationnelle ?
Σ+ représente l’ensemble des mots sur l’alphabet Σ de longueur ≥ 1. 2) Si r et s sont des expressions rationnelles, qui représentent les langages R et S,alors r + s, rs, et r* sont des expressions rationnelles qui représentent leslangages R ∪ S, RS et R*.
Qu'est-ce que le langage reconnu par un automate ?
Définition. Le langage reconnu (ou accepté) par un automate est l’ensemble des mots quicorrespondent à un calcul de l’automate partant d’un état initial et s’arrêtant dans un étatfinal. Les automates finis sont les modèles de machine les plus simples : ils n’ont aucun supportde mémoire externe (comme la pile d’un automate à pile).

Qu'est-ce que les expressions régulières ?