summaryrefslogtreecommitdiffstats
path: root/notes-inf105.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2016-11-23 22:15:33 +0100
committerDavid A. Madore <david+git@madore.org>2016-11-25 15:47:00 +0100
commitbbd3b0440217a051d0c0c720e88e6f358d3687fc (patch)
tree7aef8892dc27369886c6e099080f3675bcc085b8 /notes-inf105.tex
parenta7aea4e4e8bd899596854733f592f73df927ec5c (diff)
downloadinf105-bbd3b0440217a051d0c0c720e88e6f358d3687fc.tar.gz
inf105-bbd3b0440217a051d0c0c720e88e6f358d3687fc.tar.bz2
inf105-bbd3b0440217a051d0c0c720e88e6f358d3687fc.zip
Stability of recognizable languages under boolean operations and mirror.
Diffstat (limited to 'notes-inf105.tex')
-rw-r--r--notes-inf105.tex150
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.)
+
+
%
%
%