Prof. Dr. Franz Schweiggert Institut für Angewandte Informationsverarbeitung 14. November 2006
Norbert Heidenbluth und Ralph GuderleiBlatt 5






Allgemeine Informatik I (WS 2006/2007)


Abgabetermin: 25. November 2006

Die erste Aufgabe beschäftigt sich mit Formalen Sprachen, Grammatiken und Automaten.

In der zweiten Aufgabe geht es um die Anwendung von regulären Ausdrücken.

1 Grammatiken und Automaten

Die formale Sprache $L$ über dem Vokabular $V = \{0,1\}$ sei verbal wie folgt definiert:
$L = \{$ alle mit '1' beginnenden, nichtleeren Zeichenfolgen über $V$, bei denen die Anzahl der unmittelbar aufeinanderfolgenden Einsen '1' gerade und die Anzahl der unmittelbar aufeinanderfolgenden Nullen '0' ungerade ist $\}$

1. Beschreiben Sie $L$ mittels einer regulären Grammatik.
2. Beschreiben Sie $L$ mittels eines deterministischen endlichen Automaten (in graphischer Darstellung).

Die Lösung dieser Aufgabe ist auf Papier anzufertigen.

2 Reguläre Ausdrücke

1. Beschreiben Sie die formale Sprache aus der ersten Aufgabe mit einem regulären Ausdruck.
2. Suchen Sie mit egrep in der Datei pruef.db von Blatt 3 mit einem regulären Ausdruck nach allen Personen, deren Namen mit einem 'A' beginnt und mit einem 's' oder 'd' endet.
3. Öffnen Sie diese Datei mit dem vi(m) und ersetzen Sie (mit einem regulären Ausdruck) das Wort ''Ralf'' durch ''Ralph'' im gesamten Text.
4. Lassen Sie sich alle Dateien in Ihrem Heimatverzeichnis anzeigen, deren Namen mit einem ''a'' beginnt und mindestens 4 Zeichen lang ist (Tipp: ls und egrep)

Viel Erfolg!