DrJekyll
28-06-2002, 22:04
1)
Geben Sie einen minimalen deterministischen Automaten an, der die durch den egrep-Ausdruck (10?)*[20]?[12]+ beschriebene Sprache akzeptiert. Überprüfen Sie die Minimalität mit einer Unterscheidbarkeitstabelle.
2)
Sei M folgende Teilmenge der Anweisungen in MODULA. Eine Anweisung ist entweder eine Zuweisung, ein Block, ein Konitional, eine Exit-Anweisung oder eine Schleife. Eine Zuweisung besteht aus einem Bezeichner und einem Ausdruck, getrennt durch :=. Ein Block ist eine Anweisungsfolge zwischen BEGIN und END. Ein Konditional besteht aus einem If-Teil, gefolgt von einer beliebigen Anzahl von Elsif-Teilen (auch null), optional gefolgt von einem Ausdruck, dem Wort THEN und einer Anweisungsfolge. Ein Elsif-Teil sieht ebenso aus, beginnt aber mit ELSIF statt mit IF. Ein Else-Teil besteht aus einer Anweisungsfolge, der das Wort ELSE vorangeht. Eine Exit-Anweisung besteht lediglich aus dem Wort EXIT. Eine Schleife ist eine Anweisungsfolge zwischen LOOP und END. Eine Anweisungsfolge ist eine nicht-leere Folge von Anweisungen, die durch Strichpunkte getrennt sind. Ein Bezeichner ist eine Folge von Buchstaben und Ziffen, die mit einem Buchstaben beginnt.
Geben Sie eine kontextfreie Grammatik in EBNF an, die die Sprache M erzeugt. Nehmen Sie an, dass bereits ein Nonterminalsymbol <Ausdruck> mit geeigneten Produktionen existiert, das die Menge der Ausdrücke erzeugt. Verwenden Sie so weit als möglich EBNF-Notationen, um die Grammatik übersichtlich zu halten.
3)
Zeigen Sie mit Hilfe des Hoare-Kalküls die Gültigkeit der folgenden partiellen Korrektheitsaussage über dem Datentyp N.
z = 7 {begin y <-- z + 1; while 3 * y ungleich 4 * z do begin z <-- z + 2; y <--y + 3 end end} z = 15
4)
Erweitern Sie die imperative Sprache AL(N) um eine for-Schleife, d.h., definieren Sie die formale Syntax und Semantik des Konstrukts for v <--t1 to t2 do a (a=Alpha) . Diese Schleife initialisiert die Variable v mit dem Wert des Terms t1 und vergleicht sie mit dem momentanen Wert des Terms t2. Solange v nicht größer als t2 ist, wird das AL-Programm Alpha ausgeführt, der Wert von v um eins erhöht und erneut mit t2 verglichen. Die Schleife terminiert, sobald der Wert von v den aktuellen Wert von t2 übersteigt.
Es genügt, die neu zur Definition von AL hinzukommenden Regeln auszugeben.
Geben Sie einen minimalen deterministischen Automaten an, der die durch den egrep-Ausdruck (10?)*[20]?[12]+ beschriebene Sprache akzeptiert. Überprüfen Sie die Minimalität mit einer Unterscheidbarkeitstabelle.
2)
Sei M folgende Teilmenge der Anweisungen in MODULA. Eine Anweisung ist entweder eine Zuweisung, ein Block, ein Konitional, eine Exit-Anweisung oder eine Schleife. Eine Zuweisung besteht aus einem Bezeichner und einem Ausdruck, getrennt durch :=. Ein Block ist eine Anweisungsfolge zwischen BEGIN und END. Ein Konditional besteht aus einem If-Teil, gefolgt von einer beliebigen Anzahl von Elsif-Teilen (auch null), optional gefolgt von einem Ausdruck, dem Wort THEN und einer Anweisungsfolge. Ein Elsif-Teil sieht ebenso aus, beginnt aber mit ELSIF statt mit IF. Ein Else-Teil besteht aus einer Anweisungsfolge, der das Wort ELSE vorangeht. Eine Exit-Anweisung besteht lediglich aus dem Wort EXIT. Eine Schleife ist eine Anweisungsfolge zwischen LOOP und END. Eine Anweisungsfolge ist eine nicht-leere Folge von Anweisungen, die durch Strichpunkte getrennt sind. Ein Bezeichner ist eine Folge von Buchstaben und Ziffen, die mit einem Buchstaben beginnt.
Geben Sie eine kontextfreie Grammatik in EBNF an, die die Sprache M erzeugt. Nehmen Sie an, dass bereits ein Nonterminalsymbol <Ausdruck> mit geeigneten Produktionen existiert, das die Menge der Ausdrücke erzeugt. Verwenden Sie so weit als möglich EBNF-Notationen, um die Grammatik übersichtlich zu halten.
3)
Zeigen Sie mit Hilfe des Hoare-Kalküls die Gültigkeit der folgenden partiellen Korrektheitsaussage über dem Datentyp N.
z = 7 {begin y <-- z + 1; while 3 * y ungleich 4 * z do begin z <-- z + 2; y <--y + 3 end end} z = 15
4)
Erweitern Sie die imperative Sprache AL(N) um eine for-Schleife, d.h., definieren Sie die formale Syntax und Semantik des Konstrukts for v <--t1 to t2 do a (a=Alpha) . Diese Schleife initialisiert die Variable v mit dem Wert des Terms t1 und vergleicht sie mit dem momentanen Wert des Terms t2. Solange v nicht größer als t2 ist, wird das AL-Programm Alpha ausgeführt, der Wert von v um eins erhöht und erneut mit t2 verglichen. Die Schleife terminiert, sobald der Wert von v den aktuellen Wert von t2 übersteigt.
Es genügt, die neu zur Definition von AL hinzukommenden Regeln auszugeben.