diff options
| -rw-r--r-- | figs/example10.dot | 18 | ||||
| -rw-r--r-- | notes-inf105.tex | 63 |
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 \[ |