Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

Formale Systeme > ForSy > Flashcards

ForSy Flashcards

(76 cards)

Start Studying
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
reguläre Sprachen
sind endlich, genügt endlichen Automaten anzugeben, regulären Ausdruck, Typ-3-Grammatik, Pumping-Lemma (notwendiges Kriterium)
26
Kleenes Theorem
Eine Sprache wird genau dann von einem regulären Ausdruck beschrieben, wenn sie von einem endlichen Automaten erkannt wird
27
Umwandlung NFA -> regulärer Ausdruck
1. entfernen unnötiger Zustände 2. Gleichungssystem 3. lösen durch einsetzten, Arden 4. angeben Ausdruck
28
Äquivalenz von Zuständen
Zwei Zustände sind gleichwertig wenn man ausgehend von ihnen die gleiche Sprache akzeptiert
29
Reduktion von Automaten
1. entfernen aller unerreichbaren Zustände 2. Quotientenautomat
30
Nerode-Rechtskongruenz
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
31
Satz von Myhill und Nerode
Eine Sprache ist genau dann regulär, wenn die Nerode-Rechtskongruenz endlich viele Äquivalenzklassen hat
32
Nicht-reguläre Sprachen
- unendlich viele Äquivalezklassen der Nerode-Rechtskongruenz - Sprache wird von einem Kellerautomaten akzeptiert
33
Chomsky Normalform
alle Regeln der Form: A->AB oder A->c
34
Abschlusseigenschaften Typ-2-Sprachen
Vereinigung, Konkatenation, Kleene-Stern
35
Kellerautomat
(Menge von Zustände, Eingabe Alphabet, Kelleralphabet, Übergangsfunktion, Startzustände, Endzustände)
36
Deterministische Kellerautomaten
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
deterministisch kontextfreie Sprache
erkannt durch DPDA echte Untermenge der kontextfreien Sprachen unter Komplement abgeschlossen
38
Turing-Mächtigkeit
TM ist das mächtigste Berechnungsmodelle, was nicht TM berechenbar ist gilt als unberechenbar (Programmiersprachen etc.)
39
Konjunktion
Und ^
40
Disjunktion
Oder ∨
41
Modell
w ist ein Modell von F, wenn w F erfüllt
42
logische Konsequenz
F erfüllt G, wenn jedes Modell von F auch ein Modell von G ist
43
Logische Konsequenz allgemeingültige Formel
Jede allgemeingültige Formel ist logische Konsequenz von allen anderen Formeln
44
Logische Konsequenz unerfüllbaren Formel
Eine unerfüllbaren Formeln hat jede andere Formel als logische Konsequenz
45
Semantische Äquivalenz
Zwei Formelmengen sind semantisch äquivalent wenn sie die selben Modelle haben (alle Tautologien und unerfüllbaren Formel sind äquivalent)
46
Negationsform
besteht nur aus UND, ODER und NEGATIONS -> Negation nur direkt vor Atomen
47
Konjunktive Normalform
Konjunktion von Disjunktionstermen -> erfüllbar, wenn alle Klauseln erfüllbar
48
Disjunktive Normalform
Disjunktion von Konjunktionstermen -> erfüllbar, wenn eins der Monome erfüllbar
49
Horn-Formel
KNF, pro Klausel höchstens ein nichtnegiertes Literal
50
SAT
-Erfüllbarkeit von aussagenlogischen Formeln -entscheidbar -LBA -> Typ-1 -speicherbeschränkt -NP -nachweis-polynomiell -NP-vollständig -DTIME(2^n) DSPACE(n)
51
O(f)-zeitbeschränkt
Tm hält bestimmter Anzahl von Schritten in Abhängigkeit zu der Eingabe
52
O(f)-speicherbeschränkt
TM verwendet nur eine bestimmte Anzahl von Speicherzellen in Abhängigkeit von der Eingabe (LBA)
53
DTIME(f(n))
Klasse aller Sprachen, welche durch zeitbeschränkt TM entschieden werden können
54
DSPACE(f(n))
Klasse aller Sprachen die von speicherbeschränkten TM entschieden werden können
55
Komplexitätsklassen
P, Exp, L, PSpace
56
P
Polynomielle Zeit DTime(n^d)
57
Exp
Exponentielle Zeit DTime(2^(n^d))
58
L
Logarithmischer Speicher DSpace(log n)
59
PSpace
Polynomieller Speicher DSpace (n^d)
60
Beziehung Komplexitätsklassen
L⊆ P ⊆ PSpace ⊆ Exp -> P ⊊ Exp -> L ⊊ PSpace
61
O(f)-zeitbeschränkt (Nichtdeterministische TM)
jeder Berechnungspfad hält nach einer Anzahl von Schritten in Abhängigkeit von der Eingabe
61
NSpace(f(n))
Klasse aller Sprachen, welche durch eine speicherbeschränkte NTM entschieden werden können
61
O(f)-speicherbeschränkt (Nichtdeterministische TM)
jeder Berechnungspfad verwendet nur eine bestimmte Anzahl von Speicherzellen in Abhängigkeit von der Eingabe
62
NTime(f(n))
Klasse aller Sprachen, welche durch eine O(f)-zeitbeschränkte NTM entschieden werden können
63
Nichtdeterministische Komplexitätsklassen
NP, NExp, NL, NPSpace
64
NP
nichtdeterministische Polynomielle Zeit NTime(n^d)
65
NExp
nichtdeterministische Exponentielle Zeit NTime(2^(n^d))
66
NL
nichtdeterministischer polynomieller Speicher NSpace (log n)
67
NPSpace
nichtdeterministischer polynomieller Speicher NSpace (n^d)
68
Beziehung aller Komplexitätsklassen
L ⊆ NL ⊆ P ⊆ NP ⊆ PSpace = NPSpace ⊆ Exp ⊆ NExp
69
Polynomieller Verifikator
Zertifikat = Lösung Verifikator = prüft Lösung TM die Lösungen prüfen
70
Nachweis-polynomiell
Sprache hat einen polynomiellen Verifikator
71
NP-schwer
wenn jede Sprache in NP darauf reduzierbar ist
72
NP-vollständig
NP-schwer, liegt in NP
73
P-schwer
wenn jede Sprachein P mit logarithmischen Speicherbedarf darauf reduzierbar ist
74

Formale Systeme (2 decks)

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