Nichtdeterministischer Automat |
Gaius2006
Grünschnabel
Dabei seit: 10.02.2014
Beiträge: 4
|
|
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...
Gaius2006 hat dieses Bild (verkleinerte Version) angehängt:
|
|
10.02.2014 21:20 |
|
|
Gaius2006
Grünschnabel
Dabei seit: 10.02.2014
Beiträge: 4
|
|
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...
|
|
11.02.2014 16:33 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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
|
|
11.02.2014 17:01 |
|
|
Gaius2006
Grünschnabel
Dabei seit: 10.02.2014
Beiträge: 4
|
|
Das mit der formalen grammatik geht doch in diese Richtung oder?
S -> 0A
A -> 1B
A -> .
B -> .
mal als ganz einfache version
|
|
11.02.2014 20:35 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
|
11.02.2014 21:09 |
|
|
|