Seppel123
unregistriert
 |
|
| Epsilon-FA in NFA umwandeln |
     |
Meine Frage:
Hallo,
wir sollen als Hausaufgabe einen [latex\epsilon-FA[/latex] umwandeln in einen NFA ohne epsilon übergänge.
So, alles was das Script hergibt ist sowas:
Sei ![[latex] A := (Q,\Sigma,\delta,S_0,F)[/latex]](http://www.matheboard.de/latex2png/latex2png.php? A := (Q,\Sigma,\delta,S_0,F)) ein NFA, der epsilon Kanten besitzen kann.
Ein äquivalenter ![[latex]NFA B := (Q, \Sigma, \delta ', S_0, F')[/latex]](http://www.matheboard.de/latex2png/latex2png.php?NFA B := (Q, \Sigma, \delta ', S_0, F')) ohne epsilon Kanten wird wie folgt erklärt:
![[latex]\delta ' := \left\{(z, x, z'') \in Q x \Sigma x Q | \exists ~(z',x,z'') \in \delta : (z,\epsilon) |\!\!-^*(z',\epsilon) \right\}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\delta ' := \left\{(z, x, z'') \in Q x \Sigma x Q | \exists ~(z',x,z'') \in \delta : (z,\epsilon) |\!\!-^*(z',\epsilon) \right\})
Meine Ideen:
So, prinzipiell versteh ich das.. aber ich weiß noch nicht genau wie der Konfigurationsübergang (z, e) |-* (z',e) gemeint ist. Sind das alle Pfade die ich gehen kann im automaten die nur epsilon übergänge enthalten ??
Danke
|
|
19.06.2010 13:04 |
|
|
