Changeset 226 for liacs/TPFL2010/assignment1

Timestamp:

Nov 12, 2010, 8:39:27 PM (14 years ago)

Author:

Rick van der Zwet

Message:

3.22

File:

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

liacs/TPFL2010/assignment1/report.tex

@@ -11 +11 @@
 \usepackage{url}
 \usepackage{amssymb,amsmath}
-\usepackage{lipsum}
 \usepackage{float}
+\usepackage{tikz}
 
+\usetikzlibrary{arrows,decorations.pathmorphing,backgrounds,positioning,fit,petri}
+
+
+
+\setlength\parindent{0pt}
+\setlength\parskip{\baselineskip}
 \floatstyle{ruled}
 \newfloat{algoritm}{thp}{lop}
@@ -49 +55 @@
 $\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.
 \qed
@@ -58 +64 @@
 \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
-eigen equivalentie klasse is, is de taal $L = {0,1}^+$.
+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
+positieve 'gevallen' uitkomen. 
+
+Een mooi voorbeeld is de taal van \emph{PRIMES2}\cite{JS2009}[pg. 2], waarbij
+de priemgetallen in een binair stelsel worden vertegenwoordigd. Door op unieke
+'start' van de woorden zullen deze nooit in elkaar vervallen en zal dus elk
+woord zijn eigen klasse zijn.
+
 
 \section{Opgave 3.22}
+Om aan te tonen dat een \emph{2DFA} exponentioneel 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:
+\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\}
+\end{equation}
+
+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
+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
+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
+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.
+
+
+\begin{figure}
+\label{fig:idee}
+\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] {};
+\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)
+        ;
+\end{tikzpicture}
+\caption{Idee voor Opdracht 2.22a}
+\end{figure}
+
+Om te laten zien dat een \DFA minstens $n^n$ toestanden nodig heeft moet je
+gebruik maken van het feit dan een \DFA niet terug kan lopen. Het zal dus een
+`geheugen' moeten maken om het maximale $0$ woord voor de `splitsing' ($2^k$)
+te kunnen onthouden om zo te kijken of het overeen komt het $0$ woord na de
+`splitsing'. Omdat je voor elke $F_i$ waarbij $1 \ge i \ge n$ minimaal $n$
+toestanden nodig hebt om te kunnen tellen en hiervan weer $n$ unieke sets
+bestaan, heb je dus minimaal $n^n$ toestanden nodig.
+
+
+
+
 \section{Opgave 3.47}
 \section{Opgave 3.54}