epsilon-NDEA / NDEA

LegionWest · Anmeldungsdatum: 04.12.2005 Beiträge: 7

Hallo!
Ich stecke gerade in den Vorbereitungen zu einer Klausur und habe mir alte Klausuren unserer Uni angeschaut, die allerdings von einem anderen Prof. stammen, als dem Jetzigen.

Nun lautet eine Aufgabe, einen

-NDEA in einen NDEA umzuwandeln. Worin besteht der Unterschied zwischen diesen beiden Automaten?

Ich wüsste leider nicht, dass sowas bisher in unserer Vorlesung behandelt wurde, jedenfalls nicht unter diesem Namen.

Gast

Wofür soll NDEA stehen?

Eigentlich gibt es nur
DEA - Deterministischer endlicher Automat
NEA - Nichtdeterministischer endlicher Automat (hier ist das leere Wort epsilon erlaubt)

Gast

Aso NDEA = NEA oder?

Dann hat der Unterschied bestimmt was mit der Startkonfiguration zu tun.
Vielleicht kanns beim epsilon-ndea einen konfigurationsübergang vom start
zu einer anderen config durch das leeren wort geben beim ndea aber nicht.

Aber ohne gewähr *g

LegionWest · Anmeldungsdatum: 04.12.2005 Beiträge: 7

Ja, der NDEA ist der "Nichtdeterministische endliche Automat". Bei uns scheinen wohl immer neue Bezeichnungen erfunden zu werden grübelnd

Hier einmal die Aufgabenstellung (evtl. wird es dann ersichtlich):

"Gegeben sei der

-NDEA A = ({b,c},{s,p,q},s,{q},

) mit

={
(s,b,p)
(s,c,q)
(p,b,p)
(p,

,q)
(q,c,q)}

Kostruieren Sie den äquivalenten NDEA B. Geben Sie dafür die benötigten

-Abschlüsse an."

Kommt der

-Übergang in einem "normalen" NDEA nicht vor? Wenn das der Unterschied sein sollte, wie wandelt man dann um?

Gast

Aso, du sollst einfach nur das epsilon wegfriemeln *g
Also einen NEA ohne epsilon-Übergänge konstruieren.

Du musst also die (p,epsilon,q) ersetzen.
Ich glaube wenn du das epsilon einfach durch ein b ersetzt ist die Aufgabe schon
gelöst, die beiden NEAs müssten dieselbe Sprache akzeptieren.

Mal dir am besten mal ein Pfeildiagramm.[/quote]

LegionWest · Anmeldungsdatum: 04.12.2005 Beiträge: 7

Vielen Dank für die Antwort!
Doch, wenn ich mich nicht irre, müsste dann (p,

,q) durch (s,b,q) ersetzt werden.
Denn, da beim Original-Automaten auch nur ein einziges b erzeugt werden kann, würde bei einer einfachen Ersetzung von

durch b dies nicht mehr möglich sein.

edit: Selbstverständlich muss (p,

,q) auch durch (p,b,q) ersetzt werden.

Gast

Ja du hast vollkommen recht. Aufgabe gelöst Prost