Universität Ulm -Sektion Angewandte Informationsverarbeitung

3.Übungsblatt (10.11.99 bis 17.11.99)

zur Vorlesung Allgemeine Informatik I (WS 99)


Aufgabe 1 (6 Punkte)

Gegeben sei die folgende Grammatik (V, NT, P) mit

V = { *, /, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
NT = { Faktor, Zahl, MultOp, Ziffer }
Startsymbol: Faktor

Produktionsregeln P = {

Faktor->Zahl, Faktor->Faktor MultOp Faktor, MultOp->*,
MultOp->/, Zahl->Ziffer, Zahl->Ziffer Zahl, Ziffer->0,
Ziffer->1, Ziffer->2, Ziffer->3, Ziffer->4, Ziffer->5,
Ziffer->6, Ziffer->7, Ziffer->8, Ziffer->9
}

a) Geben Sie die Ableitungsbäume für die folgenden Sätze an (je 1 Punkt)

1.     2 * 3 / 7
2.     123 / 5
b) Erweitern Sie die Grammatik so, daß auch eine additive/subtraktive Verbindung der Faktoren möglich ist, wie z.B.:

       12*3 + 4 – 18/2          (4 Punkte)

 
Aufgabe 2 (4 Punkte)

Gegeben sei die folgende informelle Beschreibung einer formalen Sprache L:

Vokabular V = { 0,1 } (Ziffern 0 und 1)
Sprache L =
{ "alle Folgen aus V*, die mit 00 beginnen und mit einer 1
abschließen, dazwischen kann Beliebiges aus V stehen" }


Geben Sie eine Grammatik (Ersetzungsregeln) dieser Sprache an!

Jeder Teilnehmer muß eine gesonderte Lösung abgeben - via Papier im Tutorium oder via E-Mail!