NF 1, SS 1997: Lösungsblatt 8: Taschenrechner

Aufgabe 1: Operatorpräzedenz im Taschenrechner

Bisher war auf die Operatorpräzedenz (Punkt- vor Strichrechnung) beim Taschenrechner aus der letzten Aufgabe keine Rücksicht genommen worden.

Entwerfen sie einen endlichen Automaten mit Ausgabe, der Punkt- vor Strichrechnung beherrscht. Die Randbedingungen sind dabei wie gehabt: Eingabezahlen sind 0 und 1, Operatoren sind + (Addition) und * (Multiplikation), der Wertebereich der Resultate ist 0 bis 4.

Der Automat soll folglich Aufgaben dieses Typs lösen können:

0 + 1 * 0 + 1 = 1

Lösung hierzu

Aufgabe 2: Taschenrechner mit Klammerfunktion

Zeigen Sie, wie man den endlichen Automaten mit Ausgabe aus Aufgabe 1 modifizieren muß, sodaß er Klammerfunktionen beherrscht. Zusätzlich zu den bisher erlaubten Eingaben kommen also die Klammern ( und ) dazu.

Der Automat soll Aufgaben dieses Typs lösen können:

1 * (1 * 0 + 1) + 1 = 2

Lösung hierzu

Für jede Ebene von Klammerung muß ein zusätzlicher Automat vorliegen, der den Wert des geklammerten Ausdrucks berechnet. Dabei gilt nicht, wie bisher, das Gleichheitszseichen als beendendes Element, sondern die schließende Klammer. Von den Ergebniszuständen, die das Resultat des geklammerten Ausdrucks repräsentieren, müssen Kanten zum aufrufenden Automaten laufen, die den Wert in die Berechnug einbeziehen.

Kompliziert wird die Sache dadurch, daß durch die Klammerung nun Multiplikation mit Werten außer 0 und 1 möglich wird (z.B. '1 * (1 + 1) ='). Das bedeutet, daß alle Automaten nicht nur für die Addition vier verschiedene Zustände benötigen, sondern auch für jede Multiplikation. Dies gilt für alle Automaten außer dem für die innerste Klammerebene zuständigen.

Man sieht: Das Auswerten eingeschränkter arithmetischer Ausdrücke kann mit Hilfe endlicher Automaten mit Ausgabe modelliert werden, es ist nur extrem aufwendig. Die Einschränkungen, die man unbedingt vornehmen muß, sind ainerseits die Beschränkung euf endlich viele (möglichst wenige) Klammerebenen, zum andern aber auch die Beschränkung auf einen (kleinen) endlichen Resultatbereich. Die Moddellierung echter reeller Zahlen scheidet von vorneherein aus.

Aufgabe 3: EBNF-Syntax von regulären Ausdrücken

Stellen Sie ein EBNF-Syntaxdiagramm für reguläre Ausdrücke auf.

Lösung hierzu