Changeset 245 for liacs/TPFL2010/assignment1

Timestamp:

Dec 8, 2010, 6:50:15 PM (14 years ago)

Author:

Rick van der Zwet

Message:

Part of 3.22a

Location:

liacs/TPFL2010/assignment1

Files:

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

liacs/TPFL2010/assignment1/report.tex

@@ -75 +75 @@
 $xz \in L, yz \notin L$.
 
-De taal $M = {0}^* : |M|_0~is~een~priemgetal$  is een ander voorbeeld. Als we
+De taal $M = \{{0}^* : |M|_0~is~een~priemgetal\}$  is een ander voorbeeld. Als we
 kijken naar $aR_{l}b$ kan er altijd een $z$ gevormd worden zodanig dat $az \in
 M, bz \notin M$. Bijvoorbeeld $a = 0^3, b =0^5, z = 0^4$. Deze eigenschap wordt
@@ -93 +93 @@
 Als eerste kan de $F_n$ door een \emph{2DFA} van $O(n)$ toestanden geaccepteerd
 worden, welke aan te tonen is door eerst te kijken naar de eigenschappen van
-$F_n$ hierbij is de zien dat de $0$-reeks van de lengte $i^k$ zowel voor als na
+$F_n$ hierbij is de zien dat de $0$-reeks van de lengte $i_k$ zowel voor als na
 de $2^k$ moet voorkomen. Waarbij $2^k$ aangeeft, waar deze $0$-reeks gevonden
-kan worden e.g. bij welke $i_x$. De \emph{2DFA} moet dus twee dingen doen. Het
+kan worden bij de plek $k$. De \emph{2DFA} moet dus twee dingen doen. Het
 aantal keer nul op twee plekken vergelijken. Waarbij 1 plek vast staat en de
-tweede plek variabele wordt gedefinieerd. Dit lijkt mij controleren op twee los
-staande feiten. Hiervoor heb ik \underline{geen} antwoord gevonden. Ik kan
-enkel wat voor $O(n^2)$ bedenken, welke een idee is in Figuur~\ref{fig:idee}
-uitgewerkt is.
+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.
+\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.
 
 
@@ -106 +115 @@
 \center
 \begin{tikzpicture}
-\node[place,pin={[pin edge={style=<-,blue,thick,decorate,decoration={snake, pre length=4pt}}]left:}] (q0) {};
-\node[place] (q1) [below=of q0] {};
-\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] {};
+\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] {};
 \path[->] 
-          (q0) edge [decorate,decoration={snake}] node[left] {goto-2} (q1)
-          (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)
+%          (q0) edge [decorate,decoration={snake}] node[left] {goto-2} (q00)
+          (q00) edge               node[above] {3,R} (q01)
+          (q01) edge               node[above] {1,R} (q02)
+          (q01) edge [loop above]  node[above] {0,R} (q01)
+          (q02) edge               node[above] {1,R} (q03)
+          (q02) edge [loop above]  node[above] {0,R} (q02)
+          (q03) edge [loop above]  node[above] {0,R} (q03)
+
+          (q11) edge               node[above] {0,L} (q10)
+          (q12) edge [bend left]   node[below] {0,L} (q10)
+          (q13) edge [bend left]   node[below] {0,L} (q10)
+
+          (q01) edge               node {2,R} (q11)
+          (q02) edge               node {2,R} (q12)
+          (q03) edge               node {2,R} (q13)
+          (q13) edge               node[above] {2,R} (q12)
+          (q12) edge               node[above] {2,R} (q11)
+
+          (q10) edge               node {2,L} (q20)
+          (q20) edge               node[below] {2,L} (q21)
+          (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)
         ;
 \end{tikzpicture}
-\caption{Idee voor Opdracht 2.22a}
-\label{fig:idee}
+\caption{Opdracht 2.22a uitgewerkt voor $n = 3$, niet geldige stappen zijn niet genoemd en moet allen naar een 'trap' knoop gestuurd worden}
+\label{fig:2dfa}
 \end{figure}