---
# System prepended metadata

title: TGI Hausaufgabe 5

---

# TGI Hausaufgabe 5

##### <u>Aufgabe 1</u>

Geben sie alle Konfigurationsfolgen von $M$ für das Wort $010$ an.

1. $q_0, (q_1\dots)$
2. $q_0, (q_1* 2+), q_{rej}$
3. $q_0, (q_2*(1-3)), (q_1\dots)$
4. $q_0, (q_2*(1-3)), (q_1*1+), q_{rej}$
5. $q_0, (q_2*2), q_3, q_{acc}$
6. $q_0, (q_2*2), q_3, (q_1\dots)$
7. $q_0, (q_2*2), q_3, (q_1* 1+),q_{rej}$


##### <u>Aufgabe 2</u>

Unser Automat besteht aus folgenden Teilen:
1. Niederschreiber für X und Y in korrekter Form.
2. Addierer für X.
3. Subtrahierer für Y.
4. Addierer für Y.
5. Kopierer, der X auf Y kopiert.
6. Zurückspuler für X und Y.

Der Automat initialisiert X und Y auf 0.
Danach gibt es einen Loop:
X und Y werden in korrekter Form nieder geschrieben.
Auf X wird 1 addiert.
Falls Y gleich 0 ist wird Y gleich X+1 und X=0 gesetzt.
Sonst wird von Y 1 subtrahiert.
Danach beginnt der Loop von Neuem.

Kodierungsfunktion:
$0\longrightarrow0000$
$1\longrightarrow0001$
$2\longrightarrow0010$
$3\longrightarrow0011$
$4\longrightarrow0100$
$5\longrightarrow0101$
$6\longrightarrow0110$
$7\longrightarrow0111$
$8\longrightarrow1000$
$9\longrightarrow1001$
$+\longrightarrow1111$

##### <u>Aufgabe 3</u>

Zuerst eliminieren wir alle Transitionen, die das Nichtterminalzeichen in ihrer Startmenge in ihrer Zielmenge haben.

Wir suchen uns erst alle Transitionen heraus, die nur in Terminalzeichen enden.

Fall S nicht enthalten ist, suchen wir uns alle Transitionen, die nur in deren Nichtterminalzeichen oder Terminalzeichen enden.

Falls S nicht enthalten ist wiederholen wir diesen Schritt, bis nichts mehr hinzugefügt wird.

##### <u>Aufgabe 4</u>

$L_1$ ist Turing-Entscheidbar.
$L_2$ ist Turing-Erkennbar.

a) Richtig, denn $L_1$ ist Teilmenge von $L_2$, damit ist der Schnitt gleich $L_1$ und damit auch Turing-Entscheidbar.

b) Richtig, denn jede Turing-Entscheidbare Sprache ist auch Turing-Erkennbar.

c) Falsch, denn das Komplement von $L_1$ und $L_2$ enthält auch nur Co-Turing-Erkennbare Sprachen, und auch solche, die sich für gar keine der 3 Eigenschaften qualifizieren.

d) Falsch, denn jede Turing-Erkennbare Sprache (so wie $L_1\cap L_2$) ist sowohl Turing-Erkennbar, als auch Co-Turing-Erkennbar.