Tut 3 Flashcards
1
Q
Wie stellt man in einem regulären Ausdruck die Sprache dar, die das leere Wort enthält?
A
2
Q
PPL für kontextfreie Sprachen
A
-> L ist nicht kontextfrei
3
Q
Turingmaschine
A
- 𝑇𝑀 = (𝐸, 𝐵, 𝑆, 𝛿, 𝑠0, 𝐹 )
- analysierende Methode für Typ-0-Sprachen
- Eine Konfiguration bestimmt eindeutig den Gesamtzustand einer Turingmaschine inklusive Bandinhalt und Kopfposition
- LndetTM = LTM
- zu jedem EA und zu jedem KA gibt es eine äquivalente TM
- linear beschränkte TM: Begrenzungssymbol $
- Zustandstafel:
4
Q
universelle Turingmaschine
A
Eine universelle Turingmaschine 𝑈 ist in der Lage, die Kodierung einer beliebigen anderen Turingmaschine
𝑀 mitsamt einer Eingabe 𝑤 als Eingabe zu interpretieren und eine Berechnung von 𝑀 auf 𝑤 zu simulieren
5
Q
Polynomialzeitreduktion
A
- Polynomialzeitreduzierbarkeit 𝑄 ≤ 𝑝𝑜𝑙𝑃:
- 𝑄 heißt auf 𝑃 polynomialzeit-reduzierbar gdw. 𝑄 durch 𝑓 in 𝑃 transformiert werden kann, und jede Lösung 𝐿𝑃 von 𝑓(𝑄) = 𝑃 durch 𝑔 in eine Lösung 𝐿𝑄 von 𝑄 transformiert werden kann.
6
Q
Komplexitätsklassen
A
- NP vollständig: NP inter NP-schwer
- In 𝑃 liegen die „gerade so noch praktisch lösbaren“ Probleme
7
Q
Grammatiken
A
Bei allen Typen, außer Typ 1, sind auch Übergänge A → λ erlaubt (Typ 1 auch, wenn S nicht auf rechter Seite vorkommt)
8
Q
Grammatiken Hierarchie
A
z.B. Für eine reguläre Sprache gilt das Pumping-Lemma für kontextfreie Sprachen.
9
Q
Eigenschaften eines Algorithmus
A
- Allgemeinheit
- Determiniertheit (außer randomisierte Algorithmen)
- Endlichkeit
- Finitheit: endliche Beschreibung
- Effektivität: zeitliche endliche Ausführbarkeit
- Terminiertheit: endliche Anzahl an Schritten
10
Q
entscheidbar, aufzählbar, abzählbar
A
- aufzählbar -> abzählbar (umgekehrt nicht!)
- entscheidbar -> aufzählbar
