Changeset 247 for liacs/TPFL2010/assignment1/report.tex

Timestamp:

Dec 8, 2010, 8:46:35 PM (14 years ago)

Author:

Rick van der Zwet

Message:

3.22* afgemaakt (lang niet perfect)

File:

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

liacs/TPFL2010/assignment1/report.tex

@@ -204 +204 @@
         ;
 \end{tikzpicture}
-\caption{Opdracht 2.22a uitgewerkt voor $1 \le n \le 3$, niet geldige stappen zijn niet genoemd en moet allen naar een 'trap' knoop gestuurd worden. Uitbreiden dmv expanderen van `traviale' knopen.}
+\caption{Opdracht 2.22a uitgewerkt voor $1 \le n \le 3$. Niet geldige stappen zijn niet genoemd en moet voor compleetheidnaar een 'putje' knoop gestuurd worden. Uitbreiden kan door het expanderen van `traviale' knopen.}
 \label{fig:2dfa}
 \end{figure}
@@ -215 +215 @@
 toestanden nodig hebt om te kunnen tellen en hiervan weer $n$ unieke sets
 bestaan, heb je dus minimaal $n^n$ toestanden nodig.
+
+Dit vertaald zich in een Myhill-Nerode relatie om het aantal toestanden te
+kunnen bepalen. $F_p$ en $F_q$ waarbij $p < q, 1 \le p,q \le n$ is
+onderscheidbaar, door voor $z=2*0*4$ te nemen, zodanig dat het woord door $F_q$
+geaccepteerd wordt, maar niet door $F_p$, door $|z|_2 \ge p$ te kiezen.
+
+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
+`suffixes' die gegenereeerd worden van de vorm $2*0*4$, kan $i^2$ vormen
+aannemen (bijvoorbeeld $i=2 {204,2004,22004,2204}$).
+Deze unique suffixes zorgen ervoor dat de Myhill-Nerode toepassing een
+substring $z$ kan vinden welke een van de unique suffixes bevat, waardoor het
+`prefix' niet samenkomt met een `suffix'.
 
 \section{Opgave 3.47}