| Die letzten 9 Beiträge |
| Karlito |
Wikipedia ist dein Freund und Helfer... |
| Gaius2006 |
Das mit der formalen grammatik geht doch in diese Richtung oder?
S -> 0A
A -> 1B
A -> .
B -> .
mal als ganz einfache version |
| Karlito |
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 |
| Gaius2006 |
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... |
| eulerscheZahl |
@Karlito
bei 1a) hast du die 0 als letztes Zeichen nicht berücksichtigt. |
| Karlito |
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
Karlito hat dieses Bild (verkleinerte Version) angehängt:
|
| Gaius2006 |
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?
Gaius2006 hat dieses Bild (verkleinerte Version) angehängt:
|
| Karlito |
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 ![[latex]\epsilon[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\epsilon) -Übergänge kannst du als Abkürzung verwenden, wenn es weniger als 9 mal 0 sein sollten.
VG,
Karlito
Karlito hat dieses Bild (verkleinerte Version) angehängt:
|
| Gaius2006 |
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:
|
|
|
