Changeset 227 for liacs/TPFL2010/assignment1

Timestamp:

Nov 12, 2010, 10:55:52 PM (14 years ago)

Author:

Rick van der Zwet

Message:

Almost done

File:

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

liacs/TPFL2010/assignment1/report.tex

@@ -13 +13 @@
 \usepackage{float}
 \usepackage{tikz}
+\usepackage{fixltx2e}
 
 \usetikzlibrary{arrows,decorations.pathmorphing,backgrounds,positioning,fit,petri}
@@ -38 +39 @@
 Dit schrijven zal uitwerkingen van opgaven behandelen uit het boek
 \cite{JS2009} gebruikt bij het college. In deze opdracht zullen zeven opgaven
-(3,20,22,47,54,68,69) van hoofdstuk 3 behandeld worden.
+(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
+niet alle onderwerpen van hoofdstuk 3 behandeld worden.
 \end{abstract}
 
@@ -97 +100 @@
 
 \begin{figure}
-\label{fig:idee}
 \center
 \begin{tikzpicture}
@@ -115 +117 @@
 \end{tikzpicture}
 \caption{Idee voor Opdracht 2.22a}
+\label{fig:idee}
 \end{figure}
 
@@ -125 +128 @@
 bestaan, heb je dus minimaal $n^n$ toestanden nodig.
 
-
-
-
 \section{Opgave 3.47}
+
+Om te bewijzen dat `de klasse van talen geaccepteerd door \DFA' => `de klasse van
+talen gespecificeerd door de reguliere expressies'\cite{JS2009}[Theorem 1.4.2, (b) => (a)]
+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
+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
+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
+stuk voor stuk af volgens dezelfde methodiek. Stop pas als de $\delta$
+resultaat $j$ bevat. Let erop dat oneindige herhalingen gedetecteerd moeten
+worden om het algoritme te laten termineren. Je kan het zien als het volledig
+doorzoeken van een boom met in de wortel de knoop $i$.
+
 \section{Opgave 3.54}
+
+Laat $\Sigma = \{1,2,3,\ldots,n\}$ zijn en defineer:
+\begin{equation}
+L_n = \{w \in \Sigma^* : |w|_i = 1~voor~alle~i\}
+\end{equation}
+Dit zijn dus de woorden waarbij alle elementen precies \'{e}\'{e}n keer in voor
+komen. Bijvoorbeeld $L_3 = \{123,132,213,231,312,321\}$.
+
+Om te laten zijn dat er minimal een reguliere expressie van lengte $2^{n-1}$
+nodig is om $L_n$ te specificeren, moet de \emph{Myhill-Nerode} stelling
+toegepast worden. Vanwege de eigenschap dat prefix uniek is, zat het nooit
+mogelijk worden om aan beiden woorden hetzelfde toe te voegen zodanig dat ze in
+elkaars klasse terecht komen. (elk `bit' informatie is relevant). Voor alle
+klasse zal dus apart gekeken worden of aan de eisen voldaan wordt. Om dus alle
+getallen $n$ van de string te controleren of zij uniek is zijn minimaal
+$2^{n-1}$ toestanden nodig.
+
+Echter voor $\overline{L_n}$  is wel een reguliere expressie te vinden en wel
+in de grootte $O(n^2)$. Door simpelweg voor elke $i \in \Sigma^*$ een reguliere
+expressie te maken van de vorm $x^*~i~x^*~i~x^*$ waarbij $x = Sigma^* - i$. 
+
 \section{Opgave 3.68}
+
+Voor een woord $w \in \Sigma^*$, is een palc($w$) de korte palindroom $x$
+zodanig dat $w$ een prefix is van $x$. en palc($L$) = $\bigcup_{w \in L}\{palc(w)\}$.
+
+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$
+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
+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
+`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.
+
+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}
+functie zal deze allen naar \'{e}\'{e}n woord omzetten, welke dan regulier is.
+
+
 \section{Opgave 3.69}
+
+Laat $x_1,x_2,\ldots,x_k \in \Sigma^*$. Om te laten zien dat $\Sigma^* -
+x_{1}^{*}x_{2}^{*} \cdots x_{k}^*$ eindig is dan en slechts als $|\Sigma| = 1$
+en gcd($|x_1|,|x_2|,\ldots,|x_k|$) = 1 moet er een paar dingen bewezen worden
+a) aantonen dat het \underline{niet} geldt voor de tegenvoorbeelden a) $gcd
+> 1$ b) $|\Sigma| > 1$ en tevens moet aangetoond worden waarom de eindigheid
+ voor dit specifieke voorbeeld geldt.
 
 \begin{thebibliography}{1}