Informatiker Board | Automatentheorie | Epsilon-FA in NFA umwandeln

Informatiker Board » Themengebiete » Theoretische Informatik » Automatentheorie » Epsilon-FA in NFA umwandeln

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Epsilon-FA in NFA umwandeln

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Seppel123
unregistriert

Epsilon-FA in NFA umwandeln

Zitatantwort auf diesen Beitrag erstellen

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

19.06.2010 13:04

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Automatentheorie » Epsilon-FA in NFA umwandeln