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

Timestamp:

Dec 8, 2010, 9:13:12 PM (14 years ago)

Author:

Rick van der Zwet

Message:

4.47

File:

• liacs/TPFL2010/assignment1/report.tex (modified) (1 diff)

liacs/TPFL2010/assignment1/report.tex

@@ -232 +232 @@
 \section{Opgave 3.47}
 
-Om te bewijzen dat `de klasse van talen geaccepteerd door \DFA' => `de klasse van
-talen gespecificeerd door de reguliere expressies'\cite{JS2009}[Theorem 1.4.2, (b) => (a)]
+Om te bewijzen dat `de klasse van talen geaccepteerd door \DFA' $\Rightarrow$ `de klasse van
+talen gespecificeerd door de reguliere expressies'\cite{JS2009}[Theorem 1.4.2, (b) $\Rightarrow$ (a)]
 aan de hand van het volgende voorbeeld:
 Laat $M = (Q,\Sigma, \delta, q_1,F)$ een \DFA zijn, waarbij $Q =
 \{q_1,q_2,\ldots,q_n\}$. Definieer nu $R_{i,j,k}$ als de taal van alle woorden
 die van toestand $i$ naar toestand $j$ gaan zonder door toestanden te gaan die
-hoger als $k$ genummerd zijn.
-
-Om dit te doen is een recursieve formule nodig, welke $R_{i,j,k}$ als invoer
-heeft. a) Kijk welke transities er mogelijk zijn in $\delta$ met toestand $i$ als
-begin positie. Plaats deze op de `stapel'. b) Werk de elementen op de stapel
-stuk voor stuk af volgens dezelfde methodiek. Stop pas als de $\delta$
-resultaat $j$ bevat. Let erop dat oneindige herhalingen gedetecteerd moeten
-worden om het algoritme te laten termineren. Je kan het zien als het volledig
-doorzoeken van een boom met in de wortel de knoop $i$.
+hoger dan $k$ genummerd zijn.
+
+
+$R_{i,j,k}$ accepteert als $q_i \in q_1, q_j \in F$. 
+Om $R_{i,j,k+1}$ te verkrijgen, nemen we eerst de toestanden van $R_{i,j,k}$,
+deze verenigen we dan met alle toestanden die we vanuit $R_{i,j,k}$ kunnen
+bereiken met een transities $\delta(a,k+1) : i \le a \le j$, die in een
+\underline{nieuwe} toestand uitkomen, de lussen hebben geen meerwaarde voor ons
+doel. De begin toestand is te markeren als $R_{i,j,0} = {q_1} : i = j = 1$.
 
 \section{Opgave 3.54}