Turingmaschine + Nichtdeterministischer Automat (Automatentheorie) :-(

[TimB83]

Hallo,

ich stehe im Moment total auf dem Schlau. Wir haben im Fach "Automatentheorie" folgende 3 Aufgaben bekommen - aber ich finde im Internet keine richtige Seite wo man kompakt und hilfreich eine Anleitung findet, wie man dabei vorgehen muss!

Blicke da irgendwie überhaupt nicht durch und bin langsam am verzweifeln :-(

1. Gesucht ist der nichtdeterministische Automate (Graph und formale Beschreibung) für folgende Funktion: A(AvB)*abab

2. Umwandlung von 1. zu einem deterministischen Automaten

3. Auf einem Eingabeband einer Turingmaschine befinden sich beliebig lange, binär dargestellte Zahlen, die auch führende Nullen besitzen können. Die einzelnen Zahlen werden durch das Zeichen "-" voneinander getrennt. Entwerfen sie eine Turingmaschine(formal+Graph) so, dass sie die genannte Eingangsgröße prüft und als korrekt akzeptiert, wenn alle Zahlen kleiner als 7 sind.

Hat vielleicht von euch irgendjemand einen Tipp parat!?

Bis denne

Andreas

[Klotzkopp]

Wir haben im Fach "Automatentheorie" folgende 3 Aufgaben bekommen - aber ich finde im Internet keine richtige Seite wo man kompakt und hilfreich eine Anleitung findet, wie man dabei vorgehen muss!

Warum musst du überhaupt im Internet nach einer Anleitung suchen? Ist nicht genau das Bestandteil des Unterrichts in diesem Fach gewesen?

Zu 1: Konstruktion eines Automaten aus einem regulären Ausdruck

Zu 2: Potenzmengenkonstruktion - Wikipedia

[TimB83]

Hallo,

naja du sprichst mit einem einfachen Anfänger, der dieses Fach hasst und es überhaupt nicht verstanden hat :-(

Der Dozent ist so durch seinen Stoff gerasselt und hat so ein Tempo vorgelegt, sodass man entweder schnell mitschreiben konnte oder aber man hat verloren....

Ich habe mich jetzt mal an die erste Aufgabe gesetzt:

1. Gesucht ist der nichtdeterministische Automate (Graph und formale Beschreibung) für folgende Funktion: A(AvB)*abab

Lösung:

Ich weiß z.B. nicht warum vor der Klammer ein A steht bzw. ob Groß- oder Kleinschreibung unterschieden wird?! Oder steht dieses erste A nur für das Alphabet!?

Kannst du mir einen Tipp geben!?

[Hawkeye]

abab ist aber nicht eine Zustandsänderung, sondern mehrere. Wenn ich das richtig lese, musst Du einen Automaten entwerfen, der Wörter erzeugt, die mit einem A beginnen, dann eine beliebig häufige Folge von A und B beinhalten und mit "abab" enden.

Würde "abab" eine einzige Zustandsänderung sein, wie in Deiner Grafik, dann wäre der Automat deterministisch, weil er bei jeder Eingabe genau eine Aktion ausführen kann.

Selbst wenn die ersten 3 Buchstaben groß sind, musst Du Dir eigentlich nur vor Augen halten, bei welcher Zustandsänderung welcher Folgezustand erreicht wird und daraus ermitteln, wie der Automat arbeiten muss, um ein gültiges Wort erzeugen zu können. Bei nicht-deterministischen Automaten können durchaus bei der selben Eingabe 2 unterschiedliche Zustände erreicht werden.