Kann jemand die Frage Schritt für Schritt erklären?Automata Turing
Angenommen, Σ eine endliche Menge ist, und daß L1, L2 und L3 sind Turing akzeptable Teilmengen von Σ^*, das die folgenden Eigenschaften erfüllen: ∪ L1 L2 L3 = ∪ Σ^* ; L1 ∩ L2 = L2 ∩ L3 = L3 ∩ L1 = ∅. Zeigen Sie, dass L1, L2 und L3 alle rekursiv sein müssen.
Wir gegeben sind, dass:
L1 union L2 union L3 = E*
L1 intersect L2 = {}
L1 intersect L3 = {}
L2 intersect L3 = {}
L1 is acceptable/semidecidable/recursively enumerable/recognizable
L2 is acceptable/semidecidable/recursively enumerable/recognizable
L3 is acceptable/semidecidable/recursively enumerable/recognizable
Wir müssen zeigen, dass L1, L2 und L3 rejectable sind/entscheidbar/rekursive/co-erkennbar.
Können wir zeigen, dass eine Zeichenfolge nicht in L1 ist? Ja. Da die Vereinigung dieser drei Sprachen alle Zeichenfolgen enthält und sich keine zwei Sprachen überschneiden, wissen wir, dass jede Zeichenfolge, die sich nicht in L1 befindet, entweder in L2 oder in L3 ist. Da diese Sprachen akzeptierbar/semidezidierbar/rekursiv aufzählbar/erkennbar sind, haben wir TMs TM2 und TM3, die letztendlich Strings in L2 bzw. L3 akzeptieren/entscheiden/aufzählen/erkennen. Um zu erkennen, dass eine Zeichenkette nicht in L1 ist, können wir T2 und T3 ausführen lassen und sehen, ob einer die Zeichenkette jemals akzeptiert/entscheidet/aufzählt/erkennt, in welchem Fall wir wissen, dass L1 nicht muss.
Wir wissen jetzt, dass L1 sowohl akzeptabel/rekursiv aufzählbar/erkennbar und gleichzeitig ablehnbar // co-rekursiv aufzählbar/erkennbar ist. Sprachen wie diese sind entscheidbar/rekursiv.
Da L1, L2 und L3 willkürlich nummeriert wurden, muss jedes Ergebnis, das für L1 gilt, auch für L2 und L3 gelten, da wir diese anderen Sprachen genauso gut als L1 hätten betrachten können. Mit anderen Worten, das exakt gleiche Argument gilt, wenn Sie L1 entweder mit L2 oder L3 tauschen.
Daher ist jede der drei Sprachen entscheidbar/rekursiv.