Informatikaufgabe Hilfe?
Kellerautomaten
Machen Sie sich mit der Funktionsweise eines Kellerautomaten vertraut und erstellen Sie in AutoEdit einen
Kellerautomaten (KA), der
• Wörter erkennt, bei denen auf n Nullen, n Einsen folgen ( 0n1n )
• arithmetische Ausdrücke nach dem hier angegebenen Alphabet erkennt
Wörter sollen zur vom Kellerautomaten akzeptiert werden, wenn der Kellerspeicher leer ist.
idee
und bei dem zweiten hab ich leider keine Ahnung
Und deine Frage dazu?
Wie würden die entsprechenden Automaten aussehen ?
Was hast du den bisher bereits erarbeitet?
eine idee zum Automaten 1)
werd ich oben einfügen
1 Antwort
Soweit ich das verstehe wird das gelesene Zeichen vom Stack konsumiert. Dann müsste das Beispiel passen soweit.
Zu den Arithmetischen Ausdrücken: Die Beschreibung ist unzureichend, aber ich nehme mal an, dass für jede öffnende Klammer eine passende schließende Klammer existieren muss und dass alle Operatoren binär sind.
Dann sähe eine EBNF folgendermaßen aus:
S -> Exp;
Exp -> Exp Op Exp | (Exp) | Number;
Number -> Digit+;
Der Kellerautomat sollte recht trivial sein. Im Grunde musst du auf dem Stack nur schauen, dass du passende öffnende und schließende Klammern hat, ansonsten musst du keine Stackoperation durchführen.
Im Zustand "Exp" erwartest du als Übergang entweder eine Ziffer oder eine öffnende Klammer.
Wurde eine Ziffer gelesen, so folgt als nächstes entweder eine weitere Ziffer oder ein Operator oder eine schließende Klammer.
Wurde eine öffnende Klammer gelesen so landest du wieder im Zustand "Exp".
Wurde ein Operator gelesen, so landest du wieder im Zustand "Exp".
Wurde eine schließende Klammer gelesen, so folgt entweder eine weitere schließende Klammer oder ein Operator.