Lösung 09

Dateiinhalt

Musterloesung Blatt 9
---------------------

H-18:

1. unloesbar. 
Jede Loesung muesste mit 1 beginnen, dann muesste 
aber das naechste Paar in der linken Komponente
mit 11 starten.  

2. Eine Loesung ist  1,3,2,3

3. unloesbar. 
Jede Loesung muesste mit 1 beginnen

011
01111

Dann kann der zweite Index nur 3 sein:

0 1 1|1 1 0|
0 1 1 1 1|0 0|

Das dritte Paar muss links mit 0 beginnen, 
aber bei keinem der in Frage kommenden Paare 
passt dann der zweite Buchstabe mit dem ersten 
rechts zusammen.


H-19:

Wir reduzieren PKP auf PALINDROM.

Sei (v1,w1) , ... , (vn,wn) Instanz I des PKP.

Wir definieren eine Grammatik G(I) mit Variablen 
{S,A1,...,An}, Startsymbol S, und den Produktionen:

S -> A1  ,  ...  , S -> An
Ai -> viR Aj wi  und  Ai -> viR # wi   fuer alle i,j

Aus G sind genau die Woerter der Form 

   vikR ... vi1R # wi1 ... wik    

fuer eine Folge von Indizes i1 , ... , ik ableitbar. 

Ist die Indexfolge eine Loesung fuer I, so ist das entsprechende
Wort ein Palindrom, das in G(I) ableitbar ist.  

Umgekehrt, ist ein solches Wort ein Palindrom, dann muss 
vi1 ... vik = wi1 ... wik sein, also die Indexfolge eine 
Loesung fuer I. 

Also enthaelt L(G(I)) ein Palindrom, genau dann wenn I loesbar
ist. Die Abbildung I |-> G(I) reduziert also das PKP auf 
PALINDROM, daher ist PALINDROM unentscheidbar.