Add another example of state elimination (limited-depth balanced parentheses).

2 files changed, 81 insertions, 0 deletions

diff --git a/figs/example10.dot b/figs/example10.dot
new file mode 100644
index 0000000..91775c5
--- /dev/null
+++ b/figs/example10.dot
@@ -0,0 +1,18 @@
+digraph example10 {
+	rankdir="LR";
+	node [texmode="math",shape="circle",style="state"];
+	q0 [style="state,initial,final,accepting below",label="0"];
+	q1 [style="state",label="1"];
+	q2 [style="state",label="2"];
+	q3 [style="state",label="3"];
+	q4 [style="state",label="4"];
+	edge [texmode="math",lblstyle="auto"];
+	q0 -> q1 [label="a"];
+	q1 -> q0 [label="b"];
+	q1 -> q2 [label="a"];
+	q2 -> q1 [label="b"];
+	q2 -> q3 [label="a"];
+	q3 -> q2 [label="b"];
+	q3 -> q4 [label="a"];
+	q4 -> q3 [label="b"];
+}
diff --git a/notes-inf105.tex b/notes-inf105.tex
index bbb8582..8862e5d 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -3544,6 +3544,60 @@ conduit à l'automate suivant :
 \noindent et finalement à l'expression rationnelle
 $(0|11|10(1|00){*}01){*}$, qui est équivalente à la précédente.
 
+\medbreak
+
+\thingy Donnons encore l'exemple du DFAI suivant :
+
+\begin{center}
+%%% begin example10 %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (q1) at (97bp,20.28bp) [draw,circle,state] {$1$};
+  \node (q0) at (18bp,20.28bp) [draw,circle,state,initial,final,accepting below] {$0$};
+  \node (q3) at (255bp,20.28bp) [draw,circle,state] {$3$};
+  \node (q2) at (176bp,20.28bp) [draw,circle,state] {$2$};
+  \node (q4) at (334bp,20.28bp) [draw,circle,state] {$4$};
+  \draw [->] (q1) ..controls (74.757bp,3.6593bp) and (64.084bp,-1.2803bp)  .. (54bp,1.2803bp) .. controls (50.042bp,2.2853bp) and (46.047bp,3.838bp)  .. node[auto] {$b$} (q0);
+  \draw [->] (q2) ..controls (203.66bp,20.28bp) and (215.82bp,20.28bp)  .. node[auto] {$a$} (q3);
+  \draw [->] (q2) ..controls (153.76bp,3.6593bp) and (143.08bp,-1.2803bp)  .. (133bp,1.2803bp) .. controls (129.04bp,2.2853bp) and (125.05bp,3.838bp)  .. node[auto] {$b$} (q1);
+  \draw [->] (q3) ..controls (282.66bp,20.28bp) and (294.82bp,20.28bp)  .. node[auto] {$a$} (q4);
+  \draw [->] (q3) ..controls (232.76bp,3.6593bp) and (222.08bp,-1.2803bp)  .. (212bp,1.2803bp) .. controls (208.04bp,2.2853bp) and (204.05bp,3.838bp)  .. node[auto] {$b$} (q2);
+  \draw [->] (q0) ..controls (45.659bp,20.28bp) and (57.817bp,20.28bp)  .. node[auto] {$a$} (q1);
+  \draw [->] (q4) ..controls (311.76bp,3.6593bp) and (301.08bp,-1.2803bp)  .. (291bp,1.2803bp) .. controls (287.04bp,2.2853bp) and (283.05bp,3.838bp)  .. node[auto] {$b$} (q3);
+  \draw [->] (q1) ..controls (124.66bp,20.28bp) and (136.82bp,20.28bp)  .. node[auto] {$a$} (q2);
+%
+\end{tikzpicture}
+
+%%% end example10 %%%
+\end{center}
+
+Il s'agit d'un automate « compteur limité », qui ne sait compter que
+de $0$ à $4$, incrémentant son compteur quand il reçoit un $a$ et le
+décrementant quand il reçoit un $b$ (et cessant de fonctionner si le
+compteur passe au-dessus du maximum ou en-dessous du minimum), et qui
+accepte finalement les mots dont le nombre de $b$ égale le nombre
+de $a$ sans qu'il y ait jamais eu plus de $b$ que de $a$ ni plus de
+quatre $a$ de plus que de $b$.  (On peut dire aussi qu'il s'agit d'une
+\emph{approximation} du langage des expressions bien-parenthésées
+définies en \ref{example-well-parenthesized-expressions} plus loin, où
+$a$ joue le rôle de parenthèse ouvrante et $b$ de parenthèse
+fermante ; l'approximation est due au fait qu'on n'accepte que quatre
+niveaux d'imbrication des « parenthèses ».)
+
+Si on élimine les états dans l'ordre $4,3,2,1,0$, on montre que le
+langage reconnu par cet automate est décrit par l'expression
+rationnelle $(a(a(a(ab){*}b){*}b){*}b){*}$.  Si on les élimine dans
+l'ordre $0,1,2,3,4$, en revanche, on obtient une expression de taille
+considérable\footnote{À savoir : $\underline{\varepsilon} \penalty0 \;
+  | \penalty0 \; a(ba){*}b \penalty0 \; | \penalty0 \;
+  a(ba){*}a(b(ba){*}a){*}b(ba){*}b \penalty0 \; | \penalty0 \;
+  a(ba){*}a(b(ba){*}a){*}a(b(b(ba){*}a){*}a){*}b(b(ba){*}a){*}b(ba){*}b
+  \penalty0 \; | \penalty0 \;
+  a(ba){*}a(b(ba){*}a){*}a(b(b(ba){*}a){*}a){*}a(b(b(b(ba){*}a){*}a){*}a){*}b(b(b(ba){*}a){*}a){*}b(b(ba){*}a){*}b(ba){*}b$
+  (mais si on la regarde d'assez près, on peut comprendre comment elle
+  fonctionne).}  et beaucoup moins transparente.
+
 \bigbreak
 
 Récapitulons le contenu essentiel à retenir comme conséquence
@@ -4714,6 +4768,15 @@ parenthésé est une expression bien-parenthésée entourée par une
 parenthèse ouvrante et une parenthèse fermante — c'est ce que traduit
 la grammaire).
 
+Soit dit en passant, ce langage algébrique des expressions
+bien-parenthésées n'est pas rationnel : la façon la plus simple de
+s'en convaincre est de remarquer que s'il l'était, son intersection
+avec le langage $\{a^i b^j : i,j\in\mathbb{N}\}$ dénoté par
+l'expression rationnelle $a{*}b{*}$ le serait aussi
+(par \ref{dfa-union-and-intersection}), or cette intersection est
+précisément le langage $\{a^n b^n : n\in\mathbb{N}\}$ dont on a montré
+en \ref{example-of-pumping-lemma} qu'il n'était pas algébrique.
+
 \thingy\label{example-grammar-equal-a-and-b} Sur l'alphabet $\Sigma =
 \{a,b\}$, montrons que la grammaire $G$ (d'axiome $S$) donnée par
 \[