Automat/Akzeptor

[matcho]

Hallo liebe Comm,

ich soll folgenden nichtdeterministischen Akzeptor (NEA) in einen äquivalenten deterministischen Akzeptor (DEA) umwandeln. Würde mich freuen, wenn ihr mal nen Auge drauf werfen könntet:

NEA:

Umwandlung in DEA:

Bin mir nicht ganz sicher, ob es richtig ist, da nun zwei Endzustände entstanden sind.

[Klotzkopp]

Deine Bild-Links funktionieren nicht. Das Board hat übrigens eine eigene Upload-Funktion.

[matcho]

also nochmal:

[Klotzkopp]

Das ist falsch, dein DEA akzeptiert jede Eingabe aus Nullen und Einsen.

Es sollte dir schon grundsätzlich komisch vorkommen, dass dein DEA weniger Zustände hat als der NEA. Das kann nämlich nicht sein.

Es gibt eine allgemeingültige Vorgehensweise für so eine Umwandlung, ist die dir bekannt?

[Wodar Hospur]

Als kleinen Tipp kannst du versuchen mit dem regulären Ausdruck

(0|1)+0(0|1)+ dir die Aufgabe klar zu machen, wobei + für kleenschen Abschluss ohne e steht(positive Hülle).

Während der Automat den du gebaut hast folgende Form hat:

(0|1)*

[matcho]

nein die vorgehensweise ist mir leider nicht bekannt...

und Wodar Hospur, die kleensche hülle sagt mir leider auch nicht viel

ich werd mich nochmal ransetzen

[Klotzkopp]

nein die vorgehensweise ist mir leider nicht bekannt...

Das wundert mich. Eigentlich sollte man das lernen, bevor man so eine Aufgabe bekommt.

Das Verfahren nennt sich Potenzmengenkonstruktion.

[matcho]

das heißt, man kann jeden NEA nach diesem Verfahren kinderleicht in ein DEA umformen?

[Klotzkopp]

das heißt, man kann jeden NEA nach diesem Verfahren kinderleicht in ein DEA umformen?

"Kinderleicht" ist relativ, aber ansonsten stimmt das.

[Wodar Hospur]

Darf ich fragen in welchem Zusammenhang du dich dann mit Automatentheorie auseinandersetzt. Dir fehlen wohl paar Grundlagen, du kannst versuchen diese mit einem x beliebigen Script aus einer Einführungsveranstaltung theoretische Informatik (Grundlagen der theoretischen Informatik) aufzufrischen/ anzueignen.

[matcho]

ganz einfach, weil ich eine prüfung im februar schreibe zu den theoretischen grundlagen der informatik und akzeptoren/automaten zu 100% dran kommen werden

nur haben wir uns keine algorithmen zur erstellung von akzeptoren angeschaut, sondern eher alles aus der logik heraus entworfen.