diff options
| author | David A. Madore <david+git@madore.org> | 2017-10-30 14:18:00 +0100 |
|---|---|---|
| committer | David A. Madore <david+git@madore.org> | 2017-10-30 14:18:00 +0100 |
| commit | a3928191c06a3fa654c385b2a54c2195bcbe007b (patch) | |
| tree | 3d008c6b79423003ef90f93b82fe4176d0e348dd | |
| parent | 19b8cdeed8635dc1ed48d9620da1dbcf1e88cabe (diff) | |
| download | inf105-a3928191c06a3fa654c385b2a54c2195bcbe007b.tar.gz inf105-a3928191c06a3fa654c385b2a54c2195bcbe007b.tar.bz2 inf105-a3928191c06a3fa654c385b2a54c2195bcbe007b.zip | |
Illustration for the pumping lemma.
| -rw-r--r-- | notes-inf105.tex | 35 |
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 |