Changeset 244 for liacs/TPFL2010/assignment1

Timestamp:

Dec 8, 2010, 4:30:06 PM (14 years ago)

Author:

Rick van der Zwet

Message:

Opgave 3.20 verbeterd

Location:

liacs/TPFL2010/assignment1

Files:

• report.pdf (modified) ( previous)
• report.tex (modified) (1 diff)

liacs/TPFL2010/assignment1/report.tex

@@ -65 +65 @@
 \Sigma^*$ voor welke geldt dat, de Myhill-Nerode\cite{JS2009}[pg. 77--81]
 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 op-zich zijn, zal
-alle elementen met elkaar vergeleken kunnen worden door middel van $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}
+eigen equivalentie klasse is. Dit wilt zeggen dat $xR_{l}y$ dan en slechts dan
+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 op-zich zijn, zal alle elementen met elkaar vergeleken kunnen worden
+door middel van $R_L$ en hier mogen geen positieve 'gevallen' uitkomen. 
+
+De (triviale) taal $L = {01,10}$ is een voorbeeld hiervan. Beiden woorden hebben
+hun eigen klasse. Als $x = 0$ en $y = 1$, bestaat er een $z = 1$, zodanig dat
+$xz \in L, yz \notin L$.
+
+De taal $M = {0}^* : |M|_0~is~een~priemgetal$  is een ander voorbeeld. Als we
+kijken naar $aR_{l}b$ kan er altijd een $z$ gevormd worden zodanig dat $az \in
+M, bz \notin M$. Bijvoorbeeld $a = 0^3, b =0^5, z = 0^4$. Deze eigenschap wordt
+afgedwongen door het `feit' dat er geen relatie bestaat tussen de lengtes
+tussen opeenvolgende priemgetallen.\footnote{Ik heb dit voor gemak aangenomen,
+de praktijk is echter dat is nog een groot wiskundig vraagstuk is.}
+
+
+\section{Opgave 3.22*}
 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 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\}
+  F_n = \{3~0^{i_1}~1~0^{i_2} \cdots 1~0^{i_n}~2^k~0^{i_k}~4 : 1 \le k,j,i_j \le n\}
 \end{equation}