Prof. Dr. R. Laue                                                                                                                                  WS9899                                 Informatik III
                                Übungsblatt 8
                                Abgabe: 18.1.99 in der Vorlesung

URL: /axel/informatik3_ws9899_blatt8.html
Dieses Übungsblatt ist alleine zu bearbeiten.

Aufgabe 22 (8 Punkte)
Betrachten Sie die Sprache L = {aⁱb^jcⁱ d^j | i >= 1 und j >= 1}. Beweisen Sie, daß diese Sprache nicht kontext frei ist. Tip: Pumping Lemma

Aufgabe 23 (8 Punkte)
Ein nichtdeterminierter Pushdown Automat M besteht aus:

S = endliche Zustandsmenge

= endliche Menge von Eingabezeichen

K = endliche Menge von Kellerzeichen

Anfangszustand S₀ aus S

Kellerstartzustand K₀ aus K

Endzustandsmenge F, Teilmenge von S

Übergangsfunktion

: S x (

{

} ) x K ----> Potenzmege von (S x K^*)

d.h. jedem Tupel wird eine endliche, evtl. leere Menge von Paaren aus S x K^* zugeordnet.
Die von M = ( S ,

, K,

, S₀ ,K₀,F)akzeptierte Sprache wird mit L(M) bezeichnet.

Zeigen Sie: Zu jeder kontextfreien Grammatik G, kann ein Pushdown Automat M mit L(G)=L(M) angegeben werden.