From c20d0faea32e9310aee14dda85292fa207e98414 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Wed, 1 Nov 2017 00:57:40 +0100
Subject: Add another example of state elimination (limited-depth balanced
parentheses).
---
figs/example10.dot | 18 ++++++++++++++++
notes-inf105.tex | 63 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 81 insertions(+)
create mode 100644 figs/example10.dot
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
\[
--
cgit v1.2.3