Informatiker Board | Automatentheorie | Nichtdeterministischer Automat

Informatiker Board » Themengebiete » Theoretische Informatik » Automatentheorie » Nichtdeterministischer Automat

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Nichtdeterministischer Automat

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Gaius2006
Grünschnabel

Dabei seit: 10.02.2014
Beiträge: 4

Nichtdeterministischer Automat

Zitatantwort auf diesen Beitrag erstellen

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

Nehmen Sie Gaius2006 in Ihre Freundesliste auf

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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]$ -Ü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:

11.02.2014 12:02

Nehmen Sie Karlito in Ihre Freundesliste auf

Gaius2006
Grünschnabel

Dabei seit: 10.02.2014
Beiträge: 4

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:

11.02.2014 14:02

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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:

11.02.2014 15:25

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

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

__________________
Syntax Highlighting fürs Board (Link)

11.02.2014 15:45

Nehmen Sie eulerscheZahl in Ihre Freundesliste auf

Gaius2006
Grünschnabel

Dabei seit: 10.02.2014
Beiträge: 4

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...

11.02.2014 16:33

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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

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 Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Wikipedia ist dein Freund und Helfer...

11.02.2014 21:09

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Automatentheorie » Nichtdeterministischer Automat