Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

Formale Systeme > ForSy > Flashcards

ForSy Flashcards

1
Q

Präfix

A

Vorsilbe

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

Suffixe

A

Endsilbe

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

Infix

A

Teilwort in der Mitte

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

Formale Sprache

A

Menge von Wörtern über einem Alphabet

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

Kleinste Sprache

A

Leere Sprache

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

Größte Sprache

A

Sprache aller Wörter

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

Wie viele Wörter gibt es?

A

Abzählbar viele Wörter über jedem Alphabet, jede Sprache ist endlich oder abzählbar unendlich

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

Wie viele Sprachen gibt es ?

A

Überabzählbar viele Sprachen über jedem beliebigen Alphabet

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

Terminalsymbole

A

Elemente vom Alphabet

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

Nichtterminalsymbole

A

Variablen

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

Sprache einer Grammatik

A

Allen Wörtern über einem Alphabet, die man von S ableiten kann

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

Typ–0 Grammatik

A

Unbeschränkt

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

Typ–1 Grammatik kontextsenstiv

A

W–>V |w|<= |v|

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

Typ–2 kontextfreie Grammatik

A

A–>v A ist eine Variable

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

Typ–3 Grammatik regulär

A

Rechte Seite ein Terminalsymbol und maximal ein weiters Nichtterminalsymbol, Nichtterminalsymbol muss immer auf einer Seite stehen

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

Wortproblem

A

Ist ein Wort in einer Sprache

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

Deterministisch endlicher Automat

A

M=(Zustandsmenge, Alphabet, Übergangsfunktion, Startzustand, Endzustand)

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

Sprache endlicher Automaten

A

Reguläre Sprachen

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

NFA

A

DFA mit Menge von Startzuständen und Endzuständen

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

NFA, Epsilon-NFA, NFA-Wort (Aussagkraft)

A

gleiche Aussagekraft

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

Abschlusseigenschaften: Vereinigung

A

Automaten nebeneinander
alle Sachen der Tupel vereinigen
neue Übergangsfunktion die beide Übergangsfunktionen enthält

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

Abschlusseigenschaften: Schnitt

A

alle Kombinationen von Zuständen
Startzustände: Kombination von zwei Startzuständen
Endzustände: Kombinationen von zwei Endzuständen
Übergänge: nur wenn von beiden Zuständen das Symbol eingelesen werden kann

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

Abschlusseigenschaften: Komplement

A

alles gleich
Endzustände: alle Zustände die im alten Automaten keine Endzustände sind

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

Abschlusseigenschaften: Konkatenation

A

Startzustand: Startzustand des ersten Automaten
Endzustand: Endzustand des zweiten Automaten
Übergänge: alle Übergänge aus alten Automaten, Epsilon Übergang vom alten Endzustand des ersten Automaten zum Startzustand des zweiten Automaten

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

reguläre Sprachen

A

sind endlich, genügt endlichen Automaten anzugeben, regulären Ausdruck, Typ-3-Grammatik, Pumping-Lemma (notwendiges Kriterium)

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

Kleenes Theorem

A

Eine Sprache wird genau dann von einem regulären Ausdruck beschrieben, wenn sie von einem endlichen Automaten erkannt wird

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

Umwandlung NFA -> regulärer Ausdruck

A
  1. entfernen unnötiger Zustände
  2. Gleichungssystem
  3. lösen durch einsetzten, Arden
  4. angeben Ausdruck
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

Äquivalenz von Zuständen

A

Zwei Zustände sind gleichwertig wenn man ausgehend von ihnen die gleiche Sprache akzeptiert

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

Reduktion von Automaten

A
  1. entfernen aller unerreichbaren Zustände
  2. Quotientenautomat
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

Nerode-Rechtskongruenz

A

zwei Wörter sind äquivalent wenn sie al Präfixe vor ein Wort gehängt werden können und das neue Wort immer noch Teil der Sprache ist

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

Satz von Myhill und Nerode

A

Eine Sprache ist genau dann regulär, wenn die Nerode-Rechtskongruenz endlich viele Äquivalenzklassen hat

32
Q

Nicht-reguläre Sprachen

A
  • unendlich viele Äquivalezklassen der Nerode-Rechtskongruenz
  • Sprache wird von einem Kellerautomaten akzeptiert
33
Q

Chomsky Normalform

A

alle Regeln der Form: A->AB oder A->c

34
Q

Abschlusseigenschaften Typ-2-Sprachen

A

Vereinigung, Konkatenation, Kleene-Stern

35
Q

Kellerautomat

A

(Menge von Zustände, Eingabe Alphabet, Kelleralphabet, Übergangsfunktion, Startzustände, Endzustände)

36
Q

Deterministische Kellerautomaten

A

M =(endliche Menge von Zuständen, Eingabealphabet, Kelleralphabet, Übergangsfunktion, Startzustand, Endzustände)
Übergangsfunktion: (q,a,A), (q,a,Eps), (q,Eps,A), (q,Eps,Eps)
erkennen deterministisch kontextfreie Sprachen

37
Q

deterministisch kontextfreie Sprache

A

erkannt durch DPDA
echte Untermenge der kontextfreien Sprachen
unter Komplement abgeschlossen

38
Q

Turing-Mächtigkeit

A

TM ist das mächtigste Berechnungsmodelle, was nicht TM berechenbar ist gilt als unberechenbar (Programmiersprachen etc.)

39
Q

Konjunktion

40
Q

Disjunktion

41
Q

Modell

A

w ist ein Modell von F, wenn w F erfüllt

42
Q

logische Konsequenz

A

F erfüllt G, wenn jedes Modell von F auch ein Modell von G ist

43
Q

Logische Konsequenz allgemeingültige Formel

A

Jede allgemeingültige Formel ist logische Konsequenz von allen anderen Formeln

44
Q

Logische Konsequenz unerfüllbaren Formel

A

Eine unerfüllbaren Formeln hat jede andere Formel als logische Konsequenz

45
Q

Semantische Äquivalenz

A

Zwei Formelmengen sind semantisch äquivalent wenn sie die selben Modelle haben
(alle Tautologien und unerfüllbaren Formel sind äquivalent)

46
Q

Negationsform

A

besteht nur aus UND, ODER und NEGATIONS
-> Negation nur direkt vor Atomen

47
Q

Konjunktive Normalform

A

Konjunktion von Disjunktionstermen
-> erfüllbar, wenn alle Klauseln erfüllbar

48
Q

Disjunktive Normalform

A

Disjunktion von Konjunktionstermen
-> erfüllbar, wenn eins der Monome erfüllbar

49
Q

Horn-Formel

A

KNF, pro Klausel höchstens ein nichtnegiertes Literal

50
Q

SAT

A

-Erfüllbarkeit von aussagenlogischen Formeln
-entscheidbar
-LBA -> Typ-1
-speicherbeschränkt
-NP
-nachweis-polynomiell
-NP-vollständig
-DTIME(2^n)
DSPACE(n)

51
Q

O(f)-zeitbeschränkt

A

Tm hält bestimmter Anzahl von Schritten in Abhängigkeit zu der Eingabe

52
Q

O(f)-speicherbeschränkt

A

TM verwendet nur eine bestimmte Anzahl von Speicherzellen in Abhängigkeit von der Eingabe (LBA)

53
Q

DTIME(f(n))

A

Klasse aller Sprachen, welche durch zeitbeschränkt TM entschieden werden können

54
Q

DSPACE(f(n))

A

Klasse aller Sprachen die von speicherbeschränkten TM entschieden werden können

55
Q

Komplexitätsklassen

A

P, Exp, L, PSpace

56
Q

P

A

Polynomielle Zeit
DTime(n^d)

57
Q

Exp

A

Exponentielle Zeit
DTime(2^(n^d))

58
Q

L

A

Logarithmischer Speicher
DSpace(log n)

59
Q

PSpace

A

Polynomieller Speicher
DSpace (n^d)

60
Q

Beziehung Komplexitätsklassen

A

L⊆ P ⊆ PSpace ⊆ Exp
-> P ⊊ Exp
-> L ⊊ PSpace

61
Q

O(f)-zeitbeschränkt (Nichtdeterministische TM)

A

jeder Berechnungspfad hält nach einer Anzahl von Schritten in Abhängigkeit von der Eingabe

61
Q

NSpace(f(n))

A

Klasse aller Sprachen, welche durch eine speicherbeschränkte NTM entschieden werden können

61
Q

O(f)-speicherbeschränkt (Nichtdeterministische TM)

A

jeder Berechnungspfad verwendet nur eine bestimmte Anzahl von Speicherzellen in Abhängigkeit von der Eingabe

62
Q

NTime(f(n))

A

Klasse aller Sprachen, welche durch eine O(f)-zeitbeschränkte NTM entschieden werden können

63
Q

Nichtdeterministische Komplexitätsklassen

A

NP, NExp, NL, NPSpace

64
Q

NP

A

nichtdeterministische Polynomielle Zeit
NTime(n^d)

65
Q

NExp

A

nichtdeterministische Exponentielle Zeit
NTime(2^(n^d))

66
Q

NL

A

nichtdeterministischer polynomieller Speicher
NSpace (log n)

67
Q

NPSpace

A

nichtdeterministischer polynomieller Speicher NSpace (n^d)

68
Q

Beziehung aller Komplexitätsklassen

A

L ⊆ NL ⊆ P ⊆ NP ⊆ PSpace = NPSpace ⊆ Exp ⊆ NExp

69
Q

Polynomieller Verifikator

A

Zertifikat = Lösung
Verifikator = prüft Lösung
TM die Lösungen prüfen

70
Q

Nachweis-polynomiell

A

Sprache hat einen polynomiellen Verifikator

71
Q

NP-schwer

A

wenn jede Sprache in NP darauf reduzierbar ist

72
Q

NP-vollständig

A

NP-schwer, liegt in NP

73
Q

P-schwer

A

wenn jede Sprachein P mit logarithmischen Speicherbedarf darauf reduzierbar ist

Formale Systeme (2 decks)

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