Brainscape's Knowledge GenomeTM

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


See full index

Berechenbarkeit und Komplexität > Einführung > Flashcards

Einführung Flashcards

1
Q

DFA - Definition

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

delta-hut Funktion für DFA - Definiton

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

DFA - akzeptieren eines Wortes

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

DFA - Beispielautomat

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

DFA - Zustandsgraph

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

Gibt es einen DFA zur Erkennung folgernder Sprache?

A

Ja

Letztes Zeichen muss eine 0 sein.

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

Gibt es einen DFA zur Erkennung folgernder Sprache?

A

Ja

Sprache enthält nur 1001 Wörter. Jede endliche Sprache ist regulär.

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

Gibt es einen DFA zur Erkennung folgernder Sprache?

A

Nein

Mit endlich vielen Zuständen können wir uns nicht “merken” wieviele a’s wir schon gelesen haben. Erkennung mit Kellerautomat möglich.

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

Gibt es einen DFA zur Erkennung folgernder Sprache?

A

Ja

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

Gibt es einen DFA zur Erkennung folgernder Sprache?

A

Ja

Müssen uns nur “merken” welche Buchstaben noch folgen dürfen.

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

Gibt es einen DFA zur Erkennung folgernder Sprache?

A

Nein

Mit endlcih vielen Zuständen können wir und nicht “merken” wieviele a’s oder b’s wir schon gelesen haben. Erkennung mit Kellerautomaten möglich

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

Gibt es einen DFA zur Erkennung folgernder Sprache?

A

Nein

Mit endlich vielen Zuständen können wir uns nicht “merken” wieviele a’s oder c’s wir schon glesen haben. Erkennung mit Kellerautomaten möglich.

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

Turing-Maschine - Definition

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

Interpretation von:

Bei einer Turingmaschine

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

Konfiguration einer TM - Definition

A

“Momentaufnahme” der TM zu einem bestimmten Zeitpunkt bei der Abarbeitung einer Eingabe.

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

Startkonfiguration einer TM - Definiton

A
17
Q

haltende Konfiguration - Definiton

Bei einer Turing-Maschine

A

k ist eine Konfiguration einer TM

18
Q

akzeptierende Konfiguration - Definition

Bei einer Turing-Maschien

A

k ist eine Konfiguration einer TM

19
Q

Mehrer Schritte bei einer Turing-Maschine auf einmal

A
20
Q

TM - Beispiel

A
21
Q

TM - Zustandsgraph

A
22
Q

TM hält auf Wort w - Definition

A
23
Q

TM akzeptiert Wort w - Definiton

A
23
Q

M akzeptiert Sprache T(M) - Defintion

A
24
Q

Abschlusseigenschaften einer TM

A

Sprachen L und L’ werden akzeptiert von TM M und M’:
* L geschnitten L’: kann von einer TM dargestellt werden.
* L vereinigt L’: kann von einer TM dargestellt werden.
* L \ L’: kann nicht von einer TM dargestellt werden.

Berechenbarkeit und Komplexität (15 decks)

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