summaryrefslogtreecommitdiffstats
path: root/notes-inf105.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-10-30 13:18:00 (GMT)
committerDavid A. Madore <david+git@madore.org>2017-10-30 13:18:00 (GMT)
commita3928191c06a3fa654c385b2a54c2195bcbe007b (patch)
tree3d008c6b79423003ef90f93b82fe4176d0e348dd /notes-inf105.tex
parent19b8cdeed8635dc1ed48d9620da1dbcf1e88cabe (diff)
downloadinf105-a3928191c06a3fa654c385b2a54c2195bcbe007b.zip
inf105-a3928191c06a3fa654c385b2a54c2195bcbe007b.tar.gz
inf105-a3928191c06a3fa654c385b2a54c2195bcbe007b.tar.bz2
Illustration for the pumping lemma.
Diffstat (limited to 'notes-inf105.tex')
-rw-r--r--notes-inf105.tex35
1 files changed, 35 insertions, 0 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex
index 4831e7f..9a4c5b1 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -3502,6 +3502,41 @@ premier état répété, et soit $j_1$ la précédente occurrence (forcément
unique) de cet état, c'est-à-dire l'indice tel que $j_1<j_2$ et
$q_{j_1} = q_{j_2}$.
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\draw[draw=none,fill=green!20!white] (-58.476bp,-58.476bp) rectangle (58.476bp,58.476bp);
+\draw[dotted] (29.238bp,50.642bp) arc (60:-100:58.476bp);
+\draw[draw=none,fill=red!20!white] (-188.476bp,-25bp) rectangle (-68.476bp,25bp);
+\draw[draw=none,fill=blue!20!white] (-48.476bp,-25bp) rectangle (110bp,25bp);
+\node[anchor=south west] at (-188.476bp,-25bp) {$u$};
+\node[anchor=south east] at (58.476bp,-58.476bp) {$v$};
+\node[anchor=south east] at (110bp,-25bp) {$w$};
+\node (q0) at (-198.476bp,0bp) [draw,circle,state,fill=white,initial] {\vbox to0pt{\vss\hbox to0pt{$q_0$\hss}}\phantom{$q_{j_0}$}};
+\node (q1) at (-138.476bp,0bp) [draw,circle,state,fill=white] {\vbox to0pt{\vss\hbox to0pt{$q_1$\hss}}\phantom{$q_{j_0}$}};
+\node (q2) at (-98.476bp,0bp) {$\cdots$};
+\node (qj1) at (-58.476bp,0bp) [draw,circle,state,fill=white] {\vbox to0pt{\vss\hbox to0pt{$q_{j_1}$\hss}}\phantom{$q_{j_0}$}};
+\node (qj1p1) at (-44.795bp,37.588bp) [draw,circle,state,fill=white] {\phantom{$q_{j_0}$}};
+\node (qj1p2) at (-10.154bp,57.588bp) [draw,circle,state,fill=white] {\phantom{$q_{j_0}$}};
+\node (qj1p3) at (29.238bp,50.642bp) {};
+\node (qj2m2) at (-10.154bp,-57.588bp) {};
+\node (qj2m1) at (-44.795bp,-37.588bp) [draw,circle,state,fill=white] {\phantom{$q_{j_0}$}};
+\node (qj2p1) at (0bp,0bp) [draw,circle,state,fill=white] {\phantom{$q_{j_0}$}};
+\node (qj2p2) at (60bp,0bp) {$\cdots$};
+\node (qn) at (120bp,0bp) [draw,circle,state,fill=white,final] {\vbox to0pt{\vss\hbox to0pt{$q_n$\hss}}\phantom{$q_{j_0}$}};
+\draw[->] (q0) -- node[auto] {\footnotesize $x_1$} (q1);
+\draw[->] (q1) -- (q2);
+\draw[->] (q2) -- node[auto] {\footnotesize $x_{j_1}$} (qj1);
+\draw[->] (qj1) -- node[auto] {\footnotesize $x_{j_1+1}$} (qj1p1);
+\draw[->] (qj1p1) -- node[auto] {\footnotesize $x_{j_1+2}$} (qj1p2);
+\draw[->] (qj1p2) -- (qj1p3);
+\draw[->] (qj2m2) -- (qj2m1);
+\draw[->] (qj2m1) -- node[auto] {\footnotesize $x_{j_2}$} (qj1);
+\draw[->] (qj1) -- node[auto] {\footnotesize $x_{j_2+1}$} (qj2p1);
+\draw[->] (qj2p1) -- (qj2p2);
+\draw[->] (qj2p2) -- node[auto] {\footnotesize $x_n$}(qn);
+\end{tikzpicture}
+\end{center}
+
Posons $u = x_1\cdots x_{j_1}$ (le préfixe de $t$ de longueur $j_1$,
qui est le mot vide si $j_1 = 0$) et $v = x_{j_1+1}\cdots x_{j_2}$ (de
longueur $j_2 - j_1$), et enfin $w = x_{j_2+1}\cdots x_n$ (le suffixe