Prof. Dr. R. Laue
Dr. A. Kohnert
SS 2005
Compilerbau und formale Sprachen
Übungsblatt 2
URL:
/axel/compiler_ss05_blatt2.html
Dieses Blatt wird am 27.4.2005 besprochen.
Aufgabe 3
Welche der nachfolgenden Sprachen kann durch einen endlichen Automaten
erkannt
werden, d.h. ist regulär? Beweise.
- L1={endliche Wörter über {a,b} mit gleichen Anfangs und
Endbuchstaben }
- L2={ Wörter über {a,b} mit mindestens 2005 b's }
- L3={ Zahlen über {0,...,8,9} welche durch 7 teilbar
sind } (nur für Mathematiker)
- L4={ Wörter über {a,b} mit gleichviel a's und b's
}
- L5={ Wörter w über {a,b} die aus 2 gleichen Teilen v
besteht, d.h. w=vv }
Aufgabe 4
Baue einen nicht deterministischen endlichen Automaten
(Definition und Zustandsgraph) zur Erkennung folgender Sprachen:
binäre Zahlen, die ein Vielfaches
von 4 sind. (Wörter über {0,1})
c ((b|a*c) x)*| x*b (Wörter
über {a,b,c,x} )
Wandle den Automaten für die zweite Sprache in einen
deterministischen endlichen Automaten um.
Aufgabe 5
Eine Sprache heißt regulär, wenn sie durch einen
regulären Ausdruck beschreiben werden kann, oder
was equivalent ist durch einen endlichen Automaten
akzeptiert wird. Beweisen Sie das Pumping Lemma
für reguläre Sprachen:
Sei L eine reguläre Sprache,
dann gibt es eine Konstante n, sodaß jedes Wort z aus L mit
>= n Buchstaben
geschrieben werden kann als z = uvw (Produkt =
hintereinander Schreiben von Teilworten) wobei die Länge von
uv <= n und die Länge von v >= 1
ist. Es gilt dann für alle i >= 0:
u v^i w liegt auch in L
Tip: n hat was mit der Anzahl der Zustände
des Automaten zu tun.
Zeigen Sie für mindestens eine Sprache aus Aufgabe 3 mit diesem
Pumping Lemma, dass sie nicht regulär ist.