Lösung 09
loesung09.txt
—
Plain Text,
1 KB (1383 bytes)
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.
Artikelaktionen