Langages r´ eguliers Langages reconnaissables Ensembles r´ eguliers Grammaires
Langages r´ eguliers Langages reconnaissables Ensembles r´ eguliers Grammaires de r´ e´ ecriture Une grammaire de r´ e´ ecriture est un 4-uplet ⟨N, Σ, P, S⟩o` u : ◮N est un ensemble de symboles non terminaux, appel´ e l’alphabet non terminal. ◮Σ est un ensemble de symboles terminaux, appel´ e l’alphabet terminal, tel que N et Σ soient disjoints. ◮P est un sous ensemble fini de : (N ∪Σ)∗N(N ∪Σ)∗× (N ∪Σ)∗ un ´ el´ ement (α, β) de P, que l’on note α →β est appel´ e une r` egle de production ou r` egle de r´ e´ ecriture. α est appel´ e partie gauche de la r` egle β est appel´ e partie droite de la r` egle ◮S est un ´ el´ ement de N appel´ e l’axiome de la grammaire. Alexis Nasr Compilation 1 / 60 @ Langages r´ eguliers Langages reconnaissables Ensembles r´ eguliers R` egles r´ eguli` eres et grammaires r´ eguli` eres ◮Une r` egle est r´ eguli` ere ` a gauche si et seulement si elle est de la forme A →xB ou A →x avec A, B ∈N et x ∈Σ. ◮Une r` egle est r´ eguli` ere ` a droite si et seulement si elle est de la forme A →Bx ou A →x avec A, B ∈N et x ∈Σ. ◮Une grammaire est r´ eguli` ere si elle est r´ eguli` ere ` a droite ou r´ eguli` ere ` a gauche. Une grammaire est r´ eguli` ere ` a gauche si toutes ses r` egles sont r´ eguli` eres ` a gauche et une grammaire est r´ eguli` ere ` a droite si toutes ses r` egles sont r´ eguli` eres ` a droite. Alexis Nasr Compilation 2 / 60 @ Langages r´ eguliers Langages reconnaissables Ensembles r´ eguliers Proto-phrases d’une grammaire Les proto-phrases d’une grammaire G = ⟨N, Σ, P, S⟩sont des mots construits sur l’alphabet Σ ∪N, on les d´ efinit r´ ecursivement de la fa¸ con suivante : ◮S est une proto-phrase de G ◮si αβγ est une proto-phrase de G et β →δ ∈P alors αδγ est une proto-phrase de G. Une proto-phrase de G ne contenant aucun symbole non terminal est appel´ e un mot g´ en´ er´ e par G. Le langage g´ en´ er´ e par G, not´ e L(G) est l’ensemble des mots g´ en´ er´ es par G. Alexis Nasr Compilation 3 / 60 @ Langages r´ eguliers Langages reconnaissables Ensembles r´ eguliers D´ erivation ◮L’op´ eration qui consiste ` a g´ en´ erer une proto-phrase αδγ ` a partir d’une proto-phrase αβγ et d’une r` egle de production r de la forme β →δ est appel´ ee l’op´ eration de d´ erivation. Elle se note ` a l’aide d’une double fl` eche : αβγ ⇒αδγ ◮On note α k ⇒β pour indiquer que β se d´ erive de α en k ´ etapes. ◮On d´ efinit aussi les deux notations + ⇒et ∗ ⇒de la fa¸ con suivante : ◮α + ⇒β ≡α k ⇒β avec k > 0 ◮α ∗ ⇒β ≡α k ⇒β avec k ≥0 Alexis Nasr Compilation 4 / 60 @ Langages r´ eguliers Langages reconnaissables Ensembles r´ eguliers Langage g´ en´ er´ e par une grammaire ◮L(G) est d´ efini de la fa¸ con suivante : L(G) = {m ∈Σ∗|S + ⇒m} ◮L’ensemble des langages pouvant ˆ etre g´ en´ er´ es par les grammaires r´ eguli` eres est appel´ e ensemble des langages r´ eguliers. Alexis Nasr Compilation 5 / 60 @ Langages r´ eguliers Langages reconnaissables Ensembles r´ eguliers Automates finis Langages r´ eguliers = langages reconnaissables D´ eterminisation Minimisation Automates finis Un automate fini est un 5-uplet ⟨Q, Σ, δ, q0, F⟩ ◮Q est l’ensemble des ´ etats, ◮Σ est l’alphabet de l’entr´ ee ◮δ est la fonction de transition : δ : Q × (Σ ∪{ε}) →℘(Q) ◮q0 ∈Q est l’´ etat initial, ◮F ⊆Q est l’ensemble des ´ etats d’acceptation. Alexis Nasr Compilation 6 / 60 @ Langages r´ eguliers Langages reconnaissables Ensembles r´ eguliers Automates finis Langages r´ eguliers = langages reconnaissables D´ eterminisation Minimisation Exemple ⟨Q, Σ, δ, q0, F⟩ Q = {0, 1, 2, 3} Σ = {a, b, c} δ(0, a) = {1} δ(0, b) = {2} δ(1, a) = {3} δ(1, b) = {0} δ(2, c) = {3} δ(3, a) = {2} q0 = 0 F = {1, 3} Alexis Nasr Compilation 7 / 60 @ Langages r´ eguliers Langages reconnaissables Ensembles r´ eguliers Automates finis Langages r´ eguliers = langages reconnaissables D´ eterminisation Minimisation Repr´ esentation graphique ⟨Q, Σ, δ, q0, F⟩ Q = {0, 1, 2, 3} Σ = {a, b, c} δ(0, a) = {1} δ(0, b) = {2} δ(1, a) = {3} δ(1, b) = {0} δ(2, c) = {3} δ(3, a) = {2} q0 = 0 F = {1, 3} a a b c a b 0 2 3 1 etat initial etats d’acceptation Alexis Nasr Compilation 8 / 60 @ Langages r´ eguliers Langages reconnaissables Ensembles r´ eguliers Automates finis Langages r´ eguliers = langages reconnaissables D´ eterminisation Minimisation Repr´ esentation matricielle ⟨Q, Σ, δ, q0, F⟩ Q = {0, 1, 2, 3} Σ = {a, b, c} δ(0, a) = {1} δ(0, b) = {2} δ(1, a) = {3} δ(1, b) = {0} δ(2, c) = {3} δ(3, a) = {2} q0 = 0 F = {1, 3} a a b c a b 0 2 3 1 etat initial etats d’acceptation a b c → 0 1 2 ← 1 3 0 2 3 ← 3 2 Alexis Nasr Compilation 9 / 60 @ Langages r´ eguliers Langages reconnaissables Ensembles r´ eguliers Automates finis Langages r´ eguliers = langages reconnaissables D´ eterminisation Minimisation Configurations et mouvement A = ⟨Q, Σ, δ, q0, F⟩ ◮Configuration : (q, m) ∈Q × Σ∗o` u : ◮q repr´ esente l’´ etat courant de l’unit´ e de contrˆ ole ◮m est la partie du mot ` a reconnaˆ ıtre non encore lue. Le premier symbole de m (le plus ` a gauche) est celui qui se trouve sous la tˆ ete de lecture. Si m = ε alors tout le mot a ´ et´ e lu. ◮Configuration initiale : (q0, m) o` u m est le mot ` a reconnaˆ ıtre ◮Configuration d’acceptation : (q, ε) avec q ∈F ◮Mouvement : (q, aw) ⊢(q′, w) si q′ ∈δ(q, a). Alexis Nasr Compilation 10 / 60 @ Langages r´ eguliers Langages reconnaissables Ensembles r´ eguliers Automates finis Langages r´ eguliers = langages reconnaissables D´ eterminisation Minimisation Langage reconnu par un automate ◮Un mot m est reconnu par l’automate s’il existe une suite de mouvements menant de la configuration (q0, m) ` a (q, ε) avec q ∈F. ◮Le langage reconnu par un automate A, not´ e L(A), est l’ensemble des mots reconnus par ce dernier : L(A) = {m ∈Σ∗|(q0, m) ∗ ⊢(q, ε) avec q ∈F} ◮Un langage L sur Σ est reconnaissable s’il existe au moins un automate fini A ayant Σ comme alphabet d’entr´ ee tel que L = L(A). Alexis Nasr Compilation 11 / 60 @ Langages r´ eguliers Langages reconnaissables Ensembles r´ eguliers Automates finis Langages r´ eguliers = langages reconnaissables D´ eterminisation Minimisation Reconnaissance a a b c a b 0 2 3 1 (0, ababaa) ⊢ (1, babaa) ⊢ (0, abaa) ⊢ (1, baa) ⊢ (0, aa) ⊢ (1, a) ⊢ (3, ε) Alexis Nasr Compilation 12 / 60 @ Langages r´ eguliers Langages reconnaissables Ensembles r´ eguliers Automates finis Langages r´ eguliers = langages reconnaissables D´ eterminisation Minimisation Automate complet ◮Un automate A = ⟨Q, Σ, δ, q0, F⟩est complet si A peut transiter depuis chaque ´ etat vers un autre ´ etat sur tous les symboles de Σ. ∀q ∈Q, ∀a ∈Σ, ∃e ∈Q, δ(q, a) = e ◮Si un automate n’est pas complet, on peut le compl´ eter en lui ajoutant un nouvel ´ etat, qui n’est pas un ´ etat d’acceptation, appel´ e ´ etat puits dans lequel aboutiront toutes les transitions qui “manquaient”. Alexis Nasr Compilation 13 / 60 @ Langages r´ eguliers Langages reconnaissables Ensembles r´ eguliers Automates finis Langages r´ eguliers = langages reconnaissables D´ eterminisation Minimisation Etats accessibles ◮Un ´ etat q de A est dit accessible s’il est possible d’y acc´ eder depuis l’´ etat initial ou, plus pr´ ecis´ ement, s’il existe un mot m ∈Σ∗permettant d’effectuer une suite de mouvements menant de l’´ etat initial ` a q : q accessible ⇔∃m ∈Σ∗(q0, m) ∗ ⊢(q, ε) ◮il est dit co-accessible s’il est possible d’acc´ eder ` a un ´ etat d’acceptation depuis cet ´ etat, ou encore, s’il existe un mot m ∈Σ∗permettant d’effectuer une suite de mouvements menant de q ` a un ´ etat d’acceptation : q co-accessible ⇔∃m ∈Σ∗(q, m) ∗ ⊢(e, ε) avec e ∈F Alexis Nasr Compilation 14 / 60 @ Langages r´ eguliers Langages reconnaissables Ensembles r´ eguliers Automates finis Langages r´ eguliers = langages reconnaissables uploads/S4/ automates-expressions-regulieres-algo-de-moore.pdf
Documents similaires
-
20
-
0
-
0
Licence et utilisation
Gratuit pour un usage personnel Attribution requise- Détails
- Publié le Jui 19, 2021
- Catégorie Law / Droit
- Langue French
- Taille du fichier 0.6481MB