Fachrat Informatik - Forum

Quoted

Original von hyperion
Wie kann ich beweisen, dass CFL in NSPACE(n) liegt?

Hinweis: Jede kontextfreie Sprache kann von einem nichtdeterministischen Kellerautomaten erkannt werden. Wieviele Elemente befinden sich bei einem solchen Automaten während der Rechnung höchstens auf dem Keller?

Für jedes gelesene Eingabezeichen kann der Kellerautomat gemäß seinen Überführungsregeln eine konstante Anzahl von neuen Zeichen erzeugen...
bei O(n) Eingabezeichen bleiben es also höchstens cmax*O(n) = O(n) Zeichen auf dem Keller?

DKAs können leider nur einen Teil der kontextfreien Sprachen entscheiden...was aber die NKAs in Platz O(n) machen können, kann eine simulierende NTM M schon lange, diese wird also auch nur einen Platzaufwand O(n) besitzen. Daher ist CFL zumindest schonmal eine Teilmenge von NSPACE(n).
Mh, stimmt das denn soweit...?

Quoted

Original von DrChaotica
Für jedes gelesene Eingabezeichen kann der Kellerautomat gemäß seinen Überführungsregeln eine konstante Anzahl von neuen Zeichen erzeugen...
bei O(n) Eingabezeichen bleiben es also höchstens cmax*O(n) = O(n) Zeichen auf dem Keller?

Soweit richtig. Den Keller kann man also durch ein Arbeitsband der Größe O(n) ersetzen.

Quoted

DKAs können leider nur einen Teil der kontextfreien Sprachen entscheiden...was aber die NKAs in Platz O(n) machen können, kann eine simulierende NTM M schon lange, diese wird also auch nur einen Platzaufwand O(n) besitzen. Daher ist CFL zumindest schonmal eine Teilmenge von NSPACE(n).

Auch richtig. Jetzt ist noch zu erklären, wie eine DTM einen NKA in Platz O(n) simulieren kann.

Danke schon einmal für Eure Antworten.

Quoted

Original von JoachimAuch richtig. Jetzt ist noch zu erklären, wie eine DTM einen NKA in Platz O(n) simulieren kann.

Reicht es hier nicht aus, zu beweisen, dass NSPACE eine Teilmenge von SPACE ist? Oder muss dann erklärt werden wie man einen NKA mit einer DTM simuliert?

@Joachim: jippie! danke

Quoted

Original von hyperion
Reicht es hier nicht aus, zu beweisen, dass NSPACE eine Teilmenge von SPACE ist?

Du meinst, mit Hilfe des Satzes von Savitch? Dann hat man leider NSPACE(n) als Teilmenge von SPACE(n²)...es muß irgendwie einfacher sein, den NKA zu simulieren...
Also los, was gibts denn da? Z.B. Bandkopie und Tiefensuche im simulierten Kellerspeicher, aber dann müßte man sich irgendwo merken, welche Pfade man schon durchlaufen hat. Wie kann man das machen, so dass die zusätzliche Information nur höchstens linear mitwächst?
Mh. Äh ja, Hyperion. Deine Aufgabe

Quoted

Original von hyperion
Reicht es hier nicht aus, zu beweisen, dass NSPACE eine Teilmenge von SPACE ist?

Wenn das gelten würde, würde das reichen. Es gilt aber nicht.

Also einen KA mit einer TM zu simulieren ist ja nicht so das Problem. Schwierig wirds halt nur das Nichtdeterministische da rein zu basteln

Vielleicht kann man ja die Grammtik des NKA so umwandeln, dass man eine deterministische Grammatik erhält und diese dann in die DTM füttern.

Quoted

Original von hyperion
Vielleicht kann man ja die Grammtik des NKA so umwandeln, dass man eine deterministische Grammatik erhält und diese dann in die DTM füttern.

Ein KA mit deterministischen Überführungen ist ein DKA...wenn wir vorher den NKA zum DKA machen, und danach diesen vom DTM simulieren lassen wollen, funktioniert das leider nicht in allen Fällen, da DKAs nicht gleich mächtig sind (Beispiel aus Skript: wort wortR kann von NKAs akzeptiert werden, aber von DKAs nicht).

Quoted

Original von DrChaoticaEin KA mit deterministischen Überführungen ist ein DKA...wenn wir vorher den NKA zum DKA machen, und danach diesen vom DTM simulieren lassen wollen, funktioniert das leider nicht in allen Fällen, da DKAs nicht gleich mächtig sind (Beispiel aus Skript: wort wortR kann von NKAs akzeptiert werden, aber von DKAs nicht).

Hat wer dann vielleicht noch eine andere Idee? Ich weiß da auch nicht mehr so weiter.

Quoted

Original von hyperion

Quoted

Original von DrChaoticaEin KA mit deterministischen Überführungen ist ein DKA...wenn wir vorher den NKA zum DKA machen, und danach diesen vom DTM simulieren lassen wollen, funktioniert das leider nicht in allen Fällen, da DKAs nicht gleich mächtig sind (Beispiel aus Skript: wort wortR kann von NKAs akzeptiert werden, aber von DKAs nicht).

Hat wer dann vielleicht noch eine andere Idee? Ich weiß da auch nicht mehr so weiter.

Schau Dir mal den Beweis zum Satz "NTIME(t) \subseteq SPACE(t)" im Skript an.

Ok, wenn ich das jetzt richtig verstanden habe, benötigt NTIME(t) also einen Platz von O(t). Da NSPACE in NTIME läuft, passt dann auch NSPACE in SPACE?

Quoted

Original von hyperion
Ok, wenn ich das jetzt richtig verstanden habe, benötigt NTIME(t) also einen Platz von O(t). Da NSPACE in NTIME läuft, passt dann auch NSPACE in SPACE?

Ich verstehe diese Sätze nicht. Du wirfst anscheinend Maschinen und Sprachklassen durcheinander (eine Klasse benötigt keine Zeit, sie besteht aus allen Sprachen, die von einer Maschine mit dem entsprechenden Zeitbedarf entschieden werden können).

Zurück zum Thema: Um nachzuweisen, daß eine DTM in Platz O(n) einen NKA simulieren kann, hast Du verschiedene Möglichkeiten:

Zu könntest zunächst zeigen, daß eine NTM einen NKA in Zeit O(n) simulieren kann und dann mit dem von mir erwähnten Satz folgern, daß eine DTM dies in Platz O(n) kann.

Eine andere Möglichkeit wäre, von einer NTM auszugehen, die einen NKA in Platz O(n) simulieren kann und daraus eine DTM zu konstruieren, die dasselbe tut. Auch hier hilft dir Idee des von mir erwähnten Satzes: Um den Berechnungsbaum des NKA in Tiefensuche zu durchsuchen, muß die simulierende DTM nur jeweils den Weg im Baum zur aktuellen Konfiguration speichern. Und dieser hat eine Länge von O(n).

Entschuldige, ich hatte mich vielleicht etwas falsch ausgedrückt.

Quoted

Eine andere Möglichkeit wäre, von einer NTM auszugehen, die einen NKA in Platz O(n) simulieren kann und daraus eine DTM zu konstruieren, die dasselbe tut. Auch hier hilft dir Idee des von mir erwähnten Satzes: Um den Berechnungsbaum des NKA in Tiefensuche zu durchsuchen, muß die simulierende DTM nur jeweils den Weg im Baum zur aktuellen Konfiguration speichern. Und dieser hat eine Länge von O(n).

Der Beweis, auf den Du mich verwiesen hast, sagt, dass für die Tiefensuche nur ein Speicherplatz von O(n) benötigt wird. Dies entspricht doch dann NSPACE(n)?

Nun kann man daraus folgern, dass diese DTM eine NTM simulieren kann und dabei nicht mehr als O(n) Platz belegt.

Quoted

Original von hyperion
Der Beweis, auf den Du mich verwiesen hast, sagt, dass für die Tiefensuche nur ein Speicherplatz von O(n) benötigt wird. Dies entspricht doch dann NSPACE(n)?

Da die Tiefensuche deterministisch durchgeführt wird, kommen wir auf die Klasse SPACE(n).

Wunderbar. Genau das wollte ich wissen. Danke, auch wenns ein wenig länger gedauert hat.

@Joachim

Auf http://www.thi.uni-hannover.de/lehre/ss06/klausuren/ steht ja:

Hilfsmittel: Vorlesungsskript „Komplexität von Algorithmen“ ohne handschriftliche (oder andere) Ergänzungen.....

Zählt ihr Markierungen mit Textmarker (also nicht geschrieben sondern nur angestrichen) als "andere" Ergänzung, oder ist das ok?
Sonst müsste ich mir (wie wahrscheinlich viele andere) das Skript neu ausdrucken.

Gruß 3Stan

Quoted

Original von 3St@n
Zählt ihr Markierungen mit Textmarker (also nicht geschrieben sondern nur angestrichen) als "andere" Ergänzung, oder ist das ok?

Markierungen mit Textmarker sind in Ordnung. Allerdings nur, wenn es sich auch tatsächlich nur um Markierungen und nicht um damit geschriebenen Text handelt.

Wunderbar geht klar. Da haben wir doch der Umwelt mal wieder was gutes getan.

Ich kann mit Fug und Recht behaupten, dass dies wohl diejenige Klausur war, in welche ich (relativ zu allen anderen Klausuren gesehen) mit den meisten Problemen hineingegangen sein werde.
Har, har. 'Probleme'.

Falls mein Korrektor das liest: Mit n nicht Element von O(n²) habe ich natürlich genau das Gegenteil gemeint, argh.

Mh, vielleicht habe ich es in der Vorlesung damals nicht richtig mitbekommen...
wir hatten doch in THI die vier Sprachklassen der Chomsky-Hierarchie kennengelernt.

Ist es eigentlich beweisbar, bzw. wurde vielleicht sogar bereits bewiesen, dass sich die Sprachen in nicht mehr als genau diese vier Typen 0 bis 3 (oder äquivalente Klassen) aufteilen lassen? Oder könnte man eventuell noch speziellere Unterteilungen finden sowie entsprechende Automatenmodelle, die diese Sprachklassen erkennen könnten?

Ich hoffe, für diese Frage schlägt mich jetzt keiner...

Achja, dann vielleicht noch etwas zu der Klausur:

[SAT] ist doch die Äquivalenzklasse der NP-vollständigen Sprachen, oder?
Ist dementsprechend [A] für A element P, A!={}, A!=E* die Klasse der P-Sprachen? Oder gab es hier eine Besonderheit, auf die man hätte achten müssen?

In einer anderen Aufgabe sollten wir die NP-Härte von QUAD-SAT zeigen...leider hatte ich mir das ähnliche Problem DOUBLE-SAT aus den Übungen nicht mehr angesehen, und den Beweis ausgelassen... aber das ginge doch eventuell mit einer Reduktion von SAT auf QUAD-SAT, indem man der zu erfüllenden Formel einfach neue Variablen anhängt, so dass es neben der ursrünglichen erfüllenden Belegung 2^n-1 weitere gibt, oder?
(ich hoffe QUAD-SAT element NP zu zeigen gab hier mal mehr Punkte... )

Wie sah das denn nun eigentlich mit CSL element SPACE(n²) aus? Kontextsensitive Sprachen werden von LBAs entschieden, aber wie kann das weiterhelfen?