Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

BuK > Semi-Entscheidbarkeit & Rekursive Aufzählbarkeit > Flashcards

Semi-Entscheidbarkeit & Rekursive Aufzählbarkeit Flashcards

1
Q

M erkennt L, wenn…

A

M jedes Wort aus L akzeptiert und kein Wort akzeptiert, das nicht in L enthalten ist.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

L heißt semi-entscheidbar, wenn…

A

eine TM existiert, die die Sprache L erkennt.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Das Halteproblem ist… (entscheidbar/nicht entscheidbar/semi-entscheidbar)

A

nicht entscheidbar, aber semi-entscheidbar.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Definition: Ein Aufzähler für eine Sprache L⊆Σ* ist…

A

eine Variante der TM mit einem angeschlossenen Drucker.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Der Drucker des Aufzählers ist..

A

ein zusätzliches Ausgabeband, auf dem sich der Kopf nur nach rechts bewegen kann und auf dem nur geschrieben wird.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Ein Aufzähler funktioniert so:

A
  • wird mit dem leerem Arbeitsband gestartet und gibt mit der Zeit alle Wörter in L auf dem Drucker aus
  • Die ausgegebene Wörter immer durch ein Trennzeichen separiert, das nicht in Σ enthalten ist
  • Der Aufzähler druckt ausschliesslich Wörter in L.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Definition: Wenn es für L einen Aufzähler gibt, so heißt L…

A

rekursiv aufzählbar.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

L ist rekursiv aufzählbar genau dann, wenn L … ist.

A

semi-entscheidbar

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Durchschnitt: Wenn L1 und L2 entscheidbar, dann L1 ∩ L2 ist …

A

entscheidbar

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Durchschnitt: Wenn L1 und L2 rekursiv aufzählbar, dann L1 ∩ L2 ist…

A

rekursiv aufzählbar

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Vereinigung: Wenn L1 und L2 entscheidbar, dann L1 ∪ L2 ist …

A

entscheidbar

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Wenn L1 und L2 rekursiv aufzählbar, dann L1 ∪ L2 ist …

A

rekursiv aufzählbar

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Wenn sowohl L⊆Σ* als auch ihr Komplement not L := Σ* \ L rekursiv aufzählbar, so ist L …

A

entscheidbar

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Wenn L entscheidbar, ihr Komplement not L ist..

A

entscheidbar

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Wenn L rekursiv aufzählbar, ihr Komplement not L ist nicht unbedingt..

A

rekursiv aufzählbar

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Graphzusammenhang, Hamiltonkreis sind … Sprachen, wobei L … und not L ist ….

A

entscheidbare, rekursiv aufzählbar, rekursiv aufzählbar

17
Q

Beispiele von entscheidbare Sprachen, wo sowohl L als auch not L rekursiv aufzählbar

A

Graphzusammenhang, Hamiltonkreis

18
Q

H, H_epsilon, not D sind… Sprachen, mit ….. Komplement

A

rekursiv aufzählbar, nicht rekursiv aufzählbarem

19
Q

not H, not H_epsilon, D sind… Sprachen, mit ….. Komplement

A

nicht rekursiv aufzählbare, rekursiv aufzählbarem

20
Q

Beispiele von rekursiv aufzählbar Sprachen mit nicht rekursiv aufzählbarem Komplement

A

H, H_epsilon, not D

21
Q

Beispiele von nicht rekursiv aufzählbar Sprachen mit rekursiv aufzählbarem Komplement

A

not H, not H_epsilon, D

22
Q

Unentscheidbare Sprachen mit unentscheidbarem Komplement

A

H_tot, not H_tot

23
Q

H_tot ist eine … Sprache mit … Komplement

A

nicht rekursiv (aufzählbare), nicht rekursiv (aufzählbarem)

24
Q

Definition Reduktion zweier Sprachen

A

Seien L1 und L2 zwei Sprachen über einem Alphabet Σ. Dann heißt L1 auf L2 reduzierbar, wenn es eine berechenbare Funktion f : Σ* -> Σ* existiert, so dass für alle x ϵ Σ* gilt: x ϵ L1 <=> f(x) ϵ L2

25
Q

Seien L1 und L2 zwei Sprachen über einem Alphabet Σ. Wenn es eine berechenbare Funktion f : Σ* -> Σ* existiert, so dass für alle x ϵ Σ* gilt: x ϵ L1 <=> f(x) ϵ L2 gilt, dann ist L1 auf L2 ….

A

reduzierbar

26
Q

Definition Reduktion

A

Ein Algorithmus, der die Instanzen eines Startproblems als Spezialfälle eines Zielproblems formuliert.

27
Q

Wenn L1 ≤ L2 und L2 rekursiv aufzählbar, so ist L1…

A

rekursiv aufzählbar

28
Q

Wenn L1 ≤ L2 und L1 nicht rekursiv aufzählbar, so ist L2…

A

nicht rekursiv aufzählbar

29
Q

Definition Totales Halteproblem

A

{Gödelnummer von M | M hält auf jeder Eingabe}

30
Q

Wenn eine Sprache ist unentscheidbar, aber rekursiv aufzählbar, dann ihr Komplement ist…

A

nicht rekursiv aufzählbar

31
Q

Htot ist…

A

nicht rekursiv aufzählbar

32
Q

Not Htot ist…

A

nicht rekursiv aufzählbar

33
Q

Aus A ≤ not A folgt dass…

A

Not A ≤ A

34
Q

Wenn L1 ≤ L2 und L2 entscheidbar, dann ist L1…

A

L1 entscheidbar

35
Q

Wenn L1 ≤ L2 und L1 nicht entscheidbar, dann L2 ist…

A

Nicht entscheidbar

BuK (12 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions