Changeset 249 for liacs/TPFL2010/assignment1

Timestamp:

Dec 8, 2010, 9:53:18 PM (14 years ago)

Author:

Rick van der Zwet

Message:

Temp commit

Location:

liacs/TPFL2010/assignment1

Files:

• report.pdf (modified) ( previous)
• report.tex (modified) (2 diffs)

liacs/TPFL2010/assignment1/report.tex

@@ -223 +223 @@
 Voor elke $F_i : 1 \ge i \ge n$ geldt dat deze `intern' ook $i^2$ unique
 toestanden geeft. We splitsen de woorden bij $2$, zodat we over een `prefix' en
-`suffix' kunnen praten. Een `prefix' past maar bij "{e}"{e}n `suffix'. De
+`suffix' kunnen praten. Een `prefix' past maar bij '{e}'{e}n `suffix'. De
 `suffixes' die gegenereeerd worden van de vorm $2*0*4$, kan $i^2$ vormen
 aannemen (bijvoorbeeld $i=2 {204,2004,22004,2204}$).
@@ -252 +252 @@
 Laat $\Sigma = \{1,2,3,\ldots,n\}$ zijn en definieer:
 \begin{equation}
-L_n = \{w \in \Sigma^* : |w|_i = 1~voor~alle~i\}
+L_n = \{w \in \Sigma^* : |w|_i = 1~voor~alle~i\in \Sigma\}
 \end{equation}
-Dit zijn dus de woorden waarbij alle elementen precies \'{e}\'{e}n keer in voor
+Dit zijn dus de woorden waarbij alle elementen van $\Sigma$ precies \'{e}\'{e}n keer 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$. 
+a) Om te laten zijn dat er minimaal een reguliere expressie van lengte $2^{n-1}$
+nodig is om $L_n$ te specificeren, passen we de \emph{Myhill-Nerode} stelling
+toe. Neem $x,y \in \Sigma^*$. Als geldt $|x| = |y|$ en de elementen zijn
+gelijk, maar enkel hun volgorde verschilt (bijvoorbeeld $123,132$) dan zitten
+ze in dezelfde klasse. Voor $xR_{l}y$ als de lengte verschilt, dan is er een
+$z$ te vinden zodanig dat $y$ wel geaccepteerd wordt en $x$ niet (bijvoorbeeld
+voor $34,345$, is dit $12$), vanwege $|x| + a \neq = |y| + a = n$ desals $|x|
+\neq |y|$. Als de `inhoud' verschilt maar de lengte gelijk is dan $z = \Sigma -
+\{y\}$, omdat $\Sigma \backslash \{x\} \neq \Sigma \backslash \{y\}$.
+
+
+b) Echter voor $\overline{L_n}$  is wel een reguliere expressie te vinden en wel
+in de grootte $O(n^2)$. $\bigcup_{a : 0 .. n}{\bigcup_{i \in \Sigma_a}\{x^*ix^*ix^*\}}$  waarbij $x \in
+(\Sigma_a \backslash \{i\})^*$. 
 
 \section{Opgave 3.68}