Aufgabe 1: Deterministischer Automat(3 Punkte)

Im folgenden Bild ist ein nichtdeterministischer Automat dargestellt, der beliebige Folgen von Nullen und Einsen erzeugt, mit der einzigen Bedingung, daß die Folge mit einer 1 endet:

$\includegraphics[scale=.4]{endlicherAutomat.eps}$

Wie sieht ein äquivalenter deterministischer Automat aus (also ein deterministischer Automat, der die gleiche Sprache erzeugt)?

Aufgabe 2: Reguläre Ausdrücke(4 Punkte)

Im letzten Übungsblatt wurden einige erweiterte Anwendungen von regulären Ausdrücken sowie deren Mächtigkeit aufgezeigt. In diesem Übungsblatt orientieren sich die Aufgaben vorwiegend am Skript. Findet in der Datei example.cpp (die Ihr von unserem ftp-Server downloaden könnt) alle Zeilen,

die mit einem Leerzeichen gefolgt von einem # beginnen
die Klammerpaare der Form () enthalten
bei denen genau 4 Zeichen in runden Klammern stehen
bei denen mehr als 25 Zeichen in runden Klammern stehen
die Leerzeilen sind. Wieviele sind dies?
in denen mindestens ein Punkt vorkommt
in denen mehr als ein Punkt vorkommt
in denen ein + oder * vorkommt. Gibt es noch eine zweite Möglichkeit um dieses Muster auszudrücken?
die weder mit einem *, noch mit einem Leerzeichen, noch mit einem # beginnen
die Klammerpaare der Form () enthalten aber nicht das Wort copy

Aufgabe 3: Das erste Programm(3 Punkte)

Versucht folgendes Programm zu compilieren und zu starten. Erratet welche Zahlenfolge das Programm ausgibt. Beachtet beim compilieren folgendes:

Kopiert Euch die beiden Programmteile WasMacheIch.od und WasMacheIch.om von unserem ftp-Server.
Legt ein Verzeichnis an, in das Ihr BEIDE Programmteile kopiert.
Wechselt in das Verzeichnis und gebt mmo makefile ein. Es sollte eine Datei makefile entstanden sein.
Gebt anschließend make WasMachIch ein. Es sollte die Datei WasMacheIch entstanden sein!
Nun kann das Programm mit WasMacheIch gestartet werden! Dabei sollte die Zahlenfolge 1 2 3 5 8 13 21 34 55 89 144 ausgegeben werden.
Der wichtigste Teil des Programms steht in der Datei WasMacheIch.om und kann mit vi WasMacheIch.om angeschaut werden!

Viel Erfolg!

Hans Braxmeier