Théorie des langages : Cours théorie des langages langages et grammaires
Télécharger PDFChapitre 4
Langages réguliers Et
Automates d’états finis Théorie deslangages
Partie 1
Langages et grammaires
•Un langage est régulier si et seulement s’il existe une grammaire régulière générant ce langage.
•L’ensemble des mots-clés, identificateurs, constantes, chiffres (entier ou réel), parenthèses, séparateurs, ... d’un langage de programmation est un langage régulier et peut être décrit par une grammaire régulière.
Chapitre 4
Langages réguliers 3
Chapitre 4
Langages réguliers Etantdonné un alphabet VT , on appellelangageréguliersurV T
un langage surVT définide la façon suivante:
1 ∅ (l’ensemble vide) est un langageréguliersurVT .
2 {ε} est un langageréguliersurVT .
3 {a} est un langageréguliersurVT pour tout a ∈VT .
4 5 Un ensemble finide motsL={u1 ,...,uk }s’e ́crit:L={u 1
}∪ {u2 }∪ ...∪ {uk }.
L est re ́gulier car chaque {u
i }l’est et l’ensemble des langages re ́guliers est clos pourl’union.
Chapitre 4
Langages réguliers Pour tout mot u ∈ V
T ∗
, le langage {u} estrégulier.
Si u peut s’écrire sous la forme u=a
1 . . . a
n ai ∈VT , alors le langage {u} s’écritcommecomme suit: {u}={a1 }{a2 }...{an }.
{u}estréguliercar:
1. chaque{ai }est un langage régulier 2. et la concaténation des langages réguliers est un langage régulier.
Tout langage fini estrégulier
Un ensemble finide motsL={u1 ,...,uk }
s’écrit:L={u1 }∪ {u2 }∪ ...∪ {uk }.
L est régulier car:
1.chaque {ui }est un langage régulier 2.et l’union des langages réguliers est un
langage régulier Chapitre 4
Langages réguliers Le langage VT ∗ qui est l’ensemble de tous les motsdéfinis sur VT estrégulier.•V T={a 1,...,a p} •le langage{a1 ,...,ap }est régulier.•V T ∗ est la fermeture de Kleene de celangage
Chapitre 4
Langages réguliers
•Les grammaires sont des systèmes de génération de langages.
•Les langages sont reconnus par des machines formelles appelées: automates ou systèmes reconnaisseursqui étant donnée un mot sont capables de dire si ce mot appartient ou pas à un langage. Chapitre 4
Les automates d’états finis
•Un langage est régulier si et seulement si il existe un automate d’états finis qui le reconnaît. ◮Si un langage est régulier alors il existe un automate d’états finis qui le reconnaît. ◮Si un langage est reconnu par un automate d’états finis alors il est régulier. Chapitre 4
Les automates d’états finis
•Un automate d’états finis (ou automate fini) est une machine abstraite constituée d'états et de transitions. •Cette machine est destinée à traiter des mots fournis en entrée : l'automate passe d'état en état, suivant les transitions, à la lecture de chaque lettre de l'entrée. •L'automate est dit « fini » car il possède un nombre fini d'états distincts.
•Le mot est reconnu par l’automate, s’il est entièrement lu et l’automate est dans un état final. Dans tous les autres cas il est rejeté. Chapitre 4
Les automates d’états finis10 Un automate à états finis (AEF) estun quintupletA = (VT , Q, q0 , d, F)
défini par :
–Un alphabet fini VT (l’alphabet) –Un ensemble fininon vide d'états Q
Q = {q0 , q1 , q2 , q3 ...}
–Une fonction de transition
d: Qx VT Q.
qui prend en paramètre un état et un symboleet qui renvoie un état exemple: δ(qi , a) = qj –Un état initial q0 –l'ensemble Fdes états finaux F Q
Chapitre 4
Les automates d’états finis
Représentation graphiqued’un automate finis
Un automate finis peut être représenté par un grapheorienté étiqueté : –Les NœudsIls sont étiquetés par les noms des états •Le nœud étiqueté par le nom de l’état initial est représenté par un carré:
•Le nœud étiqueté par le nom de l’état final est représenté par un triangle •Les nœuds étiquetés par les noms des autres états sont représentés par des cercles.
–Les Arcs orientésreprésentent les transitions de l'automate. Chaque arc est étiqueté par un symbole terminal.
Chapitre 4
Les automates d’états finisq 0q fq aq 0q •Pour la lisibilité, lorsque deux arcs de même orientation sont possibles entre deux nœuds, ils sont fusionnés.
Chapitre 4
Les automates d’états finis
•Un arc peut «boucler» un état sur lui même:
•Des transitions peuvent partirde l'état final
Représentation d’un automate finis par une table de transitions
•Équivalente à la représentation graphique de l’automate.
•C’est une matrice dont les lignes représentent les états de l’automate et les colonnes représentent les symboles terminaux. •Le contenu de la table de transition décrit les transitions de l’automate d’un état vers un autre en lisant unsymbole terminal.
Chapitre 4
Les automates d’états finisq 0q 2q 1q 0q 1q 2q 0q 1q 2q 1q 3q 0q 3q 3q 3
Si une transition n’est pas définie on la remplace par -q 3q 3q 3
Chapitre 4
Les automates d’états finis
•Soit l’automate suivant:
•A =(VT , Q, q0 , d, F)•V T ={a,b}•q 0 :état initial
•Q ={q0 , q1 , q2 } •F={q2 }
état final
•d: fonction de transitionab q0 q1 q0 q1 q2 q2 q2 q0 q2 q1 -signifie : "transition non définie" 15
Langage reconnu par un AEF
le langage reconnu par l'automate A = (VT , Q, q0 , d, F )est le langage :
L(A) = l'ensemble des mots qui font passer l'automate de l'état initialà un état final.
L(A) = { concaténationdes étiquettes de toutes les transitions partant de l'état initial à unétat final}.
Le langage reconnu par un automate fini est un langage régulier. Chapitre 4
Les automates d’états finis16 A=( VT , Q, q0 ,, d, F)V T
= {a, b}
Q = {q0 , q1 , q2 };
F = {q2 } Table de transition
L(A)={a(ba)n a / n N}
Chapitre 4
Les automates d’états finisq 0q 2q 1ab q0 q1 q1 q2 q0 q2 -signifie : "transition non définie"