Universität Ulm -Sektion Angewandte Informationsverarbeitung
4.Übungsblatt (17.11.99 bis 24.11.99)
zur Vorlesung Allgemeine Informatik I (WS 99)
Aufgabe 1 (siehe auch: Blatt 3 Aufgabe
1)
(4 Punkte)
Gegeben sei die folgende Grammatik (V, NT, P) mit
V = { *, /, +, -, 0, 1, 2, 3,
4, 5, 6, 7, 8, 9 }
NT = { Faktor, Zahl, Op, Ziffer
}
Startsymbol: Faktor
Produktionsregeln P = {
Faktor->Zahl, Faktor->Faktor
Op Faktor,
Op->*, Op->/, Op->+, Op->-,
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
}
-
Geben Sie eine EBNF-Form der obigen Grammatik an.
(1 Punkt)
-
Modifizieren Sie die EBNF-Grammatik so, daß geklammerte
Verknüpfungen
der Faktoren
möglich sind, wie z.B.: 12
* (3+4) – 18*2 (3
Punkte)
Aufgabe 2 (siehe auch: Blatt 3 Aufgabe
2)
(2 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" }
Zeichnen Sie einen endlichen Automaten, der Sätze der Sprache L erkennt.
(Bitte Start- und Endzustände kennzeichnen!)
Aufgabe 3
(4 Punkte)
Schiller die Letzte! Suchen Sie mit dem UNIX-Tool egrep
(eine Befehlszeile muß jeweils genügen!) nach allen Zeilen in
schiller.ok,
in denen ...
-
... nichts drin steht (vielleicht ein paar Blanks, ein paar Tabs,
ansonsten ist die Zeile leer)
-
... das Wort Freund
am Ende der Zeile steht
-
... das Wort und (Groß/Kleinschreibung
spielt keine Rolle) mindestens 2 mal vorkommt (Achtung: Freunde
soll hier nicht gefunden werden!)
-
... das Wort Koenig oder
das Wort Freund oder
das Wort Freunde (nicht
aber: Freundes) vorkommt
Eine Lösung pro Gruppe genügt. Abgabe im
Tutorium.