cards-deck: university::theo_complexity

Komplement einer Sprache :

specific part of [[theo2_SprachenUnendlichkeit]] broad part of [[112.00_anchor_overview]]

Definition des Komplements einer Sprache :

Sei $L$ eine Sprache über $\Sigma$. Wir definieren die Komplement-Sprache $L^C$ als folgende Menge: welche Eigenschaft hat diese Menge, wie können wir uns das visuell vorstellen? #card $L^C:=\{w\in {\Sigma }^{\ast }|w\notin L\}$ eine AlternativeNotation : $L^C=\bar{L}$

also alle Wörter sind in der Sprache enthalten, die sich nicht in der normalen Sprache $L$ befinden! ![[Pasted image 20230516151925.png]] ^1686523705743

Es gilt: $L\in R⟹L^C\in R$ was bedeutet das, was können wir daraus folgern? #card Sei $M$ eine TM, die L entscheidet. Insbesondere stoppt sie auf allen Eingaben. Wir definieren nun eine TM $M_c$ bei der der akzeptierende und verwerfende Zustand von $M$ vertauscht wird. Diese TM entscheidet dann also $L^C$, also das Komplement. Weiter können wir für einzelne Wörter betrachten: $w\in L⟹M$ akzeptiert $w⟹M_C$ verwirft $w⟹w\notin L(M_C)$ und für alle Wörter, die nicht enthalten sind: $w\notin L⟹$ verwirft $w⟹M_C$ akzeptiert $w⟹w\in L(M_C)$ ^1686523705754

Definition co$RE$ :

Folgend definieren wir die Menge co$RE$ als: :: co$RE:=\{L|L^C\in RE\}$ oder auch $L\in coRE:⟺L^C\in RE$ ^1686523705759

Folglich ist interessant, in welchem Verhältnis sich RE und coRE befinden, also wie die beiden Mengen zueinander stehen: betrachte es visuell. Was können wir nun über eine Sprache $L\in R$ aussagen? #card ![[Pasted image 20230516152550.png]] $L\in R⟹L\in RE\cap coRE$ Wir sagen also, dass sich $R$ in der Schnittmenge der Komplemente von $RE\wedge coRE$ befindet. ^1686523705764

Beweis für $L\in R⟹L\in RE\cap coRE$ : #card $L\in R⟹L\in RE$ – ist klar, denn $R\subset RE$. Weiterhin folgt dann auch: $L\in R⟹L^C\in R\subset RE$ das Komplement coRE : bezeichnet eine Menge von Sprachen, deren Komplement in $RE$ ist.. Aus dieser Betrachtung können sich die beiden Mengen überschneiden, weil die Menge der Sprachen selbst schon R ist. $L\in R⟶L^c\in R$ ^1686523705769

Es folgt ein Satz aus dieser Aussage :

Satz von Sprachen L und ihrer Zugehörigkeit :

$L\in R⟺L\in RE\wedge L\in coRE$ was sagt uns dieser Term? Wie können wir das beweisen? #card Den Beweis können wir zum einen aus der obigen Aussage ziehen! und weiterhin dann $⟸$:

• Sei$M$ eine TM für L und $M_C$ eine TM für $L^C$.
• wir definieren eine neue TM $M^{\sim }$ folgend:
  • Lasse M und $M_C$ parallel auf Eingabe $w$ laufen
  • Falls $M$ akzeptiert, dann soll $M^{\sim }$ akzeptieren
  • Falls $M_c$ akzeptiert, dann soll $M^{\sim }$ verwerfen. Daraus folgt dann: $w\in L⟹M$ akzeptiert $⟹M^{\sim }$ akzeptiert und $w\notin L⟹w\in L^C⟹M_C$ akzeptiert $⟹M^{\sim }$ verwirft. ![[Pasted image 20230516153141.png]] ^1686523705774

Komplemente semi-entscheidbarer Sprachen nicht zwingend semi-entscheidbar :

Wir möchten jetzt mit Komplementen von Sprachen argumentieren und können einen Satz folgern: $L\in RE/⟹L^C\in RE$ was besagt diese Aussage? Warum tut sie das? #card Ein direkter Beweis dieser Aussage ist relativ schwierig, denn wir können nicht einfach die TM von L invertieren und sagen, dass das dann nicht immer $L^C$ erkennt; es könnte ja eine andere TM geben, die es kann, oder?. Aber wir wissen: $L\in RE$ und $L^C\in RE⟹L\in R$ Haben aber gesehen, dass es Sprachen in $RE\setminus R$ gibt. Für diese muss dann folglich $L^C\notin RE$ gelten, also $L\in coRE$. ^1686523705779

Wir haben zuvor bereits $A_{T}M$ angeschaut [[theo2_SprachenNichtRekursiv#Definition $A_{TM}$ :]] und jetzt betrachten wir das Komplement dieser Menge!

$\overline{A_{TM}}$ ist nicht semi-entscheidbar :

Also : $\overline{A_{TM}}\notin RE$ warum? #card Wir haben zuvor schon betrachtet, dass : $L\in RE\wedge K\in coRE⟹L\in R$. Wir wissen, dass $A_{TM}\in RE$ und $A_{TM}\in R$ Also muss $A_{TM}/coRE$ sein, also ferner $\overline{A_{TM}}\notin RE$ ^1686523705784

Als Diagram können wir es folglich darstellen: #card ![[Pasted image 20230516154250.png]] oder als Menge : $\overline{A_{TM}}=\{<M,w>|M\text{akzeptiert w nicht(verwirft oder stopp nicht)}\}$ Generell ist die definierte Sprache $\overline{A_{TM}}$ ähnlich zu der vorher beschriebenen Diagonalsprache, wo wir auch schon herausgefunden hatten, dass diese nicht in $RE$ ist. ^1686523705789

Beweisen der Aussage wie? #card
Diese hier ist gleich, jedoch wird es unter Anwendung der Komplementbildung bewiesen! ![[Pasted image 20230516154532.png]] Beachte dabei die Notation : $\overline{A_{TM}}\in coRE⟹\overline{\stackrel{ˉ}{A_{TM}}}=A_{TM}\in RE$ ^1686523705794