Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

1 49 Contenu • Théorie des langages formels • Langages naturels VS langages for

1 49 Contenu • Théorie des langages formels • Langages naturels VS langages formels • Définitions, propriétés et opérations sur les langages • Génération VS reconnaissance • Hiérarchie de Chomsky • Langages réguliers • Définitions et propriétés • Trois représentations: grammaires régulières, expressions régulières, automates à états finis • Manipulation: déterminisation, minimisation, changement de représentation • Décider si un langage est régulier Langages réguliers 50 Langages réguliers • Définition inductive des langages réguliers (Lreg) • Base : ∅∈Lreg {ε}∈Lreg ∀alphabet Σ, ∀x∈Σ, {x}∈Lreg • Induction : ∀L1,L2 ∈Lreg, L1∪L2, L1.L2 et L1* ∈Lreg • Théorème: Tout langage fini est régulier • Autres définitions : • engendré par une grammaire régulière • reconnu par un automate à états finis • défini par une expression régulière => Question: équivalence de toutes ces définitions ? Langages réguliers 51 Langages réguliers Préservation (clôture) de la régularité par : • Opérations ensemblistes : • Union (par définition) • Complémentation (admis) • Intersection: L1∩L2 = (L1 c∪L2 c)c • Différence: L1-L2= L1∩L2 c • Opérations algébriques : • Concaténation (par définition) • Itération (par définition) • Puissance: L1 n=L1.L1.L1. … .L1 Langages réguliers 52 Grammaires régulières • Rappel: G=(VT,VN,S,R) est régulière ssi ∀α→β∈R, α∈VN et β∈((VT*.VN)∪VT+) • Théorème : Langages engendrés par grammaires régulières L(Greg) = Langages réguliers (Lreg) Preuve : 1. Montrer Lreg ⊆L(Greg) en construisant des grammaires générant tout langage vérifiant la définition inductive 2. Montrer L(Greg) ⊆Lreg en définissant le langage engendré par une grammaire régulière par la définition inductive Langages réguliers 53 Lreg ⊆ ⊆ ⊆ ⊆L(Greg) • Base: • ∅engendré par (∅,{S},S,{S→S}) • {ε} engendré par (∅,{S},S,{S→ε}) • {x} engendré par ({x},{S},S,{S→x}) • Induction: Soient L1↔G1=(VT1,VN1,S1,R1) et L2↔G2=(VT2,VN2,S2,R2) • L1∪L2 ↔G=(VT1∪VT2, VN1∪VN2∪{S}, S, R1∪R2∪{S→S1|S2}) • L1.L2 ↔G=(VT1∪VT2, VN1∪VN2, S1, {α→w.X ∈R1, X∈VN1} ∪{α→w.S2 | α→w ∈R1, w∈VT1 +} ∪R2) • L1* ↔G=(VT1, VN1∪{S}, S, R1 ∪{S→S1|ε} ∪ {α→w.S1 | α→w ∈R1, w∈VT1 +}) Attention : type(G)≠3 si S1→ε∈R1 ou S2→ε∈R2 Langages réguliers 54 L(Greg) ⊆ ⊆ ⊆ ⊆Lreg Soit G=(VT,VN,S,R) une grammaire régulière • Pour chaque z∈VN, on définit Lz le langage des mots engendrés à partir de z : • Soit z→v1 | v2 | … | vn | w1z1 | w2z2 | … | wmzm ∈R l’ensemble des règles ayant pour partie gauche le symbole non-terminal z, avec vi∈VT +, wi∈VT* et zi∈VN • Alors, Lz={v1} ∪{v2} ∪… ∪{vn} ∪({w1}.Lz1) ∪({w2}.Lz2) ∪… ∪({wm}.Lzm) => Lz se définit en fonction des langages Lzi : On obtient un système d’équations ensemblistes sur les langages Lzi 2 Langages réguliers 55 L(Greg) ⊆ ⊆ ⊆ ⊆Lreg Théorème: tout système d’équations de la forme L1 = A1 ∪B11.L1 ∪B12.L2 ∪… ∪B1n.Ln L2 = A2 ∪B21.L1 ∪B22.L2 ∪… ∪B2n.Ln … Ln = An ∪Bn1.L1 ∪Bn2.L2 ∪… ∪Bnn.Ln admet pour solution des langages L1, L2, …, Ln réguliers si tous les coefficients Ai et Bij sont des langages réguliers Dans notre cas: Lz= {v1} ∪{v2} ∪… ∪{vn} ∪({w1}.Lz1) ∪({w2}.Lz2) ∪… ∪({wm}.Lzm) Ainsi LS le langage issu de l’axiome (= L(G)) est régulier Ai B1i B2i Bmi régulier régulier régulier régulier Langages réguliers 56 Expressions régulières • Expression régulière (e-reg) = notation algébrique de l’ensemble des mots appartenant à un langage • Définition inductive: • Base : ∅∈e-reg définit le langage ∅ ε∈e-reg définit le langage {ε} ∀Σ, ∀x∈Σ, x∈e-reg définit le langage {x} • Induction : ∀e1, e2 ∈e-reg définissant les langages L1, L2 e1+e2 ∈e-reg définit le langage L1∪L2 e1.e2 ∈e-reg définit le langage L1.L2 e1* ∈e-reg définit le langage L1* (e1) ∈e-reg définit le langage L1 Ex: a*.b définit {a}*.{b} = {w∈{a,b}* | w=anb, n≥0} a.a* définit {a}.{a}* = {w∈{a}* | w=an, n>0} (a+b)* définit ({a}∪{b})* = {w∈{a,b}*} Langages réguliers 57 Expressions régulières • Préséance : (pour éviter parenthèses inutiles) () > * > . > + Ex: a.b*+c+d* <=> (a . (b*)) + (c + (d*)) • Propriétés, notations : • Le ‘.’ est souvent omis (sauf ambiguïté) • Le ‘+’ est parfois noté ‘|’ • On ajoute l’opérateur ‘+’ : e∈e-reg => e+∈e-reg; e+=(e.e*) Ex: (a+b)+ <=> ((a+b).(a+b)*) • On ajoute l’opérateur ‘?’ : e∈e-reg => e?∈e-reg; e?=(e+ε) Ex: a.b? <=> a.(b+ε) • mêmes propriétés que sur les langages (associativité, distributivité, idempotence, élément neutre/absorbant, …) Langages réguliers 58 L(e-reg) = Lreg • Théorème : Langages définis par expressions régulières L(e-reg) = Langages réguliers (Lreg) • Preuve: par équivalence des définitions inductives: Langages ↔ expressions ∅ ↔ ∅ {ε} ↔ ε {x} ↔ x L1.L2 ↔ (e1.e2) L1∪L2 ↔ (e1+e2) L1* ↔ e1* => Toute construction inductive d’un langage régulier correspond à une unique construction inductive d’expression régulière Langages réguliers 59 Simplification d’expressions régulières • Soient e, e1, e2 et e3 des expressions régulières : • Cas de base : • ε* = ε • ∅* = ε • e.ε = ε.e = e • e.∅= ∅.e = ∅ • ∅+e = e • ε+e* = e* • ε+e+ = e* • Cas avancés : • si L(e1)⊆L(e2) alors e1+e2 = e2 (inclusion) • e1+e2+e2 = e1+e2 (idempotence) • e1+e2 = e2+e1 (commutativité) • e** = e* (idempotence) • e1.e2 + e1.e3 = e1.(e2+e3) (factorisation/distribution) Ex: a+a.a*+a.a*.b+a.a*.b.b* = a+b* • Mais attention : • (e1+e2)* ≠e1*+e2* Ex: (a+b)*={a,b}* ≠ a*+b*={a}*∪{b}* • (e1.e2)* ≠e1*.e2* Ex: (a.b)*=({a}.{b})*={ab}* ≠ a*.b*={a}*.{b}* Langages réguliers 60 Automates • Un automate représente un ensemble d’états entre lesquels on évolue par des transitions Ex: états = {porte ouverte, porte fermée} transitions = {ouvrir, fermer} • Les applications sont plus larges que simplement les langages formels • description de processus industriels, • conception de circuits logiques, • modélisation comportementale d’un programme, • … • En langages formels : automates à états finis, automates à pile, machine de Turing 3 Langages réguliers 61 Automates à états finis • Un automates à états finis (AF) sert à reconnaître des mots: les transitions se font à la lecture des symboles du mot à reconnaître • Un AF se définit par (V,Q,I,F,T): • V est l’alphabet des mots reconnaissables • Q = {q1,q2, …, qn} est un ensemble fini d’états • I∈Q est l’état initial (unique!) • F⊆Q est l’ensemble des états finaux • T est un ensemble de transitions (qi,x,qj), qi,qj ∈Q et x∈V Ex: ({a,b}, {q1,q2}, q1, {q2}, {(q1,a,q1), (q1,b,q2), (q2,b,q2)}) Langages réguliers 62 Automates à états finis Propriétés des états : • I peut appartenir à F (état initial et final) • Q et F ne peuvent être vides • Un état q est accessible ssi il existe une séquence de transitions (I,x0,qi1), (qi1,x1,qi2), …, (qik,xk,q) • Un état q est co-accessible ssi il existe une séquence de transitions (q,x0,qi1), (qi1,x1,qi2), …, (qik,xk,f) telle que f∈F • Un état q est utile ssi il est accessible et co- accessible Langages réguliers 63 Automates à états finis Propriétés des transitions : • (qi,ε,qj) est appelée ε ε ε ε-transition (transition sans lecture de symbole) • Deux transitions (qi,x,qj) et (qi,x,qk) sont conflictuelles ssi qj≠qk Ex: ({a,b}, {q1,q2}, q1, {q2}, {(q1,a,q1), (q1,a,q2), (q2,b,q2)}) contient 2 transitions conflictuelles: (q1,a,q1) et (q1,a,q2) Langages réguliers 64 Automates à états finis Propriétés des AF : • Un AF est complet ssi ∀q∈Q, ∀x∈V, ∃q’∈Q tq (q,x,q’)∈T Ex: ({a,b}, {q1,q2}, q1, {q2}, {(q1,a,q1), (q1,b,q2), (q2,b,q2)}) n’est pas complet car il n’y a pas de transition depuis q2 à la lecture d’un ‘a’ • Un AF déterministe (AFD) n’admet ni ε-transitions ni transitions conflictuelles Ex: ({a,b}, {q1,q2}, q1, {q2}, {(q1,a,q1), (q1,b,q2), (q2,b,q2)}) est déterministe • Un AF non-déterministe (AFN) admet des transitions conflictuelles ou une ε-transition Ex: ({a,b}, {q1,q2}, q1, {q2}, {(q1,a,q1), (q1,a,q2), (q2,b,q2)}) est non- déterministe Langages réguliers 65 • Représentation graphique d’automates : • état q nœud q • transition (q,x,q’) arc étiqueté ‘x’ entre les nœuds q et q’ • état initial I arc non-étiqueté entrant sur nœud I • état final f nœud f doublement entouré Ex: ({a,b}, {q1,q2}, q1, {q2}, {(q1,a,q1), (q1,b,q2), (q2,b,q2)}) q2 Automates à états finis q1 a b b Langages réguliers 66 Automates à états finis • T table de transition δ δ δ δ indicée par Q et par V δ(q,x)={ qi∈Q | (q,x,qi)∈T } Ex: ({a,b}, {q1,q2}, q1, {q2}, {(q1,a,q1), (q1,b,q2), (q2,b,q2)}) donne • complet => ∀q∈Q, ∀x∈V, |δ(q,x)|≥1 • déterministe => ∀q∈Q, ∀x∈V, |δ(q,x)|≤1 q2 - q2 q2 q1 q1 b a δ δ δ δ 4 Langages réguliers 67 Lecture par un automate • On appelle lecture du mot w=x0x1…xn par un AF A=(V,Q,I,F,T) une séquence (x0x1…xn,I)→(x1…xn,q1)→…→(xi…xn,qi) correspondant à l’utilisation successive des transitions (I,x0,q1), (q1,x1,q2), …, (qi-1,xi,qi) ∈T Notation: on peut omettre les étapes et noter (w,I)→*(w’,qi) Ex: une lecture de w=aab par est la séquence (aab,q1)→(ab,q1)→(b,q1)→(ε,q2) q1 q2 a b b Langages réguliers 68 Lecture par un automate • Une lecture est terminale ssi elle se termine par (ε,q) Ex: sur A, (aab,q1)→(ab,q1)→(b,q1)→(ε,q2) • Une lecture est réussie ssi elle se termine par (w,q) et q∈F Ex: sur A, (abc,q1)→(bc,q1)→(c,q2) • Un mot w est reconnu par un automate A ssi il existe une lecture terminale réussie de w par A Ex: sur A, (aab,q1)→(ab,q1)→(b,q1)→(ε,q2) est terminale et réussie => aab est uploads/Litterature/ lgg-regulier.pdf