Fragen zu rev(L(A))

patrix
Mausschubser
Mausschubser
Beiträge: 71
Registriert: 16. Nov 2009 17:10

Fragen zu rev(L(A))

Beitrag von patrix »

Hallo zusammen,
ich sitze gerade an der Hausübung und habe ein paar Fragen zu den Eigenschaften von rev(L(A))

Kann man rev(L(A)) nur auf einen NFA anwenden?
(wenn nein was ist dann mit einem DFA der mehr als einen akzeptierten Zustand hat? Welcher ist dann der Startzustand?)

Ist rev(L(A)) immer ein NFA?

Geben sei L(A): aaa*+bb(ab)*+abba* ist dann rev(L(A)) = a*aa+(ba)*bb+a*bba?

Vielen Dank im Voraus Patrick

LucasR
Kernelcompilierer
Kernelcompilierer
Beiträge: 474
Registriert: 9. Jun 2009 09:55

Re: Fragen zu rev(L(A))

Beitrag von LucasR »

DFA und NFA sind gleichmächtig, das bedeutet, dass alle Sprachen, die man mit einem DFA ausdrücken kann, auch mit einem NFA ausdrücken kann, und andersrum. Die Sprache der umgedrehten Worte (wenn ich rev() noch richtig in Erinnerung hab) kann also immer als NFA und als DFA angegeben werden. Es gibt Methoden, um aus jedem NFA einen DFA zu machen, aber ich glaube die kommen erst in einer der kommenden Vorlesungen.

Für deinen konkreten Fall, dein rev(l(A)) stimmt glaube ich.

Antworten

Zurück zu „Archiv“