Changeset 245 for liacs/TPFL2010/assignment1/report.tex
- Timestamp:
- Dec 8, 2010, 6:50:15 PM (14 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
liacs/TPFL2010/assignment1/report.tex
r244 r245 75 75 $xz \in L, yz \notin L$. 76 76 77 De taal $M = {0}^* : |M|_0~is~een~priemgetal$ is een ander voorbeeld. Als we77 De taal $M = \{{0}^* : |M|_0~is~een~priemgetal\}$ is een ander voorbeeld. Als we 78 78 kijken naar $aR_{l}b$ kan er altijd een $z$ gevormd worden zodanig dat $az \in 79 79 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 94 94 worden, welke aan te tonen is door eerst te kijken naar de eigenschappen van 95 $F_n$ hierbij is de zien dat de $0$-reeks van de lengte $i ^k$ zowel voor als na95 $F_n$ hierbij is de zien dat de $0$-reeks van de lengte $i_k$ zowel voor als na 96 96 de $2^k$ moet voorkomen. Waarbij $2^k$ aangeeft, waar deze $0$-reeks gevonden 97 kan worden e.g. bij welke $i_x$. De \emph{2DFA} moet dus twee dingen doen. Het97 kan worden bij de plek $k$. De \emph{2DFA} moet dus twee dingen doen. Het 98 98 aantal keer nul op twee plekken vergelijken. Waarbij 1 plek vast staat en de 99 tweede plek variabele wordt gedefinieerd. Dit lijkt mij controleren op twee los 100 staande feiten. Hiervoor heb ik \underline{geen} antwoord gevonden. Ik kan 101 enkel wat voor $O(n^2)$ bedenken, welke een idee is in Figuur~\ref{fig:idee} 102 uitgewerkt is. 99 tweede plek variabele wordt gedefinieerd. De aanpak kan als volgt gezien worden: 100 \begin{verbatim} 101 1. controleren of |1| <= 2de 0-reeks (dmv 'knopen-strook'). 102 2. |2| tellen (onthouden dmv 'knopen-strook', dit is `variable' A). 103 3. naar begin lopen. 104 4. A-1 '1' instanties laten passeren. 105 5. |0| tellen (onthouden dmv 'knopen-strook'm dit is `variable' A). 106 6. naar begin 2de 0-reeks lopen. 107 7. 0-reeks vergelijken. 108 \end{verbatim} 109 Voor deze aanpak zijn 3 `knopen-stroken' nodig en 3 transitie-lagen. In totaal 110 dus in ongeveer $O(6n)$ knopen. Figuur~\ref{fig:2dfa} laat de \emph{2DFA} 111 zien. 103 112 104 113 … … 106 115 \center 107 116 \begin{tikzpicture} 108 \node[place,pin={[pin edge={style=<-,blue,thick,decorate,decoration={snake, pre length=4pt}}]left:}] (q0) {}; 109 \node[place] (q1) [below=of q0] {}; 110 \node[place] (q2) [below=of q1] {}; 111 \node[place,pin={[pin edge={style=-<,thick,decorate,decoration={snake, pre length=4pt}}]below:}] (q3) [below=of q2] {}; 112 \node[place] (q01) [right=3cm of q1] {}; 113 \node[place] (q02) [right=3cm of q2] {}; 117 \node[place,pin={[pin edge={style=<-,blue,thick,decorate,decoration={snake, pre length=4pt}}]left:}] (q00) {}; 118 \node[place] (q01) [right=of q00] {}; 119 \node[place] (q02) [right=of q01] {}; 120 \node[place] (q03) [right=of q02] {}; 121 \node[place] (q11) [below=of q01] {}; 122 \node[place] (q12) [below=of q02] {}; 123 \node[place] (q13) [below=of q03] {}; 124 \node[place] (q10) [below=of q00] {}; 125 \node[place] (q20) [below=of q10] {}; 126 \node[place] (q21) [below=of q11] {}; 127 \node[place] (q22) [below=of q12] {}; 128 %\node[place] (q2) [below=of q1] {}; 129 %\node[place,pin={[pin edge={style=-<,thick,decorate,decoration={snake, pre length=4pt}}]below:}] (q3) [below=of q2] {}; 130 %\node[place] (q01) [right=3cm of q1] {}; 131 %\node[place] (q02) [right=3cm of q2] {}; 114 132 \path[->] 115 (q0) edge [decorate,decoration={snake}] node[left] {goto-2} (q1) 116 (q1) edge node[left] {2} (q2) 117 (q2) edge node[left] {2} (q3) 118 (q1) edge [decorate,decoration={snake}] node[above] {0-length-check} (q01) 119 (q2) edge [decorate,decoration={snake}] node[above] {0-length-check} (q02) 133 % (q0) edge [decorate,decoration={snake}] node[left] {goto-2} (q00) 134 (q00) edge node[above] {3,R} (q01) 135 (q01) edge node[above] {1,R} (q02) 136 (q01) edge [loop above] node[above] {0,R} (q01) 137 (q02) edge node[above] {1,R} (q03) 138 (q02) edge [loop above] node[above] {0,R} (q02) 139 (q03) edge [loop above] node[above] {0,R} (q03) 140 141 (q11) edge node[above] {0,L} (q10) 142 (q12) edge [bend left] node[below] {0,L} (q10) 143 (q13) edge [bend left] node[below] {0,L} (q10) 144 145 (q01) edge node {2,R} (q11) 146 (q02) edge node {2,R} (q12) 147 (q03) edge node {2,R} (q13) 148 (q13) edge node[above] {2,R} (q12) 149 (q12) edge node[above] {2,R} (q11) 150 151 (q10) edge node {2,L} (q20) 152 (q20) edge node[below] {2,L} (q21) 153 (q21) edge node[below] {2,L} (q22) 154 155 156 % (q1) edge node[left] {2} (q2) 157 % (q2) edge node[left] {2} (q3) 158 % (q1) edge [decorate,decoration={snake}] node[above] {0-length-check} (q01) 159 % (q2) edge [decorate,decoration={snake}] node[above] {0-length-check} (q02) 120 160 ; 121 161 \end{tikzpicture} 122 \caption{ Idee voor Opdracht 2.22a}123 \label{fig: idee}162 \caption{Opdracht 2.22a uitgewerkt voor $n = 3$, niet geldige stappen zijn niet genoemd en moet allen naar een 'trap' knoop gestuurd worden} 163 \label{fig:2dfa} 124 164 \end{figure} 125 165
Note:
See TracChangeset
for help on using the changeset viewer.