Embed Size (px)
Citation preview
Chapitre 2 TLC [email protected] 2010-2011
Université de Tunis El Manar 2010-2011 Faculté des Sciences de Tunis ---------------- Département des Sciences de l’Informatique
Théorie des Langages et Compilation (TLC)
Chapitre 2 : Automates d’états finis avec sortie Enseignant : Khaled Bsaïes Section : IF4 Les automates que nous avons étudiés acceptent ou refusent des mots. La sortie est donc binaire. Les automates de MOORE (sortie associée aux états), et les automates de MEALY (sortie associée aux transitions) permettent d’avoir une sortie dans un alphabet quelconque. Les automates de MOORE : Un automate de MOORE est un sextuplet : M = (Q, Σ, ∆, δ, λ, s) où : Q, Σ, δ et s sont les mêmes que pour les automates d’états finis (ensemble d’états, alphabet d’entrée, fonction de transitions et l’état initial). λ : Q � ∆. ∆ est l’alphabet de sortie. La sortie de M en réponse à l’entrée a1a2...an, n ≥ 0 est λ(q0) λ(q1)...λ(qn), où q0,q1,...,qn est la séquence d’états telle que δ(qi-1,ai)=qi 0 ≤ i ≤ n. Remarquons qu’un automate de MOORE donne toujours λ(q0) en réponse à l’entrée ε. Les automates d’états finis peuvent être considérés comme un cas particulier des automates de MOORE où l’alphabet de sortie est {0,1} et l’état q est un état accepteur si et seulement si λ(q)=1. Exemple Supposons que nous souhaitons déterminer le reste de la division euclidienne d’un entier par 3 pour une chaîne de 0 et de 1 désignant un entier naturel. 3 états sont à prévoir q0, q1 et q2, où être dans qj signifie avoir j comme reste. On définit donc : λ(qj)=j pour j=0, 1 et 2.
L’entrée 1010 donne les états visités : q0, q1, q2, q2, q1 générant la sortie 01221. ε (ayant comme valeur 0 par convention) rend le reste 0, 5 rend 2 et 10 rend 1.
Chapitre 2 TLC [email protected] 2010-2011
Les automates de MEALY : Un automate de MEALY est un sextuplet : M = (Q, Σ, ∆, δ, λ, s) où tout est analogue aux
automates de MOORE, sauf pour λ : QXΣ � ∆. λ(q,a) donne une sortie associée à la transition de l’état q sur l’entrée a. La sortie produite par M en réponse à l’entrée a1a2...an est λ(q0,a1) λ(q1,a2)... λ(qn-1,an), où q0,q1,...,qn est la séquence d’états telle que : δ(qi-1,ai)= qi 1 ≤ i ≤ n. Remarquons que cette séquence est de taille n, alors qu’elle l’était de taille (n+1) pour les automates de MOORE, et à l’input ε l’automate de MEALY rend ε. Exemple (0|1)*(00|11)
On peut transformer un automate de MOORE en un automate équivalent de MEALY et inversement. Voici un automate de MOORE associé à celui de la figure précédente.
