Compilerbau Blatt 1

Prof. Dr. R. Laue
Dr. A. Kohnert                                                                                                                                     SS 2005 Compilerbau und formale Sprachen
                                Übungsblatt 1

URL: /axel/compiler_ss05_blatt1.html

Dieses Blatt wird am 20.4.2005 besprochen.

Aufgabe 1

Um die Existenz ausserirdischer Lebensformen nachzuweisen, wird ein endlicher Automat gebaut um
in einer ankommenden 0-1 Folge die Zahlenfolge
0,1,2,3,4,5,6,7
in 3-stelliger Binärkodierung zu erkennen.

Geben Sie eine vollständige Definition des zugehörigen endlichen Automaten an?
Zeichnen Sie den Übergangsgraphen.
Wielange wird es dauern bis bei zufälligen Daten eine ausserirdische Lebensform nachgewiesen wird? (Wahrscheinlichkeiten)

Aufgabe 2

Beweisen Sie, dass folgende Dinge nicht von einem endlichen Automaten erkannt werden können:

Zeichenketten über {a,b} mit mehr b's als a's.
Zeichenketten über {p,a,l}, die Palindrome sind, d.h. vorwärts und rückwärts gelesen ergeben sie das gleiche Wort
die Menge der syntaktisch korrekten C Programme.