Fachrat Informatik - Forum

Quoted

Original von Thomas
Auf der Seite 49 im Skript geht es um den Beweis für das Leerheitsproblem für Typ 1 Sprachen. Und zwar ist der letzte Satz unverständlich: Was bedeutet genau "G nicht element Leerheitsproblem"? Erzeugt G dann Wörter einer nicht leeren Sprache ODER ist G=leere_Menge unentscheidbar?

Das wird weiter vorne im Skript definiert.

Schnittproblem für Typ-i-Sprachen: Die Menge aller Paare von Grammatiken vom Typ i, deren Durchschnitt der erzeugten Sprachen nicht leer ist.

Leerheitsproblem für Typ-i-Sprachen: Die Menge aller Grammatiken vom Typ i, die die leere Sprache erzeugen.

Quoted

Original von Thomas
nun habe ich noch fragen zu übung 7.1:

wie ist die funktion delta' definiert? da steht delta'(z,a,B') --> (z,aC'), d.h. B' wird durch aC' ersetzt und der zustand beibehalten. wie geht es aber weiter? für ein terminal auf dem keller ist gar keine überführung definiert. der ka müsste also stehen bleiben...???

ausserdem ist mir noch nicht klar, wie M' sicherstellt, dass das letzte kellersymbol markiert wird, so dass M' dann schließlich akzeptieren kann?

Keine Ahnung, wie das in der Übung vorgerechnet wurde, ich war da nur sehr selten. Ich kann aber mal meine Lösung skizzieren, vielleicht wird es dann klarer:

Seien L eine kontextfreie Sprache und L' := L \ {epsilon}. Zudem sei G := (N, Sigma, R, S) eine Grammatik in Greibach-Normalform, die L' erzeugt. (Die Definition von L' haben wir vorgenommen, da es nur für kontextfreie Sprachen ohne das leere Wort eine Grammatik in Greibach-Normalform gibt. Wir kommen ganz am Ende auf diese Einschränkung zurück.)

Aus der Vorlesung ist bekannt, daß der Kellerautomat M := ({z}, Sigma, N, delta, z, S) mit
(z, gamma) \in delta(z, a, A) <=> A -> a gamma \in R
für alle a \in Sigma, A \in N und gamma \in N^*
die Sprache L' durch Leeren des Kellers erkennt (also L' = N(M)). Durch diese Konstruktion besitzt M keine epsilon-Übergänge.

Aus M müssen wir nun einen Kellerautomaten M_neu konstruieren, der L' durch vollständiges Lesen der Eingabe erkennt (also L' = L(M_neu)). Die Forderung, daß M_neu keine epsilon-Übergänge enthalten soll, haben wir ja bereits in M erfüllt.

Zunächst definieren wir einen Kellerautomaten M_mark, der sich genauso wie M verhält, dessen unterstes Kellersymbol jedoch stets eine Markierung enthält. Dazu verdoppeln wir das Kelleralphabet, fügen also für jedes Zeichen a \in N ein neues Zeichen a' zum Kelleralphabet hinzu. Das Verhalten von M_mark definieren wir genauso wie das von M, nur mit dem Unterschied, daß in jedem Rechenschritt, in dem das unterste (also markierte) Kellersymbol vom Keller gelesen wird, auf dem Keller statt des bisherigen neuen untersten Kellersymbols die markierte Version dieses Symbols geschrieben wird.

Auf diese Weise können wir bereits vor der Ausführung eines Rechenschrittes herausfinden, ob in diesem Rechenschritt der Keller vollständig geleert wird und M_mark dadurch anhält. Dies ist nämlich genau dann der Fall, wenn ein markiertes Symbol vom Keller gelesen wird, aber kein neues darauf geschrieben wird.

Damit können wir M_neu definieren. M_neu verhält sich genauso wie M_mark, hat aber einen Zustand mehr. Dieser Zustand (wir nennen ihn z') soll der einzige Endzustand von M_mark sein. Zudem ergänzen wir das Kelleralphabet und ein neues Symbol, nennen wir es #. Damit M_neu durch vollständiges Lesen der Eingabe genau die Wörter akzeptiert, die M_mark durch Leeren des Kellers akzeptiert, müssen wir das Verhalten von M_mark wie folgt verändern. Immer dann, wenn der Keller vollständig geleert (also die Eingabe akzeptiert) wird, schreiben wir das Symbol # auf den Keller und gehen in den Endzustand z' über. Lesen wir nun das Symbol # vom Keller im Zustand z', so lassen wir sowohl den Zustand als auch den Keller unverändert und Lesen das nächste Eingabezeichen. Auf diese Weise haben wir irgendwann die Eingabe vollständig gelesen und sind immer noch im Zustand z', also in einem Endzustand.

M_neu ist damit ein Kellerautomat, der keine epsilon-Übergänge besitzt, und die Sprache L' per Endzustand (und vollständiges Lesen der Eingabe) akzeptiert.

Aus diesem Automaten läßt sich nun ganz einfach ein Automat machen, der die Sprache L akzeptiert. Falls L das leere Wort nicht akzeptiert, so ist M_neu bereits der gesuchte Automat. Ist das leere Wort in L enthalten, so fügen wir zu M_neu einen weiteren Zustand hinzu (nennen wir ihn z''). Dieser Zustand z'' wird der Startzustand von M_neu und ist gleichzeitig ein Endzustand. Damit wird die leere Eingabe akzeptiert. Damit sich der Automat nun für alle anderen Eingaben genauso verhält wie vorher, definieren wir die Übergangsfunktion so, daß aus dem Zustand z'' immer der Zustand z (oder falls Akzeptanz vorliegt z') erreicht wird. Damit haben wir den Sonderfall des leeren Wortes behandelt.

Fertig.

Ich hoffe, das war einigermaßen verständlich. Falls nicht: Bitte konkret nachfragen.