- Timestamp:
- Nov 12, 2010, 11:25:33 PM (14 years ago)
- File:
-
- 1 edited
-
liacs/TPFL2010/assignment1/report.tex (modified) (9 diffs)
Legend:
- Unmodified
- Added
- Removed
-
liacs/TPFL2010/assignment1/report.tex
r228 r229 40 40 \cite{JS2009} gebruikt bij het college. In deze opdracht zullen zeven opgaven 41 41 (3,20,22,47,54,68,69) van hoofdstuk 3 behandeld worden. De opgaven zijn 42 will ikeurig gekozen met behulp van een kans generator, het kans dus zijn dat42 willekeurig gekozen met behulp van een kans generator, het kans dus zijn dat 43 43 niet alle onderwerpen van hoofdstuk 3 behandeld worden. 44 44 \end{abstract} … … 50 50 \end{equation} 51 51 regulier. Zie dat er een `verdubbeling' optreed van symbolen, dit gedrag is de 52 model eren in een \DFA. Omdat $L$ regulier is bestaat er een \DFA $M =53 (Q,\Sigma,\delta,q_0,F)$ die $L$ besch ijft. Construreer nu een nieuwe \DFA $P$52 modelleren in een \DFA. Omdat $L$ regulier is bestaat er een \DFA $M = 53 (Q,\Sigma,\delta,q_0,F)$ die $L$ beschrijft. Construeer nu een nieuwe \DFA $P$ 54 54 die de nieuwe taal $2L$ gaat beschrijven, neem hiervoor het alfabet ($\Sigma$), 55 en de begintoestand $q_0$ over van $L$. De toestanden ($Q$) worden verdubbel ed.55 en de begintoestand $q_0$ over van $L$. De toestanden ($Q$) worden verdubbeld. 56 56 $voor~alle~q \in Q:~voeg~q'~toe~aan~Q$. Neem ook de transities over van $M$, 57 maar maak aanpassingen zodani ng dat de nieuwe toestanden ook gelezen worden. Dus57 maar maak aanpassingen zodanig dat de nieuwe toestanden ook gelezen worden. Dus 58 58 $\delta(q,x)$ wordt $\delta(q,q'),\delta(q',x)$. De acceptatie toestand $F$ 59 59 moet ook aangepast worden, door de oude acceptatie $q$ te vervangen door $q'$. 60 60 \\ 61 De nieuwe \DFA $P$ besch ijft $2L$ en dus is $2L$ regulier.61 De nieuwe \DFA $P$ beschrijft $2L$ en dus is $2L$ regulier. 62 62 \qed 63 63 … … 66 66 Laat $\Sigma = {0,1}$ zijn. Een voorbeeld van de taal $L \subseteq 67 67 \Sigma^*$ voor welke geldt dat, de Myhill-Nerode\cite{JS2009}[pg. 77--81] 68 gelijkheid srelatie $R_L$ de eigenschap heeft dat elk woord in $\Sigma^*$ zijn68 gelijkheid relatie $R_L$ de eigenschap heeft dat elk woord in $\Sigma^*$ zijn 69 69 eigen equivalentie klasse is. Dit wilt zeggen dat voor alle $z \in \Sigma^*$, 70 70 is er een $xz \in L$ dan en slechts als $yz \in L$. Omdat hier gezocht wordt 71 naar een taal waarbij de woorden allemaal equivalentie klassen op zich zijn, zal72 alle elementen met elkaar vergeleken kunnen worden d mv$R_L$ en hier mogen geen71 naar een taal waarbij de woorden allemaal equivalentie klassen op-zich zijn, zal 72 alle elementen met elkaar vergeleken kunnen worden door middel van $R_L$ en hier mogen geen 73 73 positieve 'gevallen' uitkomen. 74 74 … … 80 80 81 81 \section{Opgave 3.22} 82 Om aan te tonen dat een \emph{2DFA} exponenti oneel meer expressief is dan een82 Om aan te tonen dat een \emph{2DFA} exponentieel meer expressief is dan een 83 83 \DFA voor bepaalde talen kijken we naar de volgende taal; Laat $n$ een integer 84 $\ge1$ en $F_n \subseteq \{0,1,2,3,4\}^*$ als volgende gedefin eerd:84 $\ge1$ en $F_n \subseteq \{0,1,2,3,4\}^*$ als volgende gedefinieerd: 85 85 \begin{equation} 86 86 F_n = \{3~0^{i_1}~1~0^{i_2} \cdots 1~0^{i_n}~2^k~0^{i_k}~4 : 1 \ge k,j,i_j \ge n\} … … 93 93 kan worden e.g. bij welke $i_x$. De \emph{2DFA} moet dus twee dingen doen. Het 94 94 aantal keer nul op twee plekken vergelijken. Waarbij 1 plek vast staat en de 95 tweede plek variab le wordt gedefineerd. Dit lijkt mij controleren op twee los95 tweede plek variabele wordt gedefinieerd. Dit lijkt mij controleren op twee los 96 96 staande feiten. Hiervoor heb ik \underline{geen} antwoord gevonden. Ik kan 97 97 enkel wat voor $O(n^2)$ bedenken, welke een idee is in Figuur~\ref{fig:idee} … … 134 134 aan de hand van het volgende voorbeeld: 135 135 Laat $M = (Q,\Sigma, \delta, q_1,F)$ een \DFA zijn, waarbij $Q = 136 \{q_1,q_2,\ldots,q_n\}$. Defin eer nu $R_{i,j,k}$ als de taal van alle woorden136 \{q_1,q_2,\ldots,q_n\}$. Definieer nu $R_{i,j,k}$ als de taal van alle woorden 137 137 die van toestand $i$ naar toestand $j$ gaan zonder door toestanden te gaan die 138 138 hoger als $k$ genummerd zijn. 139 139 140 Om dit te doen is een recursi ve formule nodig, welke $R_{i,j,k}$ als invoer140 Om dit te doen is een recursieve formule nodig, welke $R_{i,j,k}$ als invoer 141 141 heeft. a) Kijk welke transities er mogelijk zijn in $\delta$ met toestand $i$ als 142 142 begin positie. Plaats deze op de `stapel'. b) Werk de elementen op de stapel … … 148 148 \section{Opgave 3.54} 149 149 150 Laat $\Sigma = \{1,2,3,\ldots,n\}$ zijn en defin eer:150 Laat $\Sigma = \{1,2,3,\ldots,n\}$ zijn en definieer: 151 151 \begin{equation} 152 152 L_n = \{w \in \Sigma^* : |w|_i = 1~voor~alle~i\} … … 174 174 175 175 Om te laten zien dat palc($w$) = $wt^{-1}w^R$, waarbij $wt^{-1}$ het woord is $w$ 176 waar het suffix $t$ eraf gehaald is en $t$ de langste palindroom suffix van $w$176 waar het suffix $t$ eraf gehaald is en $t$ de langste palindroom suffix van $w$ 177 177 is, moet er gebruik gemaakt worden van een tegenstelling. Als $w$ nog een 178 178 palindroom aan het einde zal bevatten $uu$, dan ziet $x$ er als volgt uit 179 179 $wuuuuw$, dit is niet de korte palindroom ($ww$), welke $uuuu$ er nog makkelijk 180 uit weggehaald had kunnen worden. Een wil ekeurige suffix van $w$ kan ook geen180 uit weggehaald had kunnen worden. Een willekeurige suffix van $w$ kan ook geen 181 181 palindroom vormen die nog `weggesneden' kan worden, omdat hij anders al in den 182 182 beginne een palindroom had moeten zijn. 183 183 184 If$L$ is regulier, dan is palc($L$) ook regulier, welke er een unieke184 Als $L$ is regulier, dan is palc($L$) ook regulier, welke er een unieke 185 185 `vertaling' van een woord $w$ naar zijn palc($w$). De nieuwe woorden zullen in 186 186 het slechtste geval evenveel blijven, maar de taal kan ook kleiner worden. … … 188 188 De andere kant op geldt dit \underline{niet}, als $L$ regulier is, dan is het 189 189 onbeslist of palc\textsuperscript{-1}($L$) ook regulier is. Het kan namelijk 190 zeer goed dat een (ingewikke nde) functie die woorden genereerdwelke een191 palindroom zijn en die aan een vast prefix ($p$) toe voegd. De \emph{palc}190 zeer goed dat een (ingewikkelde) functie die woorden genereerde welke een 191 palindroom zijn en die aan een vast prefix ($p$) toegevoegd. De \emph{palc} 192 192 functie zal deze allen naar \'{e}\'{e}n woord omzetten, welke dan regulier is. 193 193
Note:
See TracChangeset
for help on using the changeset viewer.
