Changeset 248 for liacs/TPFL2010/assignment1/report.tex
- Timestamp:
- Dec 8, 2010, 9:13:12 PM (14 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
liacs/TPFL2010/assignment1/report.tex
r247 r248 232 232 \section{Opgave 3.47} 233 233 234 Om te bewijzen dat `de klasse van talen geaccepteerd door \DFA' =>`de klasse van235 talen gespecificeerd door de reguliere expressies'\cite{JS2009}[Theorem 1.4.2, (b) =>(a)]234 Om te bewijzen dat `de klasse van talen geaccepteerd door \DFA' $\Rightarrow$ `de klasse van 235 talen gespecificeerd door de reguliere expressies'\cite{JS2009}[Theorem 1.4.2, (b) $\Rightarrow$ (a)] 236 236 aan de hand van het volgende voorbeeld: 237 237 Laat $M = (Q,\Sigma, \delta, q_1,F)$ een \DFA zijn, waarbij $Q = 238 238 \{q_1,q_2,\ldots,q_n\}$. Definieer nu $R_{i,j,k}$ als de taal van alle woorden 239 239 die van toestand $i$ naar toestand $j$ gaan zonder door toestanden te gaan die 240 hoger als$k$ genummerd zijn.241 242 Om dit te doen is een recursieve formule nodig, welke $R_{i,j,k}$ als invoer 243 heeft. a) Kijk welke transities er mogelijk zijn in $\delta$ met toestand $i$ als 244 begin positie. Plaats deze op de `stapel'. b) Werk de elementen op de stapel 245 stuk voor stuk af volgens dezelfde methodiek. Stop pas als de $\delta$ 246 resultaat $j$ bevat. Let erop dat oneindige herhalingen gedetecteerd moeten247 worden om het algoritme te laten termineren. Je kan het zien als het volledig 248 do orzoeken van een boom met in de wortel de knoop $i$.240 hoger dan $k$ genummerd zijn. 241 242 243 $R_{i,j,k}$ accepteert als $q_i \in q_1, q_j \in F$. 244 Om $R_{i,j,k+1}$ te verkrijgen, nemen we eerst de toestanden van $R_{i,j,k}$, 245 deze verenigen we dan met alle toestanden die we vanuit $R_{i,j,k}$ kunnen 246 bereiken met een transities $\delta(a,k+1) : i \le a \le j$, die in een 247 \underline{nieuwe} toestand uitkomen, de lussen hebben geen meerwaarde voor ons 248 doel. De begin toestand is te markeren als $R_{i,j,0} = {q_1} : i = j = 1$. 249 249 250 250 \section{Opgave 3.54}
Note:
See TracChangeset
for help on using the changeset viewer.