Endlicher Automat...

P

pilx

Mitglied
Hi,

ich soll zur Übung einen endlichen Automaten schreiben. Hört sich so an als ob das eine "Standartaufgabe" wäre, die mehr oder weniger jeder im ersten Semester zu erledigen hat ;)
Naja auf jeden Fall verstehe ich noch nicht ganz was mit einem endlichen Automaten gemeint ist.
Ich kann euch die Aufgabe ja mal verlinken Aufgabe 4.2 (30 Punkte)
Also ich bin jetzt soweit, dass ich mir klar gemacht habe ich gebe einen String ein und dieser wird Buchstabe (char) für Buchstabe durchgegangen vom Automaten richtig? Und am Ende kommt halt wahr oder falsch raus aber ich habe leider keine Ahnung wie ich das in Java implementieren soll :(

Ich hoffe/denke, dass mir hier jemand weiterhelfen kann ;)
 
P

pilx

Mitglied
Habe ich ja schon trotzdem verstehe ich das Ding nicht wirklich. Entweder es ist zu kompliziert oder ich stehe total auf dem Schlauch. Wie soll ich denn, wenn ich einen String Zeichen für Zeichen durchgehe am Ende prüfen, ob der gesamte String den Anforderungen entspricht?
 
M

Marco13

Top Contributor
Das erkennt man daran, ob man in einem gütigen Zustand ist (bin schon ein bißchen raus, aber gibt's da nicht üblicherweise sogar ein explizites "ENDE"-Zeichen, damit man in den Endzustand geht?)

Hast du die ersten beiden Teile schon? Wie sieht das da bisher aus?

Die einzelnen Zeichen eines Strings kann man mit
Code: 
for (int i=0; i<string.length(); i++)
{
    char zeichen = string.charAt(i);
    ...
}
untersuchen...
 
A

Andi_CH

Top Contributor
pilx hat gesagt.:
Habe ich ja schon trotzdem verstehe ich das Ding nicht wirklich. Entweder es ist zu kompliziert oder ich stehe total auf dem Schlauch. Wie soll ich denn, wenn ich einen String Zeichen für Zeichen durchgehe am Ende prüfen, ob der gesamte String den Anforderungen entspricht?
Zum Vergrößern anklicken....

Wenn der erste Buchstabe den Anforderungen entspricht und der Zweite auch und der Dritte auch und die Folgenden auch und der Letzte auch, dann entspricht der ganze String den Anforderungen - Wenn ich jetzt "auf dem Schlauch stehe" sag es mir einfach ???:L
 
G

Gast2

Gast
Andi_CH hat gesagt.:
Wenn der erste Buchstabe den Anforderungen entspricht und der Zweite auch und der Dritte auch und die Folgenden auch und der Letzte auch, dann entspricht der ganze String den Anforderungen - Wenn ich jetzt "auf dem Schlauch stehe" sag es mir einfach ???:L
Zum Vergrößern anklicken....

Um es mal so sagen: Versucht es etwas mathematischer auszudrücken... Weg von Strings, Buchstaben und "Anforderungen" erfüllen. Ein endlicher Automat ist erstmal nur ein Model. Wenn man das einmal verstanden hat ist es recht einfach und universell übertragbar.

Das wichtigste ist imho also erstmal sich in Endliche Automaten und formale Grammatiken einzuarbeiten und dann an einer konkreten Aufgabe zu arbeiten.

Du hast eine Menge von Zuständen (inkl einem Startzustand und einer Menge Endzustände), du hast eine Menge von gültigen Transitionen zwischen Zuständen.

Stell dir einfach vor was passiert wenn du im Startzustand eine Eingabe machst. Was pasiert dann? Wohin führt dich das? Was passiert dann bei der nächsten Eingabe? Usw.

Ziel ist es letztendlich zu bestimmen ob ein Eingabewort von dem Automaten aktzeptiert wird - sprich ob dieses Wort Teil der formale Sprache ist die durch die zugrundelegende formalen Grammatik beschrieben ist.
 

Aktuelle Jobs

Neue Themen


Oben