Fiche de synthèse¶
Définition
AFD \(A = (Q, \Sigma, \delta, q_i, F)\)
- un seul état initial
- pas de choix : si \(q \xrightarrow{a} q'\) et \(q \xrightarrow{a} q''\) alors \(q' = q''\)
AFND \(A = (Q, \Sigma, \delta, I, F)\) : plusieurs états initiaux et choix
AFND\(\epsilon\) \(A = (Q, \Sigma, \delta, q_i, F)\) : un seul état initial, choix et transitions spontanées \(q \xrightarrow{\epsilon} q'\)
complet : toutes les transitions sont définies, \(\forall q \in Q, \forall a \in \Sigma, \exists q', q \xrightarrow{a} q'\)
émondé : \(\forall q \in Q, \exists q_f \in F, q_i \leadsto q \leadsto q_f\)
Fonction de transition
AFD \(\delta : Q \times \Sigma \rightarrow Q\) partielle
\((q, a) \in \mathop{dom}(\delta) \iff q \xrightarrow{a} \delta(q,a)\)
AFND \(\delta : Q \times \Sigma \rightarrow \mathcal{P}(Q)\)
AFND\(\epsilon\) \(\delta : Q \times (\Sigma \cup \{ \epsilon \}) \rightarrow \mathcal{P}(Q)\)
transition spontanée \(q \xrightarrow{\epsilon} q'\)
Fonction de transition étendue
AFD \(q_0 \xrightarrow{a_1} q_1 \dots \xrightarrow{a_n} q_n \Rightarrow \delta^*(q_0,a_1\dots a_n) = q_n\)
\(\delta^*(q,\epsilon) = q\qquad w \in \mathop{lang}(A) \iff \delta^*(q_i, w) \in F\)
AFND \(q_0 \xrightarrow{a_1} q_1 \dots \xrightarrow{a_n} q_n \Rightarrow q_n \in \delta^*(q_0,a_1\dots a_n)\)
\(\delta^*(q,\epsilon) = \{ q\} \qquad \delta^*(q,wa) = \bigcup_{q' \in \delta^*(q,w)} \delta(q',a)\)
\(w \in \mathop{lang}(A) \iff \left(\bigcup_{q_i \in I} \delta^*(q_i, w)\right) \cap F\neq \emptyset\)
AFND → AFD
\(A = (Q, \Sigma, \delta, I, F) \Rightarrow A'=(\mathcal{P}(Q), \Sigma, \delta', I, F')\)
\(\delta'(E,a) = \bigcup_{q \in E} \delta(q, a)\)
\(F' = \enscomp{E \subset Q}{E \cap F \neq \emptyset}\)
AFNDε : clôture
\(\overline{q} = \enscomp{q'}{q \xrightarrow{\epsilon} \dots \xrightarrow{\epsilon} q'}\) (avec \(q \in \overline{q}\))
\(\delta^*(q,\epsilon) = \overline{q} \qquad \delta^*(q,wa) = \overline{\bigcup_{q' \in \delta^*(q,w)} \delta(q',a)}\)
AFNDε → AFND
\(A = (Q, \Sigma, \delta, q_i, F) \Rightarrow A'=(Q, \Sigma, \delta', \overline{q_i}, F)\)
\(\delta'(q,a) = \overline{\delta(q,a)}\)
Thompson : expression régulière → AFNDε
\(A(\emptyset) =\)
\(\quad A(\epsilon) =\)
\(\forall a \in \Sigma, A(a) =\)
\(A(ee') =\)
\(A(e|e') =\)
\(A(e^*) =\)
Méthode de McNaughton-Yamada
\(Q = \range{1}{n}\), état initial \(1\).
\(R^{(k)}_{ij} =\) expression régulière dénotant les étiquettes des chemins \(i \leadsto j\) dont les états intermédiaires sont \(\le k\).
\(R^{(0)}_{ii} = \epsilon\) si \(i \not\rightarrow i \qquad R^{(0)}_{ii} = \epsilon | a_1 | \dots | a_p\) si \(i \xrightarrow{a_1} i, \dots, i \xrightarrow{a_p} i\)
\(i \neq j\) : \(R^{(0)}_{ij} = \emptyset\) si \(i \not\rightarrow j \qquad R^{(0)}_{ij} = a_1 | \dots | a_p\) si \(i \xrightarrow{a_1} j, \dots, i \xrightarrow{a_p} j\)
\(R^{(k)}_{ij} = R^{(k-1)}_{ij} | R^{(k-1)}_{ik} \left(R^{(k-1)}_{kk}\right)^* R^{(k-1)}_{kj}\)
Si \(F = \{ f_1, \dots, f_p \}\) :
\(R^{(n)}_{1 f_1} | \dots | R^{(n)}_{1 f_p}\)
Élimination des états - Brzozowski-McCluskey
EX-AF(N)D : automates avec des expressions régulières comme étiquettes.
Élimination de \(s\) :
On aboutit à :
Expression régulière associée : \((e_i | e e_f^* e')^* e e_f^*\)
Théorème de Kleene
régulier (ou rationnel) : dénoté par une expression régulière
reconnaissable : reconnu par un AFD
Théorème : un langage est régulier si et seulement s'il est reconnaissable par un AFD (ou par un AFND, ou par un AFND\(\epsilon\)).
Stabilité des langages réguliers
Les langages réguliers sont stables par union, intersection, complémentaire, étoile, concaténation, miroir.
Lemme de l'étoile
Si \(L\) est régulier, il existe \(n \in \N^*\) tel que tout \(w \in L\) avec \(|w| \ge n\) s'écrit \(w = xyz\) avec \(y \neq \epsilon\), \(|xy| \le n\) et \(x y^* z \subset L\).
Contraposée : soit \(L\) un langage sur \(\Sigma\). Si pour tout \(n \in \N^*\), il existe \(w \in L\) tel que \(|w| \ge n\) et que pour tout \(x, y, z \in \Sigma^*\) tels que \(w = x y z\), \(y \neq \epsilon\) et \(|xy| \le n\) il existe \(k \in \N\) avec \(x y^k z \not\in L\), alors \(L\) n'est pas régulier.
Langages locaux
\(L\) local ssi \(\exists P, S \subset \Sigma, N \subset \Sigma^2,\)
Si \(L\) est local, on peut prendre :
\(P = \enscomp{a \in \Sigma}{\exists w \in \Sigma^*, aw \in L}\)
\(S = \enscomp{a \in \Sigma}{\exists w \in \Sigma^*, wa \in L}\)
\(\Sigma^2 \backslash N = \enscomp{ab \in \Sigma^2}{\exists w,v \in \Sigma^*, wabv \in L}\)
Automates locaux
AFD local : si \(q \xrightarrow{a} q_1\) et \(q' \xrightarrow{a} q_2\) alors \(q_1 = q_2\).
AFD standard : aucune transition n'arrive sur l'état initial.
langage local \(\iff\) reconnu par un AFD local \(\iff\) reconnu par un AFD local et standard.
Si \(P,S,N\) sont donnés : \(A = (\Sigma \cup \{\epsilon\}, \Sigma, \delta, \epsilon, S')\) avec
\(\forall a \in P, \delta(\epsilon, a) = a \qquad \forall a, b \in \Sigma, ab \not\in N \Rightarrow \delta(a,b) = b\)
Berry-Sethi
Expression régulière linéaire : chaque lettre apparaît au plus une fois.
Linéarisation : \(a(a|b)cb^*a \Rightarrow a_1(a_2|b_1)cb_2^*a_3\)
\(e\) linéaire \(\Rightarrow \mathop{lang}(e)\) local : on calcule \(P\), \(S\), \(N\) par induction, on construit l'AFD local, puis on efface les indices pour obtenir un AFND reconnaissant l'expression de départ.
\(accv(\emptyset) = \perp \quad \forall a \in \Sigma, accv(a) = \perp \quad accv(\epsilon) =\top \quad accv(e^*) = \top\)
\(accv(e_1|e_2) = accv(e_1) \vee accv(e_2) \quad accv(e_1 e_2) = accv(e_1) \wedge accv(e_2)\)
Pour \(e\) ne contenant pas \(\emptyset\) (ou \(e = \emptyset\)) :
\(P(\emptyset) = \emptyset \quad \forall a \in \Sigma, P(a) = \{a\} \quad P(\epsilon) =\emptyset \quad P(e^*) = P(e)\)
\(S(\emptyset) = \emptyset \quad \forall a \in \Sigma, S(a) = \{a\} \quad S(\epsilon) =\emptyset \quad S(e^*) = S(e)\)
\(N(\emptyset) = N(\epsilon) = \Sigma^2 \quad \forall a\in \Sigma, N(a) = \Sigma^2 \quad N(e^*) = N(e) \backslash S(e)P(e)\)
\(N(e_1|e_2) = N(e_1) \cap N(e_2) \quad N(e_1 e_2) = (N(e_1) \cap N(e_2)) \backslash S(e_1) P(e_2)\)
Schéma global¶
