Calculabilité - Décidabilité (LI347) [0.3cm] Cours no3

Calculabilité - Décidabilité (LI347)oCours n 3Stef GraillatUniversité Pierre et Marie Curie (Paris 6)S. Graillat (Univ. Paris 6) LI347 (cours n˚3) 1 / 30Résumé du cours précédentε-transitions : elles permettent d’étendre un AFN en autorisant unchangement d’état en lisant une entrée vide (c’est-à-dire en ne lisantaucun symbole). Les ε-AFN peuvent être convertis en AFD acceptantle même langage.Expression régulière : notation algébrique décrivant exactement lesmêmes langages que les automates finis. Les opérateurs sont l’union,la concaténation et la fermeture.Equivalence entre expressions régulières et automates finis : on peutconvertir un AFN en ER. On peut aussi convertir une ER en un ε-AFN.S. Graillat (Univ. Paris 6) LI347 (cours n˚3) 2 / 30AF et expressions régulières : Des AFD aux expressionsrégulières et réciproquementOn a déjà montré les équivalences suivantes :AFD ⇐⇒ AFN ⇐⇒ ε-AFNOn veut montrer que les langages définis par les ER sont exactement ceuxreconnus par les AFD.Passage d’un AFD à une ERTheorem3.4: ForeveryDFAA=(Q,!,!,q,F)Passage d’une ER à un ε-AFN. 0there is a regex R, s.t. L(R)=L(A).Proof: Let the states of A be {1,2,...,n},S. Graillat (Univ. Paris 6) LI347 (cours n˚3) 3 / 30with 1 being the start state.Des AFD aux expressions régulières(k)• Let R be a regex describing the set ofijA = (Q,Σ,δ,q ,F) un AFD avec Q ={1,...,n}, q = 1.0 0labels of all paths in A from state i to state(k)R : l’expression régulière reconnaissant les ...