close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

17. Dezember

EinbettenHerunterladen
313
Das Postsche Korrespondenzproblem
Beispiel
aSbS, ε
▲
Sei G ❼➌S ➑, ➌a, b ➑, ➌S
▲
Die MPCP-Instanz f ❼aabb ➁ enthält dann die acht Wortpaare
f ❼aabb ➁ ▲
✟
❵❙
▲
➈
S S a b
❙
S aSbS ε S a b
❙
❵
❵❙
S
✟
aabb ❙ ❡
✟
❡
Der Ableitung S aSbS aaSbSbS aaSbbS
entspricht dann das MPCP-Lösungswort
❵❙
▲
➆
, S ➁ und w aabb.
➑
➇
.
➉
✟ aabbS ✟ aabb
S ❙ aSbS ❙ aaSbSbS ❙ aaSbbS ❙ aabbS ❙ aabb ❙ ❡
S ❙ aSbS ❙ aaSbSbS ❙ aaSbbS ❙ aabbS ❙ aabb ❙ ❡
Das kürzeste MPCP-Lösungswort für f ❼aabb ➁ ist
❵ ❙ S ❙ aSbS ❙ aaSbSb ❙ aabb ❙ ❡
❵ ❙ S ❙ aSbS ❙ aaSbSb ❙ aabb ❙ ❡
Dieses entspricht der „parallelisierten“ Ableitung
S aSbS 2 aaSbSb
✟
✟
✟2 aabb
❘
Das Schnittproblem für CFL ist unentscheidbar
Das Schnittproblem für kontextfreie Grammatiken
Gegeben: Zwei kontextfreie Grammatiken G1 und G2 .
Gefragt: Ist L❼G1 ➁ ✾ L❼G2 ➁ ① ❣?
Satz
Das Schnittproblem für kontextfreie Grammatiken ist RE-vollständig.
Beweis
▲
▲
Es ist leicht zu sehen, dass das Problem semi-entscheidbar ist.
Um PCP auf dieses Problem zu reduzieren, betrachte für eine Folge
s ❼x1 , . . . , xk ➁ von Strings xi ❃ ➌a, b ➑ die Sprache
Ls ➌in . . . i1 #xi1 ✆xin ❙ n ❈ 1, 1 ❇ i1 , . . . , in ❇ k ➑.
❻
▲
Ls wird von der Grammatik Gs ❼➌A➑, ➌1, . . . , k, #, a, b ➑, Ps , A➁
erzeugt mit
Ps : A 1Ax1 , . . . , kAxk , 1#x1 , . . . , k#xk
314
Das Schnittproblem für CFL ist unentscheidbar
315
Reduktion von PCP auf das Schnittproblem für CFL
▲
▲
...xk
➂ bilden wir das Paar ❼Gs , Gt ➁, wobei
Zu einer PCP-Instanz I ❽yx11 ...y
k
s ❼x1 , . . . , xk ➁ und t ❼y1 , . . . , yk ➁ ist.
Dann ist L❼Gs ➁ ✾ L❼Gt ➁ die Sprache
➌in . . . i1 #xi1
▲
▲
. . . xin ❙ 1 ❇ n, xi1 . . . xin yi1 . . . yin ➑.
Folglich ist α ❼i1 , . . . , in ➁ genau dann eine Lösung für I, wenn
in . . . i1 #xi1 . . . xin ❃ L❼Gs ➁ ✾ L❼Gt ➁ ist.
✭
Also vermittelt f ✂ I ❼Gs , Gt ➁ eine Reduktion von PCP auf das
Schnittproblem für CFL.
❥
Das Schnittproblem für CFL ist unentscheidbar
316
Beispiel
▲
Die PCP-Instanz
x1 x2 x3
a
aab abbaa
I ❿
➄ ❿
➄
y1 y2 y3
aabba ababb aa
wird auf das Grammatikpaar ❼Gs , Gt ➁ mit folgenden Regeln reduziert:
Ps : A
1Aa, 2Aaab, 3Aabbaa,
1#a, 2#aab, 3#abbaa,
Pt : A
1Aaabba, 2Aababb, 3Aaa,
1#aabba, 2#ababb, 3#aa.
▲
Der PCP-Lösung α ❼1, 3, 2, 3➁ entspricht dann das Wort
3231#x1 x3 x2 x3 3231#aabbaaaababbaa
3231#aabbaaaababbaa 3231#y1 y3 y2 y3
im Schnitt L❼Gs ➁ ✾ L❼Gt ➁.
❘
Das Schnitt- und das Inklusionsproblem für DCFL
317
Das Inklusionsproblem für DPDAs
Gegeben: Zwei DPDAs M1 und M2 .
Gefragt: Gilt L❼M1 ➁ ❜ L❼M2 ➁?
Korollar
1. Das Schnittproblem für DPDAs ist RE-vollständig.
2. Das Inklusionsproblem für DPDAs ist co-RE-vollständig.
Beweisidee.
Die kontextfreie Grammatik Gs in obigem Beweis lässt sich leicht in
DPDAs Ms und M s überführen mit L❼Ms ➁ L❼Gs ➁ und L❼M s ➁ L❼Gs ➁
(siehe Übungen).
Weitere Unentscheidbarkeitsresultate für CFL
318
Korollar
Für kontextfreie Grammatiken sind folgende Probleme unentscheidbar:
1. Ist L❼G ➁ Σ ?
(Ausschöpfungsproblem)
❻
2. Ist L❼G1 ➁ L❼G2 ➁?
(Äquivalenzproblem)
3. Ist G mehrdeutig?
(Mehrdeutigkeitsproblem)
1. Das Ausschöpfungsproblem für CFL ist co-RE-vollständig
Wir reduzieren das Komplement von PCP auf das Ausschöpfungsproblem für kontextfreie Grammatiken. Es gilt
I ❃⑦ PCP
Ls ✾ Lt ❣
Ls ✽ Lt Σ .
✔
✔
Daher vermittelt die Funktion f ✂ I
Grammatik mit
❻
✭ G, wobei G eine kontextfreie
L❼G ➁ Ls ✽ Lt
ist, die gewünschte Reduktion.
❥
319
Weitere Unentscheidbarkeitsresultate für CFL
Korollar
Für kontextfreie Grammatiken sind folgende Probleme unentscheidbar:
1. Ist L❼G ➁ Σ ?
(Ausschöpfungsproblem)
❻
2. Ist L❼G1 ➁ L❼G2 ➁?
3. Ist G mehrdeutig?
(Äquivalenzproblem)
(Mehrdeutigkeitsproblem)
2. Das Äquivalenzproblem für CFL ist co-RE-vollständig
Wir reduzieren das Ausschöpfungsproblem für CFL auf das
Äquivalenzproblem für CFL.
Dies leistet beispielsweise die Reduktionsfunktion
f ✂G
✭ ❼G, Gall ➁,
wobei Gall eine kontextfreie Grammatik mit L❼Gall ➁ Σ ist.
❻
❥
Weitere Unentscheidbarkeitsresultate für CFL
320
3. Das Mehrdeutigkeitsproblem ist RE-vollständig
▲
Wir reduzieren PCP auf dieses Problem.
▲
...xk
➂ in die Grammatik
Hierzu überführen wir eine PCP-Instanz I ❽yx11 ...y
k
G ❼➌S, A, B ➑, ➌a, b, 1, . . . , k ➑, P ✽ ➌S
A, S B ➑, S ➁
mit den Regeln
1Ax1, . . . , kAxk , 1#x1, . . . , k#xk ,
B 1By1 , . . . , kByk , 1#y1 , . . . , k#yk .
P: A
▲
Da alle von A oder B ausgehenden Ableitungen eindeutig sind, ist G
genau dann mehrdeutig, wenn es ein Wort w ❃ L❼G ➁ gibt mit
S
▲
✟A✟
❻
w und S
✟B✟
❻
w.
Wie wir gesehen haben, ist dies genau dann der Fall, wenn I eine
PCP-Lösung hat.
❥
Ein Unentscheidbarkeitsresultat für DCSL
321
Das Leerheitsproblem für DLBAs
Gegeben: Ein DLBA M.
Gefragt: Ist L❼M ➁ ❣?
Satz
Das Leerheitsproblem für DLBAs ist co-RE-vollständig.
Beweis.
▲
▲
▲
Wir reduzieren PCP auf das Leerheitsproblem für DLBAs.
k
➂
Hierzu transformieren wir eine PCP-Instanz I ❽xy11 ...x
...yk in einen DLBA
M für die Sprache Ls ✾ Lt , wobei s ❼x1 , . . . , xk ➁ und t ❼y1 , . . . , yk ➁
ist (siehe Übungen).
Dann gilt I ❃⑦ PCP
✔ L❼M ➁ ❣
.
❥
Entscheidbare Probleme
322
Dagegen ist es nicht schwer,
▲
▲
für eine kontextfreie Grammatik G zu entscheiden, ob mindestens ein
Wort in G ableitbar ist (Leerheitsproblem für CFL), und
für eine kontextsensitive Grammatik G und ein Wort x zu entscheiden,
ob x in G ableitbar ist (Wortproblem für CSL).
Satz
▲
Das Leerheitsproblem für CFL ist entscheidbar.
▲
Das Wortproblem für CSL ist entscheidbar.
Beweis.
Siehe Übungen.
❥
323
Überblick der (Un-)Entscheidbarkeitsresultate
In folgender Tabelle fassen wir nochmals zusammen, wie schwierig die
betrachteten Entscheidungsprobleme für die verschiedenen Stufen der
Chomsky-Hierarchie sind.
Wort- Leerheits- Aus- Äquivalenz- Inklusions- Schnittproblem problem schöpfung problem
problem problem
x ❃L ? L ❣ ?
L Σ❻ ?
L1 L2 ?
L1 ❜ L2 L1 ✾ L2 ⑦ ❣ ?
REG
DCFL
CFL
DCSL
CSL
RE
a
ja
ja
ja
ja
ja
nein
ja
ja
ja
nein
nein
nein
ja
ja
nein
nein
nein
nein
ja
jaa
nein
nein
nein
nein
ja
nein
nein
nein
nein
nein
Bewiesen in 1997 von Géraud Sénizergues (Univ. Bordeaux).
ja
nein
nein
nein
nein
nein
Document
Kategorie
Gesundheitswesen
Seitenansichten
8
Dateigröße
308 KB
Tags
1/--Seiten
melden