- Professur für Theoretische Informatik

Theoretische Informatik 2
Sommersemester 2016
Noleen Köhler
Georg Schnitger
Hannes Seiwert
Institut für Informatik
AG Theoretische Informatik
Ausgabe: 30.05.16
Abgabe: 06.06.16
Übung 7
Aufgabe 7.1. ε-Variablen und nützliche Variablen
(4+4 Punkte)
Nur wenige Fragestellungen im Bereich der kontextfreien Grammatiken besitzen effiziente Lösungen.
Hier besprechen wir einige der wichtigsten dieser effizient lösbaren Fragestellungen.
G = (Σ, V, S, P ) sei eine kontextfreie Grammatik und es gelte V = {X0 , X1 , . . . , Xk } mit X0 = S.
∗
a) Eine Variable X ∈ V heißt eine ε-Variable, wenn X → ε gilt, d.h. wenn das leere Wort in
möglicherweise mehreren Schritten aus X ableitbar ist. Entwerfen Sie einen möglichst effizienten Algorithmus, der alle ε-Variablen von G ausgibt und bestimmen Sie seine Laufzeit in
Abhängigkeit von
X
|G| :=
|α|.
X→α∈P
∗
b) Eine Variable X ∈ V heißt nützlich, wenn X → w für ein Wort w ∈ Σ+ gilt, d.h. wenn
das nicht-leere Wort w aus X in möglicherweise mehreren Schritten ableitbar ist. Entwerfen
Sie einen möglichst effizienten Algorithmus, der alle nützlichen Variablen von G ausgibt und
bestimmen Sie seine Laufzeit in Abhängigkeit von |G|.
Aufgabe 7.2. Das Postsche Korrespondenzproblem
(2+4 Punkte)
Wir sagen, dass das Postsche Korrespondenzproblem (PKP) zu einer Instanz „lösbar“ ist, wenn die
Instanz zur Sprache PKP gehört.
a) Wir betrachten das PKP mit den „Dominosteinen“ (a, ac), (c, ba), (ba, a) und (acb, b). Entscheiden Sie, ob das „Puzzle“ lösbar ist und begründen Sie ihre Antwort.
b) Sei Σ = {1}. Zeigen Sie: Das PKP für Σ = {1} ist entscheidbar. (Aus den Resultaten der
Vorlesung folgt, dass das PKP für alle Alphabete Σ mit |Σ| ≥ 2 unentscheidbar ist.)
Hinweis: Wann ist eine PKP Instanz mit den Dominosteinen (1a , 1b ) und (1c , 1d ) lösbar? (Wir
nehmen natürlich a 6= b und c 6= d an.)
1
Aufgabe 7.3. Eine Reduktion
(5+5 Punkte)
Die Sprache Universalität besteht aus allen kontextfreien Grammatiken G = (Σ, V, S, P ) für die
L(G) = Σ∗
gilt.
a) Die Sprache Regularität besteht aus allen kontextfreien Grammatiken G = (Σ, V, S, P ) für die
L(G) eine reguläre Sprache ist.
Zeigen Sie die Reduktion
Universalität ≤ Regularität.
Hinweis: Für eine beliebige kontextfreie Grammatik G ist – mit einem stets haltenden Programm – eine kontextfreie Grammatik G∗ zu konstruieren, so dass gilt
L(G) = Σ∗ ⇐⇒ L(G∗ ) ist regulär.
(1)
Sei # ein Buchstabe, der nicht zu Σ gehört. Machen Sie den Ansatz
∗
∗
∗
L(G ) = L(G) · # · Σ ∪ Σ · # · L
Natürlich muss L(G∗ ) eine kontextfreie Grammatik sein. Wie sollte man L wählen, so dass (1)
gilt? Begründen Sie Ihre Konstruktion sorgfältig.
Kommentar : In der Vorlesung wurde gezeigt, dass das Universalitätsproblem, also die Sprache
„Universalität“ nicht entscheidbar ist. Als Konsequenz der Reduktion folgt, dass die Sprache
„Regularität“ und damit, dass das Regularitätsproblem nicht entscheidbar ist.
b) Die Sprache DK besteht aus allen kontextfreien Grammatiken G = (Σ, V, S, P ) für die L(G)
eine deterministisch kontextfreie Sprache ist.
Zeigen Sie die Reduktion
Universalität ≤ DK.
Kommentar : Das Problem zu entscheiden, ob eine gegebene kontextfreie Grammatik eine deterministisch kontextfreie Sprache definiert, ist also unentscheidbar.
2

Download Report