Brainscape's Knowledge GenomeTM

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


See full index

SMK2 > Technische INF > Flashcards

Technische INF Flashcards

1
Q

Jede endliche Menge ist abzählbar

A

richtig

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

Jede unendliche Menge ist abzählbar

A

falsch

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

Jede unedliche Menge ist überabzählbar

A

falsch

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

Die Menge aller Algorithmen ist abzählbar

A

richtig

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

Die Menge aller Algorithmen ist überabzählbar

A

falsch

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

Alle rechtslinearen Grammatiken sind auch kontextfrei.

A

richtig

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

Alle beschränkten Grammatiken sind auch kontextsensitiv

A

falsch

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

Ein Wort besteht immer nur aus endlich vielen Buchstaben

A

richtig

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

Ein Wort besteht nicht immer nur aus endlich vielen
Buchstaben

A

falsch

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

Eine Sprache besteht immer nur aus endlich vielen
Wörtern

A

falsch

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

Jede Grammatik definiert genau eine Sprache

A

richtig

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

Für jede Sprache L gibt es genau eine Grammatik, die
L definiert

A

falsch

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

Für jede Sprache L gibt es nicht genau eine Grammatik, die L definier

A

richtig

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

Jeder DEA hat genau einen Endzustand

A

falsch

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

NEA und DEA sind gleichmächtig

A

richtig

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

Ist L in P und L NP-hart, dann ist P=NP

A

richtig

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

Die Vereinigung zweier entscheidbarer Mengen ist
entscheidbar

A

richtig

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

Die Vereinigung zweier nicht entscheidbarer Mengen
ist entscheidbar

A

falsch

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

Ist eine Menge und ihr Komplement rekursiv
aufzählbar, dann ist die Menge entscheidbar

A

richtig

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

Ist eine Menge und ihr Komplement rekursiv
aufzählbar, dann ist die Menge nicht entscheidbar

A

falsch

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

Jeder DEA hat genau einen Startzustand

A

richtig

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

Jede von einem Kellerautomaten akzeptierte Sprache
wird auch von einem nichtdeterminischten Kellerautomaten akzpetiert

A

richtig

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

Jede von einem Kellerautomaten akzeptierte Sprache
wird auch von einem determinischten Kellerautomaten akzpetiert

A

falsch

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

Jede loop-berechenbare Funktion ist total

A

richtig

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

Typ 0- Sprachen sind unter Komplementblidung
abgeschlossen

A

falsch

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

Typ 0- Sprachen sind unter Komplementblidung nicht
abgeschlossen

A

richtig

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

Jede Sprache enthält das leere Wort

A

falsch

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

Jede Sprache kann das leere Wort enthalten

A

richtig

27
Q

Die Anzahl der Äquivalenzenklassen einer Nerode-Relation ist bei regulären Sprachen endlich

A

richtig

28
Q

AB->C ist eine Produktion vom Typ 0

A

richtig

29
Q

A->BC ist eine Produktion vom Typ 0

A

falsch

30
Q

Typ-1-Sprachen werden von linear beschränkten
nichtdeterministischen Turingmaschinen akzeptiert

A

richtig

31
Q

Das Rucksackproblem mit Objektgewichten aus
{1,2,…,10} ist in P

A

richtig

32
Q

Die Grammatik, deren Regelmenge als einzige Regel S
’ µ enth¨alt, erzeugt dieselbe Sprache wie die Grammatik
mit leerer Regelmenge.

A

falsch

33
Q

Um zu beweisen, dass eine Sprache L nicht regul¨ar ist, genugt es, eine kontextfreie Grammatik für L
anzugeben.

A

falsch

34
Q

Um zu beweisen, dass eine Sprache L nicht regul¨ar
ist, genugt es, zu zeigen, dass das Pumping-Lemma
fur ¨ L nicht gilt.

A

richtig

35
Q

Immer wenn es in einer kontextfreien Grammatik zu
einer Variablen A keine Regel gibt, auf deren linker
Seite A steht (die also die Form A ’ . . . hat), dann ist
A nicht co-erreichbar und damit nutzlos.

A

richtig

36
Q

Wenn eine Sprache L regul¨ar ist, dann ist ihr Komplement L = (£ \ L) regul¨ar

A

richtig

37
Q

Wenn die Sprachen L1 und L2 regul¨ar sind, dann ist
die Sprache L1 ) L2 regul¨ar

A

richtig

38
Q

Wenn eine Sprache L regul¨ar ist, dann ist jede
Sprache L 0‚ L regul¨ar.

A

falsch

39
Q

Gegeben sei eine kontextfreie Grammatik. Zu jeder Ableitung mit den Regeln der Grammatik gibt es
genau einen entsprechenden Ableitungsbaum

A

richtig

40
Q

Gegeben sei eine kontextfreie Grammatik. Zu jedem
Ableitungsbaum gibt es genau eine entsprechende
Ableitung mit den Regeln der Grammatik.

A

falsch

41
Q

Gegeben sei eine kontextfreie Grammatik. Zu jedem in
der Grammatik ableitbaren Wort gibt es (mindestens)
einen entsprechenden Ableitungsbaum.

A

richtig

42
Q

Aus einem Ableitungsbaum kann man eine
Linksableitung ablesen

A

richtig

43
Q

Zu jeder mehrdeutigen kontextfreien Grammatik gibt
es eine ¨aquivalente eindeutige kontextfreie Grammatik

A

falsch

44
Q

Das Komplement jeder kontextfreien Sprache ist kontextfrei.

A

richtig

45
Q

Wenn L1 und L2 kontextfrei sind, dann ist auch L1)L2
kontextfrei.

A

richtig

46
Q

Jede unendliche Sprache ist unentscheidbar

A

falsch

47
Q

Es ist bekannt und einfach zu beweisen, dass PSPACE
!= NP

A

falsch

48
Q

Es ist bekannt und einfach zu beweisen, dass P †
PSPACE

A

richtig

49
Q

Zu jeder Sprache L, die von einem PDA akzeptiert wird,
gibt es eine NTM, die L akzeptiert

A

richtig

50
Q

Zu jeder Sprache L, die von einer DTM akzeptiert wird,
gibt es einen PDA, der L akzeptiert.

A

falsch

51
Q

Eine universelle Turing-Maschine kann sich selbst
simulieren.

A

richtig

52
Q

Jede akzeptierbare Sprache ist entscheidbar

A

falsch

53
Q

Jede entscheidbare Sprache ist rekursiv aufz¨ahlbar

A

richtig

54
Q

Das Komplement einer entscheidbaren Sprache ist
entscheidbar.

A

richtig

55
Q

AB->BC ist eine Produktion in CNF

A

falsch

56
Q

Eine NEA kann spontane Übergänge haben

A

richtig

57
Q

{a,b}^+ kann das leere Wort enthalten

A

falsch

58
Q

Falls ein Problem in EXPTIME ist, kann es NP-vollständig sein

A

falsch

59
Q

Jede entscheidbare Sprache ist akzeptierba

A

richtig

60
Q

Das Komplement jeder rekursiv aufzählbaren Sprache
isr rekkursiv aufzählbar

A

falsch

61
Q

Jede endliche Sprache ist akzeptierbar

A

richtig

62
Q

Jede unentschiedbare Sprache ist unendlich

A

richtig

63
Q

Es gibt eine Turing Maschine, die für alle Java-Programmme P entscheiden kann, ob P, wenn man es
laufen lässt, eine NullPointerException werfen wird

A

falsch

64
Q

Es ist bekannt und einfach zu beweisen, dass P !=NP

A

falsch

65
Q

Das Erfüllbarkeitsproblem der Aussagenlogik ist
NP-hart

A

richtig

66
Q

Jedes NP-harte Problem liegt in NP

A

falsch

SMK2 (2 decks)

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