pigfacejoe - Mi 31.10.12 09:44
Titel: Wie zeige ich,dass Sprache L von DEA akzeptiert wird?

---

Guten Morgen zusammen ;)
Ich sitze seit längerem an einer Aufgabe auf meinem Übungsblatt für Theoretische Informatik: Ich habe einen DEA gegeben und soll zeigen, dass dieser eine Sprache L(M) akzeptiert, L(M) ist natürlich angegeben.
Mir fehlt jedoch eine Idee, wie ich das angehen könnte - hat da vlt. jemand einen Tipp?

Vielen Dank,
Max


Moderiert von Gausi: Topic aus Sonstiges (Delphi) verschoben am Mi 31.10.2012 um 10:25. Hat weder mit Delphi direkt was zu tun, noch mit "Algorithmen und Optimierung", daher wohl (leider) Off-Topic...

Kha - Mi 31.10.12 10:27

---

Da die Sprache höchstwahrscheinlich nicht endlich ist ;) läuft es wahrscheinlich auf vollständige Induktion heraus. Also beispielsweise:
Nach Eingabe von a ist der Automat in Zustand B, "ab" führt ihn von Zustand B wieder dahin, "c" nach Endzustand C, also wird a(ab)*c akzeptiert."
Um zu zeigen, dass er genau L akzeptiert, muss man natürlich noch etwas mehr Arbeit reinstecken, aber das ist so allgemein schwer zu sagen.

Fiete - Do 01.11.12 11:13

---

Moin pigfacejoe,
http://de.wikipedia.org/wiki/Deterministischer_endlicher_Automat
versuche das Automatendiagramm zu erstellen, wenn nicht schon geschehen.
Du hast dann einen besseren Durchblick.
Erstelle zu L(M) deinen eigenen DEA und vergleiche den Aufbau und die Zustände.
Viel Erfolg
Fiete