Informatiker Board | Druckvorschau: Epsilon-FA in NFA umwandeln

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
---- Automatentheorie (http://www.informatikerboard.de/board/board.php?boardid=13)
----- Epsilon-FA in NFA umwandeln (http://www.informatikerboard.de/board/thread.php?threadid=734)

Geschrieben von Seppel123 am 19.06.2010 um 13:04:

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]$ ein NFA, der epsilon Kanten besitzen kann.

Ein äquivalenter $[latex]NFA B := (Q, \Sigma, \delta ', S_0, F')[/latex]$ 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]$

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