diff options
| -rw-r--r-- | notes-inf105.tex | 150 |
1 files changed, 140 insertions, 10 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index 1098ac5..d31b9dd 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -343,15 +343,15 @@ définition ci-dessus, on pourra prendre $u_0 = \varepsilon$ et $v_1 = a$ et $u_1 = bb$ et $v_2 = c$ et $u_2 = a$ et $v_3 = b$ et $u_3 = \varepsilon$). -\thingy Si $w = x_1\cdots x_n$, où $x_1,\ldots,x_n \in \Sigma$, est un -mot de longueur $n$ sur un alphabet $\Sigma$, alors on définit son mot -\textbf{miroir} ou \textbf{transposé}, parfois noté $w^{\textsf{R}}$ -ou $w^{\textsf{T}}$ (parfois les exposants sont écrits à gauche), -comme le mot $x_n\cdots x_1$ dont les lettres sont les mêmes que -celles de $w$ mais dans l'ordre inverse. À titre d'exemple, -$(ababb)^{\textsf{R}} = bbaba$. On remarquera que $(w_1 -w_2)^{\textsf{R}} = w_2^{\textsf{R}} w_1^{\textsf{R}}$ si $w_1,w_2$ -sont deux mots quelconques. +\thingy\label{definition-mirror-word} Si $w = x_1\cdots x_n$, où +$x_1,\ldots,x_n \in \Sigma$, est un mot de longueur $n$ sur un +alphabet $\Sigma$, alors on définit son mot \textbf{miroir} ou +\textbf{transposé}, parfois noté $w^{\textsf{R}}$ ou $w^{\textsf{T}}$ +(parfois les exposants sont écrits à gauche), comme le mot $x_n\cdots +x_1$ dont les lettres sont les mêmes que celles de $w$ mais dans +l'ordre inverse. À titre d'exemple, $(ababb)^{\textsf{R}} = bbaba$. +On remarquera que $(w_1 w_2)^{\textsf{R}} = w_2^{\textsf{R}} +w_1^{\textsf{R}}$ si $w_1,w_2$ sont deux mots quelconques. Un mot $w$ est dit \textbf{palindrome} lorsque $w = w^{\textsf{R}}$. @@ -537,6 +537,12 @@ diffère de $L^*$ seulement en ce qu'il ne contient pas $\varepsilon$ ; tandis que si $\varepsilon$ appartient déjà à $L$, alors $L^+$ est égal à $L^*$. En toute généralité, on a $L^+ = LL^*$. +\thingy\label{definition-mirror-language} En rappelant la définition +du mot miroir faite en \ref{definition-mirror-word}, si $L$ est un +langage sur l'alphabet $\Sigma$, on définit le langage miroir +$L^{\mathsf{R}}$ comme l'ensemble des mots miroirs des mots de $L$, +c'est-à-dire $L^{\mathsf{R}} = \{w^{\mathsf{R}} : w \in L\}$. + \subsection{Langages rationnels et expressions rationnelles} @@ -988,7 +994,7 @@ quelconque de $c$. (Ce langage est aussi désigné par l'expression rationnelle $c{*}ac{*}bc{*}$.) -\begin{prop} +\begin{prop}\label{completion-of-dfai} Soit $A = (Q,q_0,F,\delta)$ un DFAI sur un alphabet $\Sigma$. Alors il existe un DFA $A' = (Q',q'_0,F',\delta')$ (sur le même alphabet $\Sigma$) qui soit équivalent à $A$ au sens où il reconnaît @@ -1542,6 +1548,130 @@ incomplet, mais ce n'est pas un phénomène général : en général il faut s'attendre à obtenir un NFA.) +\section{Langages reconnaissables et langages rationnels} + +\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. + +Nous allons maintenant montrer que les langages reconnaissables sont +stables par différentes opérations : complémentaire, union, +intersection, concaténation et étoile de Kleene. + +\begin{prop} +Si $L$ est un langage reconnaissable sur un alphabet $\Sigma$, alors +le complémentaire $\Sigma^*\setminus L$ de $L$ est reconnaissable ; de +plus, un DFA reconnaissant l'un se déduit algorithmiquement d'un DFA +reconnaissant l'autre. +\end{prop} +\begin{proof} +Par hypothèse, il existe un DFA $A = (Q,q_0,F,\delta)$ tel que $L = +L_A$. Considérons le DFA $A'$ défini par l'ensemble d'états $Q' = Q$, +l'état initial $q'_0 = q_0$, la fonction de transition $\delta' = +\delta$ et pour seul changement l'ensemble d'états finaux $F' = Q +\setminus F$ complémentaire de $F$. + +Si $w \in \Sigma^*$, on a $w \in L_{A'}$ si et seulement si +$\delta^{\prime*}(q_0,w) \in F'$, c'est-à-dire $\delta^*(q_0,w) \in +F'$ (puisque $\delta' = \delta$), c'est-à-dire $\delta^*(q_0,w) +\not\in F$ (par définition du complémentaire), c'est-à-dire $w \not\in +L_A$. Ceci montre bien que $L_{A'}$ est le complémentaire de $L_A$. +\end{proof} + +\thingy Cette démonstration a utilisé la caractérisation des langages +reconnaissables par les DFA : il était crucial de le faire, et les +autres sortes d'automates définis plus haut n'auraient pas permis +d'arriver (simplement) à la même conclusion. Pourquoi ? + +\begin{prop} +Si $L_1,L_2$ sont des langages reconnaissables (sur un même +alphabet $\Sigma$), alors la réunion $L_1\cup L_2$ et l'intersection +$L_1\cap L_2$ sont reconnaissables ; de plus, un DFA reconnaissant +l'un comme l'autre se déduit algorithmiquement de DFA reconnaissant +$L_1$ et $L_2$. +\end{prop} +\begin{proof} +Par hypothèse, il existe des DFA $A_1 = (Q_1,q_{0,1},F_1,\delta_1)$ et +$A_2 = (Q_2,q_{0,2},F_2,\delta_2)$ tels que $L_1 = L_{A_1}$ et $L_2 = +L_{A_2}$. Considérons le DFA $A'$ défini par l'ensemble d'états $Q' = +Q_1 \times Q_2$, l'état initial $q'_0 = (q_{0,1},q_{0,2})$, la +fonction de transition $\delta' \colon ((p_1,p_2),x) \mapsto +(\delta_1(p_1,x), \delta_2(p_2,x))$ et pour ensemble d'états finaux +$F' = (F_1\times Q_2) \cup (Q_1 \times F_2)$ (si on cherche à +reconnaître $L_1\cup L_2$) respectivement $F' = F_1\times F_2$ (si on +cherche à reconnaître $L_1\cap L_2$). Remarquons que $(p_1,p_2) \in +Q'$ appartient à $F' = (F_1\times Q_2) \cup (Q_1 \times F_2)$ +respectivement $F' = F_1\times F_2$ si et seulement si $p_1 \in F_1$ +ou $p_2 \in F_2$ respectivement $p_1 \in F_1$ et $p_2 \in F_2$. Par +ailleurs, si $w\in \Sigma^*$, on a $\delta'(q_0',w) = +(\delta_1(q_{0,1},w), \delta_2(q_{0,2},w))$. On voit donc qu'un mot +$w$ appartient à $L_{A'}$ si et seulement il appartient à $L_1 \cup +L_2$ respectivement $L_1 \cap L_2$, ce qu'il fallait démontrer. +\end{proof} + +\thingy On pouvait aussi traiter uniquement l'une des deux opérations +booléennes et déduire l'autre par complémentaire, mais le gain de +place est faible (et la construction est exactement la même). + +La construction ci-dessus est un \emph{produit} de DFA (que ce soit +pour prendre la réunion ou l'intersection). La construction produit +fonctionnerait encore avec les NFA \emph{pour la réunion de langages + mais pas pour l'intersection} : il est intéressant de réfléchir à +pourquoi (essentiellement, ce qui casse la symétrie est que dans un +NFA, un mot est accepté dès qu'\emph{il existe} un chemin qui +l'accepte, or le quantificateur $\exists$ distribue sur les +disjonctions mais pas sur les conjonctions). + +Ceci étant, il existe une construction plus simple pour faire la +réunion $L_1 \cup L_2$ de deux langages définis par des εNFA $A_1$ et +$A_2$ : il suffit de construire l'automate $A'$ dont l'ensemble +d'états est la réunion disjointe de ceux de $A_1$ et de $A_2$ et d'un +nouvel état $q_0$ (seul état initial de $A'$), garder les états finaux +de $A_1$ et de $A_2$ (i.e., prendre leur réunion), ainsi que leurs +transitions, et ajouter des transitions spontanées de $q_0$ vers les +états initiaux de $A_1$ et vers ceux de $A_2$. Symboliquement : + +\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) {$A_1$}; +\node (A2) at (50bp,-30bp) {$A_2$}; + \draw [->] (q0) to node[auto] {$\varepsilon$} (A1); + \draw [->] (q0) to node[auto] {$\varepsilon$} (A2); +\end{tikzpicture} +\end{center} + +\begin{prop} +Si $L$ est un langage reconnaissable sur un alphabet $\Sigma$, alors +le langage miroir (cf. \ref{definition-mirror-language}) +$L^{\mathsf{R}}$ de $L$ est reconnaissable ; de plus, un NFA ou εNFA +reconnaissant l'un se déduit algorithmiquement d'un NFA ou εNFA +reconnaissant l'autre. +\end{prop} +\begin{proof} +Par hypothèse, il existe un εNFA ou un NFA $A = (Q,I,F,\delta)$ tel +que $L = L_A$. Considérons l'automate $A'$ de même type défini par +l'ensemble d'états $Q' = Q$ et inversant toutes les flèches de $A$, +c'est-à-dire $I' = F$ et $F' = I$ et $(q,t,q') \in \delta'$ si et +seulement si $(q',t,q) \in \delta$. Un chemin existe dans $A'$ si et +seulement si le même chemin inversé existe dans $A$, ce qui montre +qu'un mot appartient à $L_{A'}$ si et seulement si son miroir +appartient à $L_A$. +\end{proof} + +\thingy Alors que les constructions du complémentaire et de +l'intersection s'effectuaient naturellement sur les DFA, celle du +langage miroir s'effectue naturellement sur les NFA. (On peut, bien +sûr, considérer un DFA comme un NFA particulier, et effectuer dessus +l'opération d'inversion des flèches qu'on vient de décrire, mais en +général on n'obtiendra pas un DFA, seulement un NFA.) + + % % % |