---

Geschrieben von Gaius2006 am 10.02.2014 um 21:20:

  Nichtdeterministischer Automat

Meine Frage:
Hi,
stehe gerade am Anfang der Automatenlehrer im Informatikgrundkurs am Gymnasium und komme bei dieser Aufgabe nicht weiter:


Hier die Aufgabe:

A1)
a)
Definieren Sie einen NEA (NFA), der folgende Sprache akzeptiert:
Die Menge der Zeichenreihen aus dem Alphabet {0,1,2,...,9}, derart, dass die letzte Ziffer schon vorher vorgekommen ist.

b)
Entwerfen sie einen NEA (Epsilon), der die folgende Sprache akzeptiert.
Die Menge aller aus Nullen und Einsen bestehenden Zeichenreihen, derart, dass mindestens eine der letzten zehn Stellen eine 1 ist.
Benutzen sie (Epsilon)-Übergänge um ihren Entwurf zu vereinfachen.

Vielen Dank schonmal im Vorraus!
LG

Meine Ideen:
Bei genannter Aufgabe habe ich schon mehrfach gegoogelt und auch versucht das mit Hilfe unserer "Lernseite" (www.inf-schule.de) herauszubekommen, aber für mich ist das einfach nicht schlüssig.
Habe mal zu Punkt a) einen Automaten gemacht...

---

Geschrieben von Karlito am 11.02.2014 um 12:02:

 

Hallo Gaius2006,

bei der Aufgaben A1 a) musst du dir den Nichtdeterminismus zu Nutze machen, sonst wird der Automat sehr groß (1026 Zustände, wenn ich richtig gerechnet habe).

Wir wissen als Vorraussetzung, dass der Automat beliebige folgen des Alphabets akzeptiert. Dann muss irgendwann (nicht deterministisch) ein Zeichen folgen, welches am Ende noch einmal folgt. Danach kann wieder eine beliebige Folge aus dem Alphabet folgen. Als letztes dann wieder Endzeichen um den Finalzustand zu erreichen. (s. Anhang)

Zu der zweiten Aufgabe gebe ich dir erstmal nur den Tipp, dass der Finalzustand nu dann erreich werden kann, wenn höchstens 9 mal 0 vorher ersscheint. Die -Übergänge kannst du als Abkürzung verwenden, wenn es weniger als 9 mal 0 sein sollten.

VG,

Karlito

---

Geschrieben von Gaius2006 am 11.02.2014 um 14:02:



Vielen vielen Dank für die schnelle und gute Antwort !
Hat mir im Verständnis schon sehr weitergeholfen.

Also hab das mal versucht
1b)

Hab im Anhang das Bild von rein gemacht.
Habe bis jetzt keine Zahl gefunden die nicht funktioniert.
Zahlen die länger als 10 sind sollten ja so nicht funktionieren und zehn Nuller auch nicht.

Da bleibt mir noch aus der Aufgabenstellung die Frage ob es auch größer als 10Stellen sein dürfen , wenn ja müsste man ja nurnoch eine Schleife an den Finalzustand packen in der 0 und 1 erlaubt sind oder?

---

Geschrieben von Karlito am 11.02.2014 um 15:25:

 

Hallo Gaius2006,

erstmal ist dein Automat richtig. Ich konnte auch keinen Fehler entdecken.

Zitat:

Original von Gaius2006 Da bleibt mir noch aus der Aufgabenstellung die Frage ob es auch größer als 10Stellen sein dürfen , wenn ja müsste man ja nurnoch eine Schleife an den Finalzustand packen in der 0 und 1 erlaubt sind oder?

Gefragt ist nach der Menge Menge aller aus Nullen und Einsen bestehenden Zeichenreihen. Einzige Einschränkung ist, dass mindestens eine der letzten 10 Zeichen eine "1" ist. Somit müssen mehr als 10 Zeichen zugelassen werden.
Dein Lösungsansatz ist dafür auch richtig.

Im Anhang findest du noch einen kleineren Automaten, welcher die selbe Funktion erfüllt, jedoch mit weniger Zuständen auskommt.

VG,

Karlito

---

Geschrieben von eulerscheZahl am 11.02.2014 um 15:45:

 

@Karlito
bei 1a) hast du die 0 als letztes Zeichen nicht berücksichtigt.

---

Geschrieben von Gaius2006 am 11.02.2014 um 16:33:

  Dankeschön

Erstmal ein erneutes großes Dankeschön @Karlito!!!

@eulerscheZahl auch danke hab es ergänz.

Dürfte ich euch noch eine letzte Frage stellen?
Wir schreiben morgen Kursarbeit darüber und ansonsten ist mir dank der Beiträge alles klar, jetzt habe ich eine Aufgabe entdeckt die mich wieder rausbringt:

A4)
Finde einen Automaten der überprüft ob ein Wort ein Palindrom ist.
(Beispiel: Regen - Neger; Rentner - Rentner)

Mache eine Summenangabe und gib alle Produktionen an.
Kommentiere dein Vorgehen.

Mit den Nichtdeterministischen und deterministischen Automaten komm ich da auf keine Lösung? Gibt es noch andere? Beim googeln ist mir der Kellerautomat aufgefallen, wobei die Erklärungen bei mir mal wieder nur für Verwirrung sorgen...

---

Geschrieben von Karlito am 11.02.2014 um 17:01:

  RE: Dankeschön

Hallo Gaius2006,

Zitat:

Original von Gaius2006 A4) Finde einen Automaten der überprüft ob ein Wort ein Palindrom ist. (Beispiel: Regen - Neger; Rentner - Rentner) Mache eine Summenangabe und gib alle Produktionen an. Kommentiere dein Vorgehen. Mit den Nichtdeterministischen und deterministischen Automaten komm ich da auf keine Lösung? Gibt es noch andere? Beim googeln ist mir der Kellerautomat aufgefallen, wobei die Erklärungen bei mir mal wieder nur für Verwirrung sorgen...

Diese Aufgabe kann nur mit Kellerautomaten oder mächtigeren Automaten gelöst werden (Turingmaschine).

Die Aufgabe, Produktionen anzugeben fordert zur Erstellung einer formalen Grammatik auf. Hattet ihr das schon?

Zitat:

Original von eulerscheZahl @Karlito bei 1a) hast du die 0 als letztes Zeichen nicht berücksichtigt.

Danke euler!

VG,

Karlito

---

Geschrieben von Gaius2006 am 11.02.2014 um 20:35:

 

Das mit der formalen grammatik geht doch in diese Richtung oder?

S -> 0A
A -> 1B
A -> .
B -> .

mal als ganz einfache version

---

Geschrieben von Karlito am 11.02.2014 um 21:09:

 

Wikipedia ist dein Freund und Helfer...