Ignore:
Timestamp:
Dec 8, 2010, 8:46:35 PM (14 years ago)
Author:
Rick van der Zwet
Message:

3.22* afgemaakt (lang niet perfect)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • liacs/TPFL2010/assignment1/report.tex

    r246 r247  
    204204        ;
    205205\end{tikzpicture}
    206 \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.}
     206\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.}
    207207\label{fig:2dfa}
    208208\end{figure}
     
    215215toestanden nodig hebt om te kunnen tellen en hiervan weer $n$ unieke sets
    216216bestaan, heb je dus minimaal $n^n$ toestanden nodig.
     217
     218Dit vertaald zich in een Myhill-Nerode relatie om het aantal toestanden te
     219kunnen bepalen. $F_p$ en $F_q$ waarbij $p < q, 1 \le p,q \le n$ is
     220onderscheidbaar, door voor $z=2*0*4$ te nemen, zodanig dat het woord door $F_q$
     221geaccepteerd wordt, maar niet door $F_p$, door $|z|_2 \ge p$ te kiezen.
     222
     223Voor elke $F_i : 1 \ge i \ge n$ geldt dat deze `intern' ook $i^2$ unique
     224toestanden geeft. We splitsen de woorden bij $2$, zodat we over een `prefix' en
     225`suffix' kunnen praten. Een `prefix' past maar bij "{e}"{e}n `suffix'. De
     226`suffixes' die gegenereeerd worden van de vorm $2*0*4$, kan $i^2$ vormen
     227aannemen (bijvoorbeeld $i=2 {204,2004,22004,2204}$).
     228Deze unique suffixes zorgen ervoor dat de Myhill-Nerode toepassing een
     229substring $z$ kan vinden welke een van de unique suffixes bevat, waardoor het
     230`prefix' niet samenkomt met een `suffix'.
    217231
    218232\section{Opgave 3.47}
Note: See TracChangeset for help on using the changeset viewer.