Changeset 246

Timestamp:

Dec 8, 2010, 8:08:05 PM (14 years ago)

Author:

Rick van der Zwet

Message:

2.22 expantie.

Location:

liacs/TPFL2010/assignment1

Files:

• report.pdf (modified) ( previous)
• report.tex (modified) (2 diffs)

liacs/TPFL2010/assignment1/report.tex

@@ -99 +99 @@
 tweede plek variabele wordt gedefinieerd. De aanpak kan als volgt gezien worden:
 \begin{verbatim}
-1. controleren of |1| <= 2de 0-reeks (dmv 'knopen-strook').
-2. |2| tellen (onthouden dmv 'knopen-strook', dit is `variable' A).
-3. naar begin lopen.
-4. A-1 '1' instanties laten passeren. 
-5. |0| tellen (onthouden dmv 'knopen-strook'm dit is `variable' A).
-6. naar begin 2de 0-reeks lopen.
-7. 0-reeks vergelijken.
+1. controleren of |1| <= 2de 0-reeks dmv 'knopen-strook' (knopen 0.X en 1.X).
+2. |2| tellen onthouden dmv 'knopen-strook' (knopen 2.X).
+3. naar gewenste locatie lopen (knopen 3.X).
+4. |0| tellen onthouden dmv 'knopen-strook' (knopen 4.X).
+5. naar begin 2de 0-reeks lopen (knopen 5.X).
+6. 0-reeks vergelijken (knopen 6.X).
 \end{verbatim}
-Voor deze aanpak zijn 3 `knopen-stroken' nodig en 3 transitie-lagen. In totaal
-dus in ongeveer $O(6n)$ knopen.  Figuur~\ref{fig:2dfa} laat de \emph{2DFA}
-zien.
+Voor deze aanpak zijn 3 `knopen-stroken' nodig, 3 `transitie-lagen' en 1 controle
+strook. In totaal dus in ongeveer $O(7n)$ knopen.  Figuur~\ref{fig:2dfa} laat
+de \emph{2DFA} zien.
 
 
 \begin{figure}
 \center
-\begin{tikzpicture}
-\node[place,pin={[pin edge={style=<-,blue,thick,decorate,decoration={snake, pre length=4pt}}]left:}] (q00) {};
-\node[place] (q01) [right=of q00] {};
-\node[place] (q02) [right=of q01] {};
-\node[place] (q03) [right=of q02] {};
-\node[place] (q11) [below=of q01] {};
-\node[place] (q12) [below=of q02] {};
-\node[place] (q13) [below=of q03] {};
-\node[place] (q10) [below=of q00] {};
-\node[place] (q20) [below=of q10] {};
-\node[place] (q21) [below=of q11] {};
-\node[place] (q22) [below=of q12] {};
-%\node[place] (q2) [below=of q1] {};
-%\node[place,pin={[pin edge={style=-<,thick,decorate,decoration={snake, pre length=4pt}}]below:}] (q3) [below=of q2] {};
-%\node[place] (q01) [right=3cm of q1] {};
-%\node[place] (q02) [right=3cm of q2] {};
+\begin{tikzpicture}[node distance=20mm]
+\node[place,pin={[pin edge={style=<-,blue,thick,decorate,decoration={snake, pre length=4pt}}]left:}] (q00) {0.0};
+\node[place] (q01) [right=of q00] {0.1};
+\node[place] (q02) [right=of q01] {0.2};
+\node[place] (q03) [right=of q02] {0.3};
+\node[place] (q10) [below=of q00] {1.0};
+\node[place] (q11) [below=of q01] {1.1};
+\node[place] (q12) [below=of q02] {1.2};
+\node[place] (q13) [below=of q03] {1.3};
+\node[place] (q20) [below=of q10] {2.0};
+\node[place] (q21) [below=of q11] {2.1};
+\node[place] (q22) [below=of q12] {2.2};
+
+\node[place] (q30) [below=of q20] {3.0};
+\node[place] (q31) [below=of q21] {3.1};
+\node[place] (q32) [below=of q22] {3.2};
+\node[place] (q33) [right=of q32] {3.3};
+
+\node[place] (q40) [below=of q30] {4.0};
+\node[place] (q41) [below=of q31] {4.1};
+\node[place] (q42) [below=of q32] {4.2};
+
+\node[place] (q50) [below=of q40] {5.0};
+\node[place] (q51) [below=of q41] {5.1};
+\node[place] (q52) [below=of q42] {5.2};
+\node[place] (q53) [double,right=of q52] {5.3};
+
+\node[place] (q60) [below=2cm of q50] {6.0};
+\node[place] (q61) [below=2cm of q51] {6.1};
+\node[place] (q62) [below=2cm of q52] {6.2};
+\node[place] (q63) [right=of q62] {6.3};
+
 \path[->] 
-%          (q0) edge [decorate,decoration={snake}] node[left] {goto-2} (q00)
           (q00) edge               node[above] {3,R} (q01)
           (q01) edge               node[above] {1,R} (q02)
@@ -153 +167 @@
           (q21) edge               node[below] {2,L} (q22)
 
-
-%          (q1) edge              node[left] {2} (q2)
-%          (q2) edge              node[left] {2} (q3)
-%          (q1) edge [decorate,decoration={snake}] node[above] {0-length-check} (q01)
-%          (q2) edge [decorate,decoration={snake}] node[above] {0-length-check} (q02)
+          (q20) edge               node {0,L} (q30)
+          (q21) edge               node {0,L} (q31)
+          (q22) edge               node {0,L} (q32)
+
+          (q30) edge               node {1,L} (q31)
+          (q31) edge               node {1,L} (q32)
+          (q32) edge [bend left]   node {3,R} (q33)
+          (q32) edge [bend right]  node {1,R} (q33)
+
+          (q30) edge [loop below]  node {0,L} (q30)
+          (q31) edge [loop below]  node {0,L} (q31)
+          (q32) edge [loop below]  node {0,L} (q32)
+
+          (q33) edge [bend left]   node {0,R} (q42)
+          (q42) edge               node {0,R} (q41)
+          (q41) edge               node {0,R} (q40)
+
+          (q40) edge [bend right]  node {2,R} (q60)
+          (q40) edge               node {1,R} (q50)
+          (q41) edge [bend right]  node {2,R} (q61)
+          (q41) edge               node {1,R} (q51)
+          (q42) edge [bend right]  node {2,R} (q62)
+          (q42) edge               node {1,R} (q52)
+
+          (q50) edge [loop below]  node {$\begin{array}{c}1,R\\0,R\end{array}$} (q50)
+          (q51) edge [loop below]  node {$\begin{array}{c}1,R\\0,R\end{array}$} (q51)
+          (q52) edge [loop below]  node {$\begin{array}{c}1,R\\0,R\end{array}$} (q52)
+          (q50) edge [bend left,looseness=2]  node {2,R} (q60)
+          (q51) edge [bend left,looseness=2]  node {2,R} (q61)
+          (q52) edge [bend left,looseness=2]  node {2,R} (q62)
+ 
+          (q60) edge               node {0,R} (q61)
+          (q61) edge               node {0,R} (q62)
+          (q62) edge               node {0,R} (q63)
+          (q63) edge               node {4,R} (q53)
         ;
 \end{tikzpicture}
-\caption{Opdracht 2.22a uitgewerkt voor $n = 3$, niet geldige stappen zijn niet genoemd en moet allen naar een 'trap' knoop gestuurd worden}
+\caption{Opdracht 2.22a uitgewerkt voor $1 \le n \le 3$, niet geldige stappen zijn niet genoemd en moet allen naar een 'trap' knoop gestuurd worden. Uitbreiden dmv expanderen van `traviale' knopen.}
 \label{fig:2dfa}
 \end{figure}