diff options
Diffstat (limited to 'notes-inf105.tex')
| -rw-r--r-- | notes-inf105.tex | 403 |
1 files changed, 322 insertions, 81 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index ead466a..efb4a57 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -22,7 +22,7 @@ \usepackage{graphics} \usepackage[usenames,dvipsnames]{xcolor} \usepackage{tikz} -\usetikzlibrary{arrows,automata,positioning} +\usetikzlibrary{arrows,automata,positioning,calc} \usepackage[hyperindex=false]{hyperref} % \theoremstyle{definition} @@ -761,7 +761,8 @@ cccc,\ldots\}$, est rationnel, et comme $\{d\}$ l'est aussi, la concaténation $\{d\}(\{c\}^*) = \{d, dc, dcc, dccc, \ldots\}$ est encore un langage rationnel. -\thingy Formellement, la définition des langages rationnelles est la +\thingy\label{stable-under-rational-operations} +Formellement, la définition des langages rationnelles est la suivante : un ensemble $\mathscr{C} \subseteq \mathscr{P}(\Sigma^*)$ de langages (où $\mathscr{P}(\Sigma^*)$ est l'ensemble des parties de $\Sigma^*$, i.e., l'ensemble de tous les langages sur $\Sigma$, @@ -2085,12 +2086,12 @@ choix. \subsection{Stabilité des langages reconnaissables} -\thingy On rappelle qu'on a défini un langage reconnaissable comme un -langage $L$ pour lequel il existe un DFA $A$ tel que $L = L_A$. -D'après \ref{completion-of-dfai}, \ref{determinization-of-nfa} et -\ref{removal-of-epsilon-transitions}, on peut remplacer « DFA » dans -cette définition par « DFAI », « NFA » ou « εNFA » sans changer la -définition. +\thingy On rappelle qu'on a défini un langage \index{reconnaissable + (langage)}reconnaissable comme un langage $L$ pour lequel il existe +un DFA $A$ tel que $L = L_A$. D'après \ref{completion-of-dfai}, +\ref{determinization-of-nfa} et \ref{removal-of-epsilon-transitions}, +on peut remplacer « DFA » dans cette définition par « DFAI », « NFA » +ou « εNFA » sans changer la définition. Nous allons maintenant montrer que les langages reconnaissables sont stables par différentes opérations : complémentaire, union, @@ -2212,6 +2213,77 @@ chaque état $q$ et chaque lettre $x$, il existe une unique arête aboutissant à $q$ et étiquetée par $x$ — sont parfois dits « co-déterministes ».) +\thingy Nous allons maintenant montrer que la classe des langages +reconnaissables est stable par les opérations rationnelles (union, +concaténation et étoile de Kleene, +cf. \ref{stable-under-rational-operations} ; on l'a déjà vu pour la +réunion, mais on va en donner une nouvelle démonstration, qui a un +contenu algorithmique utile dans des circonstances différentes). + +Pour établir ces stabilités, on va travailler sur les NFA et utiliser +la construction parfois appelée « de Glushkov » ou « automate +standard ». Celle-ci travaille, en fait, sur des NFA vérifiant une +propriété supplémentaire facile à assurer, et on va commencer par un +lemme dans ce sens : + +\begin{lem}\label{standard-automaton-lemma} +Soit $A$ un NFA. Alors il existe un NFA $A'$ (sur le même +alphabet $\Sigma$) qui soit équivalent à $A$ et qui possède la +propriété supplémentaire d'avoir un \emph{unique} état initial $q_0$ +et qu'aucune transition n'aboutit à $q_0$. De plus, $A'$ se déduit +algorithmiquement de $A$ et a au plus un état de plus que $A$. + +(On pourra appeler \defin[standard (automate)]{standard} un NFA +vérifiant cette propriété d'avoir un unique état initial qui n'est la +cible d'aucune transition. L'affirmation est donc que tout NFA est +équivalent à un NFA \emph{standard} qui s'en déduit algorithmiquement +par l'ajout d'au plus un état.) +\end{lem} +\begin{proof} +On fabrique $A'$ en reprenant le même ensemble d'états $Q$ que +dans $A$ auquel on ajoute un unique nouvel état $q_0$ qui sera le seul +état initial de $A'$ ; pour chaque transition partant d'un état +initial de $A$, on ajoute dans $A'$ une transition identiquement +étiquetée partant de $q_0$. + +Formellement : soit $A = (Q,I,F,\delta)$. On définit alors $A' = +(Q',\{q_0\},F,\delta')$ de la manière suivante : $Q' = Q \uplus +\{q_0\}$ (où $\uplus$ désigne une réunion +disjointe\footnote{C'est-à-dire qu'on s'arrange pour que $q_0$ + n'appartienne pas à $Q$.}), et $\delta'$ est la réunion des +transitions $(q,x,q')$ qui étaient déjà dans $\delta$ et des +$(q_0,x,q')$ telles qu'il existe une transition $(q,x,q') \in \delta$ +avec $q\in I$. + +La figure suivante illustre la transformation en question : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(A.base)] +\node (A) at (0bp,0bp) [draw,dotted,circle,minimum size=75bp] {$A$}; +\node (q) at (-15bp,15bp) [draw,circle,state,initial] {\footnotesize $q$}; +\node (qp) at (15bp,15bp) [draw,circle,state] {\footnotesize\vbox to0pt{\vss\hbox to0pt{$q'$\hss}}\phantom{$q$}}; +\draw [->] (A.east) -- ($(A.east)+(3ex,0)$); +\draw [->] (q) -- node[auto] {\footnotesize $x$} (qp); +\end{tikzpicture} +\quad devient\quad +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(A.base)] +\node (A) at (0bp,0bp) [draw,dotted,circle,minimum size=75bp] {\phantom{$A$}}; +\node (q) at (-15bp,15bp) [draw,circle,state] {\footnotesize $q$}; +\node (qp) at (15bp,15bp) [draw,circle,state] {\footnotesize\vbox to0pt{\vss\hbox to0pt{$q'$\hss}}\phantom{$q$}}; +\node (q0) at (-40bp,0bp) [draw,circle,state,initial,fill=white] {$q_0$}; +\draw [->] (A.east) -- ($(A.east)+(3ex,0)$); +\draw [->] (q) -- node[auto] {\footnotesize $x$} (qp); +\draw [->] (q0) to[out=0,in=270] node[auto,swap] {\footnotesize $x$} (qp.south); +\end{tikzpicture} +\end{center} + +(\emph{Remarque : } De façon équivalente, on peut fabriquer $A'$ en +ajoutant d'abord un unique état initial $q_0$ et des ε-transitions de +$q_0$ vers chacun des états initiaux de $A$, puis en éliminant les +ε-transitions qu'on vient d'ajouter +(cf. \ref{removal-of-epsilon-transitions}). Cela donne le même +résultat que ce qui vient d'être dit.) +\end{proof} + \thingy On a vu en \ref{dfa-union-and-intersection} une preuve, à base de NFA, que $L_1 \cup L_2$ est reconnaissable lorsque $L_1$ et $L_2$ le sont. Donnons maintenant une autre preuve de ce fait, à base de @@ -2220,40 +2292,99 @@ le sont. Donnons maintenant une autre preuve de ce fait, à base de \begin{prop}\label{nfa-union} Si $L_1,L_2$ sont des langages reconnaissables (sur un même alphabet $\Sigma$), alors la réunion $L_1 \cup L_2$ est -reconnaissable ; de plus, un εNFA (resp. NFA) la reconnaissant se -déduit algorithmiquement de εNFA (resp. NFA) reconnaissant $L_1$ -et $L_2$ (c'est simplement, en un sens évident, la réunion disjointe -des automates donnés). +reconnaissable ; de plus, un NFA la reconnaissant se déduit +algorithmiquement de NFA reconnaissant $L_1$ et $L_2$. \end{prop} \begin{proof} -Par hypothèse, il existe des εNFA (resp. NFA) $A_1 = -(Q_1,I_1,F_1,\delta_1)$ et $A_2 = (Q_2,I_2,F_2,\delta_2)$ tels que -$L_1 = L_{A_1}$ et $L_2 = L_{A_2}$. Considérons l'automate $A'$ dont -l'ensemble d'états est $Q' = Q_1 \uplus Q_2$ où $\uplus$ désigne la -réunion disjointe\footnote{C'est-à-dire que, quitte à renommer les - états, on remplace $Q_2$ par un ensemble en bijection avec lui de - façon à être disjoint de $Q_1$.}, l'ensemble d'états initiaux est la -réunion $I' = I_1 \cup I_2$, les états finaux $F' = F_1 \cup F_2$, et -la relation de transition $\delta'$ est $\delta_1 \cup \delta_2$ -(l'ensemble des transitions existant déjà dans $A_1$ ou $A_2$). -Symboliquement : +Par hypothèse, il existe des NFA reconnaissant $L_1$ et $L_2$ : +d'après \ref{standard-automaton-lemma}, on peut supposer qu'ils sont +\emph{standards} en ce sens qu'ils ont un unique état initial qui +n'est la cible d'aucune transition. Disons que $A_1 = +(Q_1,\{q_1\},F_1,\delta_1)$ et $A_2 = (Q_2,\{q_2\},F_2,\delta_2)$ sont +des NFA standards tels que $L_1 = L_{A_1}$ et $L_2 = L_{A_2}$. + +L'automate $A'$ s'obtient réunissant $A_1$ et $A_2$ mais en +« fusionnant » les états initiaux $q_1$ et $q_2$ de $A_1$ et $A_2$ en +un unique état initial $q'_0$, d'où partent les mêmes transitions que +de l'un ou de l'autre : \begin{center} -\begin{tikzpicture}[>=latex,line join=bevel,automaton] -\node (A1) at (0bp,25bp) [draw,dotted,circle,initial,final] {$A_1$}; -\node (A2) at (0bp,-25bp) [draw,dotted,circle,initial,final] {$A_2$}; +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(A.base)] +\node (A) at (0bp,0bp) [draw,dotted,circle,minimum size=60bp] {$A_1$}; +\node (q0) at (-35bp,0bp) [draw,circle,state,initial,fill=white] {$q_1$}; +\node (i1) at (-10bp,20bp) [circle,inner sep=2bp,fill] {}; +\node (i2) at (-10bp,-20bp) [circle,inner sep=2bp,fill] {}; +\node (o1) at (15bp,20bp) [circle,inner sep=2bp,fill] {}; +\node (o2) at (25bp,0bp) [circle,inner sep=2bp,fill] {}; +\node (o3) at (15bp,-20bp) [circle,inner sep=2bp,fill] {}; +\draw [->] (q0) -- (i1); +\draw [->] (q0) -- (i2); +\draw [->] (o1) -- ($(o1.east)+(3ex,0)$); +\draw [->] (o2) -- ($(o2.east)+(3ex,0)$); +\draw [->] (o3) -- ($(o3.east)+(3ex,0)$); +\end{tikzpicture} +et +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(A.base)] +\node (A) at (0bp,0bp) [draw,dotted,circle,minimum size=60bp] {$A_2$}; +\node (q0) at (-35bp,0bp) [draw,circle,state,initial,fill=white] {$q_2$}; +\node (i1) at (-10bp,20bp) [circle,inner sep=2bp,fill] {}; +\node (i2) at (-10bp,-20bp) [circle,inner sep=2bp,fill] {}; +\node (o1) at (15bp,20bp) [circle,inner sep=2bp,fill] {}; +\node (o2) at (25bp,0bp) [circle,inner sep=2bp,fill] {}; +\node (o3) at (15bp,-20bp) [circle,inner sep=2bp,fill] {}; +\draw [->] (q0) -- (i1); +\draw [->] (q0) -- (i2); +\draw [->] (o1) -- ($(o1.east)+(3ex,0)$); +\draw [->] (o2) -- ($(o2.east)+(3ex,0)$); +\draw [->] (o3) -- ($(o3.east)+(3ex,0)$); +\end{tikzpicture} +\\deviennent\\ +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(A.base)] +\node (A1) at (0bp,0bp) [draw,dotted,circle,minimum size=60bp] {\phantom{$A_1$}}; +\node (q0) at (-35bp,0bp) [draw,circle,state,initial,fill=white] {$q'_0$}; +\node (A1) at (90bp,0bp) [draw,dotted,circle,minimum size=60bp] {\phantom{$A_2$}}; +\node (i1) at (-10bp,20bp) [circle,inner sep=2bp,fill] {}; +\node (i2) at (-10bp,-20bp) [circle,inner sep=2bp,fill] {}; +\node (l1) at (15bp,20bp) [circle,inner sep=2bp,fill] {}; +\node (l2) at (25bp,0bp) [circle,inner sep=2bp,fill] {}; +\node (l3) at (15bp,-20bp) [circle,inner sep=2bp,fill] {}; +\node (r1) at (80bp,20bp) [circle,inner sep=2bp,fill] {}; +\node (r2) at (80bp,-20bp) [circle,inner sep=2bp,fill] {}; +\node (o1) at (105bp,20bp) [circle,inner sep=2bp,fill] {}; +\node (o2) at (115bp,0bp) [circle,inner sep=2bp,fill] {}; +\node (o3) at (105bp,-20bp) [circle,inner sep=2bp,fill] {}; +\draw [->] (q0) -- (i1); +\draw [->] (q0) -- (i2); +\draw [->] (l1) -- ($(l1.east)+(3ex,0)$); +\draw [->] (l2) -- ($(l2.east)+(3ex,0)$); +\draw [->] (l3) -- ($(l3.east)+(3ex,0)$); +\draw [->] (o1) -- ($(o1.east)+(3ex,0)$); +\draw [->] (o2) -- ($(o2.east)+(3ex,0)$); +\draw [->] (o3) -- ($(o3.east)+(3ex,0)$); +\draw [->] (q0) to[out=10,in=180] (r1); +\draw [->] (q0) to[out=350,in=180] (r2); \end{tikzpicture} \end{center} -%% \begin{center} -%% \begin{tikzpicture}[>=latex,line join=bevel,automaton] -%% \node (q0) at (0bp,0bp) [draw,circle,state,initial] {$q_0$}; -%% \node (A1) at (50bp,30bp) [draw,dotted,circle] {$A_1$}; -%% \node (A2) at (50bp,-30bp) [draw,dotted,circle] {$A_2$}; -%% \draw [->] (q0) to node[auto] {$\varepsilon$} (A1); -%% \draw [->] (q0) to node[auto] {$\varepsilon$} (A2); -%% \end{tikzpicture} -%% \end{center} +De façon plus formelle, considérons un nouvel ensemble d'états $Q' = +(Q_1 \uplus Q_2) \setminus \{q_1,q_2\} \uplus \{q'_0\}$ où $\uplus$ +désigne la réunion disjointe (autrement dit, on prend la réunion +disjointe des états non-initiaux de $A_1$ et $A_2$ et on ajoute un +nouvel état $q'_0$), et la fonction $\varphi_1\colon Q_1 \to Q'$ qui +envoie $q_1$ sur $q'_0$ et tout autre état de $Q_1$ sur lui-même, et +$\varphi_2\colon Q_2 \to Q'$ de même. On définit alors l'automate +$A'$ dont l'ensemble d'états est $Q'$, l'état initial est $q'_0$, les +états finaux $F' = \varphi_1(F_1) \cup \varphi_2(F_2)$, et la relation +de transition $\delta'$ est formée des triplets $(\varphi_1(q),x,q')$ +où $q\in Q_1$ et $(\varphi_2(q),x,q')$ où $q\in Q_2$. + +(\emph{Remarque : } De façon équivalente, on peut fabriquer $A'$ en +ajoutant d'abord un unique état initial $q'_0$ à la réunion disjointe +de $A_1$ et $A_2$ et des ε-transitions de $q'_0$ vers $q_1$ et $q_2$, +puis en éliminant les ε-transitions qu'on vient d'ajouter +(cf. \ref{removal-of-epsilon-transitions}) ainsi que les états $q_1$ +et $q_2$ devenus inutiles. Cela donne le même résultat que ce qui +vient d'être dit.) Il est alors clair qu'un chemin de l'état initial à un état final dans cet automate $A'$ consiste soit en un chemin d'un état initial à un @@ -2264,69 +2395,180 @@ bien $L_{A'} = L_1 \cup L_2$. \begin{prop}\label{nfa-concatenation} Si $L_1,L_2$ sont des langages reconnaissables (sur un même alphabet $\Sigma$), alors la concaténation $L_1 L_2$ est -reconnaissable ; de plus, un εNFA la reconnaissant se déduit -algorithmiquement de εNFA reconnaissant $L_1$ et $L_2$. +reconnaissable ; de plus, un NFA la reconnaissant se déduit +algorithmiquement de NFA reconnaissant $L_1$ et $L_2$. \end{prop} \begin{proof} -Par hypothèse, il existe des εNFA $A_1 = (Q_1,I_1,F_1,\delta_1)$ et -$A_2 = (Q_2,I_2,F_2,\delta_2)$ tels que $L_1 = L_{A_1}$ et $L_2 = -L_{A_2}$. Considérons le εNFA $A'$ dont l'ensemble d'états est $Q' = -Q_1 \uplus Q_2$ où $\uplus$ désigne la réunion disjointe, dont les -états initiaux sont $I_1$, les états finaux sont $F_2$, et la relation -de transition $\delta'$ est $\delta_1 \cup \delta_2$ (l'ensemble des -transitions existant déjà dans $A_1$ ou $A_2$) à quoi on ajoute encore -une ε-transition $(q,\varepsilon,q')$ pour chaque $q\in F_1$ et -chaque $q'\in I_2$. Symboliquement : +Par hypothèse, il existe des NFA reconnaissant $L_1$ et $L_2$ : +d'après \ref{standard-automaton-lemma}, on peut supposer qu'ils sont +\emph{standards} en ce sens qu'ils ont un unique état initial qui +n'est la cible d'aucune transition. Disons que $A_1 = +(Q_1,\{q_1\},F_1,\delta_1)$ et $A_2 = (Q_2,\{q_2\},F_2,\delta_2)$ sont +des NFA standards tels que $L_1 = L_{A_1}$ et $L_2 = L_{A_2}$. + +L'automate $A'$ s'obtient en réunissant $A_1$ et $A_2$, en ne gardant +que les états finaux de $A_2$, en supprimant $q_2$ et en remplaçant +chaque transition sortant de $q_2$ par une transition identiquement +étiquetée partant de chaque état final de $A_1$ : \begin{center} -\begin{tikzpicture}[>=latex,line join=bevel,automaton] -\node (A1) at (0bp,0bp) [draw,dotted,circle,initial] {$A_1$}; -\node (A2) at (70bp,0bp) [draw,dotted,circle,final] {$A_2$}; - \draw [->] (A1) to node[auto] {$\varepsilon$} (A2); +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(A.base)] +\node (A) at (0bp,0bp) [draw,dotted,circle,minimum size=60bp] {$A_1$}; +\node (q0) at (-35bp,0bp) [draw,circle,state,initial,fill=white] {$q_1$}; +\node (i1) at (-10bp,20bp) [circle,inner sep=2bp,fill] {}; +\node (i2) at (-10bp,-20bp) [circle,inner sep=2bp,fill] {}; +\node (o1) at (15bp,20bp) [circle,inner sep=2bp,fill] {}; +\node (o2) at (25bp,0bp) [circle,inner sep=2bp,fill] {}; +\node (o3) at (15bp,-20bp) [circle,inner sep=2bp,fill] {}; +\draw [->] (q0) -- (i1); +\draw [->] (q0) -- (i2); +\draw [->] (o1) -- ($(o1.east)+(3ex,0)$); +\draw [->] (o2) -- ($(o2.east)+(3ex,0)$); +\draw [->] (o3) -- ($(o3.east)+(3ex,0)$); +\end{tikzpicture} +et +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(A.base)] +\node (A) at (0bp,0bp) [draw,dotted,circle,minimum size=60bp] {$A_2$}; +\node (q0) at (-35bp,0bp) [draw,circle,state,initial,fill=white] {$q_2$}; +\node (i1) at (-10bp,20bp) [circle,inner sep=2bp,fill] {}; +\node (i2) at (-10bp,-20bp) [circle,inner sep=2bp,fill] {}; +\node (o1) at (15bp,20bp) [circle,inner sep=2bp,fill] {}; +\node (o2) at (25bp,0bp) [circle,inner sep=2bp,fill] {}; +\node (o3) at (15bp,-20bp) [circle,inner sep=2bp,fill] {}; +\draw [->] (q0) -- (i1); +\draw [->] (q0) -- (i2); +\draw [->] (o1) -- ($(o1.east)+(3ex,0)$); +\draw [->] (o2) -- ($(o2.east)+(3ex,0)$); +\draw [->] (o3) -- ($(o3.east)+(3ex,0)$); +\end{tikzpicture} +\\deviennent\\ +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(A.base)] +\node (A1) at (0bp,0bp) [draw,dotted,circle,minimum size=60bp] {\phantom{$A_1$}}; +\node (q0) at (-35bp,0bp) [draw,circle,state,initial,fill=white] {$q_1$}; +\node (A1) at (90bp,0bp) [draw,dotted,circle,minimum size=60bp] {\phantom{$A_2$}}; +\node (i1) at (-10bp,20bp) [circle,inner sep=2bp,fill] {}; +\node (i2) at (-10bp,-20bp) [circle,inner sep=2bp,fill] {}; +\node (l1) at (15bp,20bp) [circle,inner sep=2bp,fill] {}; +\node (l2) at (25bp,0bp) [circle,inner sep=2bp,fill] {}; +\node (l3) at (15bp,-20bp) [circle,inner sep=2bp,fill] {}; +\node (r1) at (80bp,20bp) [circle,inner sep=2bp,fill] {}; +\node (r2) at (80bp,-20bp) [circle,inner sep=2bp,fill] {}; +\node (o1) at (105bp,20bp) [circle,inner sep=2bp,fill] {}; +\node (o2) at (115bp,0bp) [circle,inner sep=2bp,fill] {}; +\node (o3) at (105bp,-20bp) [circle,inner sep=2bp,fill] {}; +\draw [->] (q0) -- (i1); +\draw [->] (q0) -- (i2); +\draw [->] (l1) to[out=0,in=180] (r1); +\draw [->] (l1) to[out=0,in=180] (r2); +\draw [->] (l2) to[out=0,in=180] (r1); +\draw [->] (l2) to[out=0,in=180] (r2); +\draw [->] (l3) to[out=0,in=180] (r1); +\draw [->] (l3) to[out=0,in=180] (r2); +\draw [->] (o1) -- ($(o1.east)+(3ex,0)$); +\draw [->] (o2) -- ($(o2.east)+(3ex,0)$); +\draw [->] (o3) -- ($(o3.east)+(3ex,0)$); \end{tikzpicture} \end{center} -Il est alors clair qu'un chemin d'un état initial à un état final dans -cet automate $A'$ consiste en un chemin d'un état initial à un état -final dans $A_1$ suivi d'une ε-transition et d'un chemin d'un état -initial à un état final dans $A_2$. On a donc bien $L_{A'} = L_1 -L_2$. +De façon plus formelle, considérons un nouvel ensemble d'états $Q' = +(Q_1 \uplus Q_2) \setminus \{q_2\}$ où $\uplus$ désigne la réunion +disjointe. On définit alors l'automate $A'$ dont l'ensemble d'états +est $Q'$, l'état initial est $q_1$, les états finaux $F' = F_2$, et la +relation de transition $\delta$ est la réunion de $\delta_1$, de +l'ensemble des triplets $(q,x,q') \in \delta_2$ tels que $q\neq q_2$, +et enfin de l'ensemble des triplets $(q,x,q')$ tels que $(q_2,x,q') +\in \delta_2$ et que $q\in F_1$. + +(\emph{Remarque : } De façon équivalente, on peut fabriquer $A'$ en +ajoutant d'abord à la réunion disjointe de $A_1$ et $A_2$ une +ε-transition de chaque état final de $A_1$ vers $q_2$, puis en +éliminant les ε-transitions qu'on vient d'ajouter +(cf. \ref{removal-of-epsilon-transitions}) ainsi que l'état $q_2$ +devenu inutile. Cela donne le même résultat que ce qui vient d'être +dit.) + +Il est alors clair qu'un chemin de l'état initial $q_1$ à un état +final dans cet automate $A'$ consiste en un chemin de $q_1$ à un état +final dans $A_1$ suivi d'un chemin de $q_2$ à un état final dans $A_2$ +(moins $q_2$ lui-même). On a donc bien $L_{A'} = L_1 L_2$. \end{proof} \begin{prop}\label{nfa-star} Si $L$ est un langage reconnaissable (sur un alphabet $\Sigma$), alors -l'étoile de Kleene $L^*$ est reconnaissable ; de plus, un εNFA la -reconnaissant se déduit algorithmiquement de εNFA reconnaissant $L$. +l'étoile de Kleene $L^*$ est reconnaissable ; de plus, un NFA la +reconnaissant se déduit algorithmiquement de NFA reconnaissant $L$. \end{prop} \begin{proof} -Par hypothèse, il existe un εNFA $A = (Q,I,F,\delta)$ tel que $L = -L_A$. Considérons le εNFA $A'$ dont l'ensemble d'états est $Q' = -\{q_0\} \uplus Q$ (où $q_0$ est un nouvel état) dont les états -initiaux sont $I' = \{q_0\}$, les états finaux sont $F' = \{q_0\}$, et -la relation de transition $\delta'$ est $\delta$ (l'ensemble des -transitions existant déjà dans $A$) à quoi on ajoute encore une -ε-transition $(q_0,\varepsilon,q)$ pour chaque $q\in I$ et une autre -$(q,\varepsilon,q_0)$ pour chaque $q\in F$. Symboliquement : +Par hypothèse, il existe un NFA reconnaissant $L$ : +d'après \ref{standard-automaton-lemma}, on peut supposer qu'ils est +\emph{standard} en ce sens qu'il a un unique état initial qui n'est la +cible d'aucune transition. Disons que $A = (Q,\{q_0\},F,\delta)$ est +un NFA standard tel que $L = L_A$. + +L'automate $A'$ s'obtient en ajoutant à $A$, pour chaque transition +sortant de $q_0$, une transition identiquement étiquetée partant de +chaque état final de $A$, et en rendant $q_0$ final s'il ne l'était +pas déjà : \begin{center} -\begin{tikzpicture}[>=latex,line join=bevel,automaton] -\node (q0) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$q_0$}; -\node (A) at (70bp,0bp) [draw,dotted,circle] {$A$}; - \draw [->,out=45,in=135] (q0) to node[auto] {$\varepsilon$} (A); - \draw [->,out=225,in=315] (A) to node[auto] {$\varepsilon$} (q0); +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(A.base)] +\node (A) at (0bp,0bp) [draw,dotted,circle,minimum size=60bp] {$A$}; +\node (q0) at (-35bp,0bp) [draw,circle,state,initial,fill=white] {$q_0$}; +\node (i1) at (-10bp,20bp) [circle,inner sep=2bp,fill] {}; +\node (i2) at (-10bp,-20bp) [circle,inner sep=2bp,fill] {}; +\node (o1) at (15bp,20bp) [circle,inner sep=2bp,fill] {}; +\node (o2) at (25bp,0bp) [circle,inner sep=2bp,fill] {}; +\node (o3) at (15bp,-20bp) [circle,inner sep=2bp,fill] {}; +\draw [->] (q0) -- (i1); +\draw [->] (q0) -- (i2); +\draw [->] (o1) -- ($(o1.east)+(3ex,0)$); +\draw [->] (o2) -- ($(o2.east)+(3ex,0)$); +\draw [->] (o3) -- ($(o3.east)+(3ex,0)$); +\end{tikzpicture} +devient +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(A.base)] +\node (A) at (0bp,0bp) [draw,dotted,circle,minimum size=60bp] {\phantom{$A$}}; +\node (q0) at (-35bp,0bp) [draw,circle,state,initial,accepting below,fill=white] {$q_0$}; +\node (i1) at (-10bp,20bp) [circle,inner sep=2bp,fill] {}; +\node (i2) at (-10bp,-20bp) [circle,inner sep=2bp,fill] {}; +\node (o1) at (15bp,20bp) [circle,inner sep=2bp,fill] {}; +\node (o2) at (25bp,0bp) [circle,inner sep=2bp,fill] {}; +\node (o3) at (15bp,-20bp) [circle,inner sep=2bp,fill] {}; +\draw [->] (q0) -- (i1); +\draw [->] (q0) -- (i2); +\draw [->] (o1) -- ($(o1.east)+(3ex,0)$); +\draw [->] (o2) -- ($(o2.east)+(3ex,0)$); +\draw [->] (o3) -- ($(o3.east)+(3ex,0)$); +\draw [->] (o1) -- (i1); +\draw [->] (o1) -- (i2); +\draw [->] (o2) -- (i1); +\draw [->] (o2) -- (i2); +\draw [->] (o3) -- (i1); +\draw [->] (o3) -- (i2); \end{tikzpicture} \end{center} -Il est alors clair qu'un chemin de l'état initial $q_0$ à l'état final -$q_0$ dans cet automate $A'$ consiste en un nombre quelconque +De façon plus formelle, on considère l'automate $A'$ dont l'ensemble +d'états est $Q' := Q$, l'état initial est $q_0$, les états finaux $F' +:= F$, et la relation de transition $\delta'$ est la réunion de +$\delta$ et de l'ensemble des triplets $(q,x,q')$ tels que $(q_0,x,q') +\in \delta$ et que $q \in F$. + +(\emph{Remarque : } De façon équivalente, on peut fabriquer $A'$ en +ajoutant d'abord à $A$ une ε-transition de chaque état final de $A$ +vers $q_0$, puis en éliminant les ε-transitions qu'on vient d'ajouter +(cf. \ref{removal-of-epsilon-transitions}), et enfin en marquant $q_0$ +comme final. Cela donne le même résultat que ce qui vient d'être +dit.) + +Il est alors clair qu'un chemin de l'état initial $q_0$ à un état +final dans cet automate $A'$ consiste en un nombre quelconque (éventuellement nul) de chemins d'un état initial à un état final -dans $A$ chacun précédé d'une ε-transition de $q_0$ vers l'état -initial de $A$ en question et suivi d'une ε-transition de l'état final -de $A$ en question vers $q_0$. On a donc bien $L_{A'} = L^*$. +dans $A$. On a donc bien $L_{A'} = L^*$. \end{proof} \begin{cor}\label{rational-languages-are-recognizable} -Tout langage rationnel est reconnaissable ; de plus, un εNFA le +Tout langage rationnel est reconnaissable ; de plus, un NFA le reconnaissant se déduit algorithmiquement d'une expression rationnelle le dénotant. (Et en particulier, il est possible de décider algorithmiquement si un mot vérifie une expression rationnelle.) @@ -2340,11 +2582,10 @@ propositions \ref{nfa-union}, \ref{nfa-concatenation} et \ref{nfa-star}. Pour décider si un mot vérifie une expression rationnelle, on peut -commencer par transformer cette expression rationnelle en εNFA (i.e., -construire un εNFA reconnaissant le langage qu'elle dénote) comme on -vient de l'expliquer, et transformer ensuite cet automate en DFA -quitte à éliminer les ε-transitions -(cf. \ref{removal-of-epsilon-transitions}) et à déterminiser +commencer par transformer cette expression rationnelle en NFA standard +(i.e., construire un NFA standard reconnaissant le langage qu'elle +dénote) comme on vient de l'expliquer, et transformer ensuite cet +automate en DFA quitte déterminiser (cf. \ref{determinization-of-nfa}), après quoi il est facile de tester si l'automate accepte le mot. \end{proof} |