Changeset 229

Timestamp:

Nov 12, 2010, 11:25:33 PM (14 years ago)

Author:

Rick van der Zwet

Message:

Basic spell check done

File:

• liacs/TPFL2010/assignment1/report.tex (modified) (9 diffs)

liacs/TPFL2010/assignment1/report.tex

@@ -40 +40 @@
 \cite{JS2009} gebruikt bij het college. In deze opdracht zullen zeven opgaven
 (3,20,22,47,54,68,69) van hoofdstuk 3 behandeld worden. De opgaven zijn
-willikeurig gekozen met behulp van een kans generator, het kans dus zijn dat
+willekeurig gekozen met behulp van een kans generator, het kans dus zijn dat
 niet alle onderwerpen van hoofdstuk 3 behandeld worden.
 \end{abstract}
@@ -50 +50 @@
 \end{equation}
 regulier. Zie dat er een `verdubbeling' optreed van symbolen, dit gedrag is de
-modeleren in een \DFA. Omdat $L$ regulier is bestaat er een \DFA $M =
-(Q,\Sigma,\delta,q_0,F)$ die $L$ beschijft.  Construreer nu een nieuwe \DFA $P$
+modelleren in een \DFA. Omdat $L$ regulier is bestaat er een \DFA $M =
+(Q,\Sigma,\delta,q_0,F)$ die $L$ beschrijft.  Construeer nu een nieuwe \DFA $P$
 die de nieuwe taal $2L$ gaat beschrijven, neem hiervoor het alfabet ($\Sigma$),
-en de begintoestand $q_0$ over van $L$. De toestanden ($Q$) worden verdubbeled.
+en de begintoestand $q_0$ over van $L$. De toestanden ($Q$) worden verdubbeld.
 $voor~alle~q \in Q:~voeg~q'~toe~aan~Q$. Neem ook de transities over van $M$,
-maar maak aanpassingen zodaning dat de nieuwe toestanden ook gelezen worden. Dus
+maar maak aanpassingen zodanig dat de nieuwe toestanden ook gelezen worden. Dus
 $\delta(q,x)$ wordt $\delta(q,q'),\delta(q',x)$. De acceptatie toestand $F$
 moet ook aangepast worden, door de oude acceptatie $q$ te vervangen door $q'$.
 \\
-De nieuwe \DFA $P$ beschijft $2L$ en dus is $2L$ regulier.
+De nieuwe \DFA $P$ beschrijft $2L$ en dus is $2L$ regulier.
 \qed
 
@@ -66 +66 @@
 Laat $\Sigma = {0,1}$ zijn. Een voorbeeld van de taal $L \subseteq
 \Sigma^*$ voor welke geldt dat, de Myhill-Nerode\cite{JS2009}[pg. 77--81]
-gelijkheids relatie $R_L$ de eigenschap heeft dat elk woord in $\Sigma^*$ zijn
+gelijkheid relatie $R_L$ de eigenschap heeft dat elk woord in $\Sigma^*$ zijn
 eigen equivalentie klasse is. Dit wilt zeggen dat voor alle $z \in \Sigma^*$,
 is er een $xz \in L$ dan en slechts als $yz \in L$. Omdat hier gezocht wordt
-naar een taal waarbij de woorden allemaal equivalentie klassen opzich zijn, zal
-alle elementen met elkaar vergeleken kunnen worden dmv $R_L$ en hier mogen geen
+naar een taal waarbij de woorden allemaal equivalentie klassen op-zich zijn, zal
+alle elementen met elkaar vergeleken kunnen worden door middel van $R_L$ en hier mogen geen
 positieve 'gevallen' uitkomen. 
 
@@ -80 +80 @@
 
 \section{Opgave 3.22}
-Om aan te tonen dat een \emph{2DFA} exponentioneel meer expressief is dan een
+Om aan te tonen dat een \emph{2DFA} exponentieel meer expressief is dan een
 \DFA voor bepaalde talen kijken we naar de volgende taal; Laat $n$ een integer
-$\ge1$ en $F_n \subseteq \{0,1,2,3,4\}^*$ als volgende gedefineerd:
+$\ge1$ en $F_n \subseteq \{0,1,2,3,4\}^*$ als volgende gedefinieerd:
 \begin{equation}
   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
 aantal keer nul op twee plekken vergelijken. Waarbij 1 plek vast staat en de
-tweede plek variable wordt gedefineerd. Dit lijkt mij controleren op twee los
+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}
@@ -134 +134 @@
 aan de hand van het volgende voorbeeld:
 Laat $M = (Q,\Sigma, \delta, q_1,F)$ een \DFA zijn, waarbij $Q =
-\{q_1,q_2,\ldots,q_n\}$. Defineer nu $R_{i,j,k}$ als de taal van alle woorden
+\{q_1,q_2,\ldots,q_n\}$. Definieer nu $R_{i,j,k}$ als de taal van alle woorden
 die van toestand $i$ naar toestand $j$ gaan zonder door toestanden te gaan die
 hoger als $k$ genummerd zijn.
 
-Om dit te doen is een recursive formule nodig, welke $R_{i,j,k}$ als invoer
+Om dit te doen is een recursieve formule nodig, welke $R_{i,j,k}$ als invoer
 heeft. a) Kijk welke transities er mogelijk zijn in $\delta$ met toestand $i$ als
 begin positie. Plaats deze op de `stapel'. b) Werk de elementen op de stapel
@@ -148 +148 @@
 \section{Opgave 3.54}
 
-Laat $\Sigma = \{1,2,3,\ldots,n\}$ zijn en defineer:
+Laat $\Sigma = \{1,2,3,\ldots,n\}$ zijn en definieer:
 \begin{equation}
 L_n = \{w \in \Sigma^* : |w|_i = 1~voor~alle~i\}
@@ -174 +174 @@
 
 Om te laten zien dat palc($w$) = $wt^{-1}w^R$, waarbij $wt^{-1}$ het woord is $w$
-waar het suffix $t$ erafgehaald is en $t$ de langste palindroom suffix van $w$
+waar het suffix $t$ eraf gehaald is en $t$ de langste palindroom suffix van $w$
 is, moet er gebruik gemaakt worden van een tegenstelling. Als $w$ nog een
 palindroom aan het einde zal bevatten $uu$, dan ziet $x$ er als volgt uit
 $wuuuuw$, dit is niet de korte palindroom ($ww$), welke $uuuu$ er nog makkelijk
-uit weggehaald had kunnen worden. Een wilekeurige suffix van $w$ kan ook geen
+uit weggehaald had kunnen worden. Een willekeurige suffix van $w$ kan ook geen
 palindroom vormen die nog `weggesneden' kan worden, omdat hij anders al in den
 beginne een palindroom had moeten zijn.
 
-If $L$ is regulier, dan is palc($L$) ook regulier, welke er een unieke
+Als $L$ is regulier, dan is palc($L$) ook regulier, welke er een unieke
 `vertaling' van een woord $w$ naar zijn palc($w$). De nieuwe woorden zullen in
 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
 onbeslist of palc\textsuperscript{-1}($L$) ook regulier is. Het kan namelijk
-zeer goed dat een (ingewikkende) functie die woorden genereerd welke een
-palindroom zijn en die aan een vast prefix ($p$) toevoegd. De \emph{palc}
+zeer goed dat een (ingewikkelde) functie die woorden genereerde welke een
+palindroom zijn en die aan een vast prefix ($p$) toegevoegd. De \emph{palc}
 functie zal deze allen naar \'{e}\'{e}n woord omzetten, welke dan regulier is.