-
Definition Menge der regulären Ausdrücke über Σ
- Kleinste Menge, die alle Elemente aus Σ enthält und
- bezüglich der Konstruktionsregeln abgeschlossen ist: Wenn A und B reguläre Ausdrücke, dann auch (AB), (A|B) und (A)*
-
-
Turingmaschine
Endkonfiguration
Konfiguration nqav ist genau dann Endkonfiguration, wenn (q,a,0)∈δ(q,a) gilt
TM kann in dieser Konfiguration anhalten
-
Turingmaschinen
Arten von Nichtdeterminismus
- (1) Undefiniertheit: |δ(q,a)|<1
- (2) Mehrdeutigkeit: |δ(q,a)|>1
-
deterministische Turingmaschine
wenn |δ(q,a)|=1 für alle (q,a) ∈ Q  Γ
-
Turing Maschinen
Konfiguration
- Wort uqv mit u,v∈Γ* und q∈Q heißt Konfiguration
- z.B. uqav heißt:
- ...B u a v B...
- mit Position des Schreibkopfs im Zustand q auf a
-
Turing Maschine
Komponenten
- M=(Q,Γ,δ,q0,F)
- Q Zustandsmenge, endlich
- Σ Eingabealphabet, endlich
- Γ Bandalphabet, enthält B∉Σ, umfasst Eingabealphabet
- q0∈Q Anfangszustand
- F⊆Q Endzustände:
Endzustand Übergangsfunktion
-
Sprache eindeutig oder inhärent mehrdeutig
- kontextfreie Sprache eindeutig, wenn G mit L=L(G) eindeutig
- Andernfalls ist L inhärent mehrdeutig
-
eindeutige kontextfreie Grammatik
Für jedes mit G ableitbare Wort gibt es nur einen Syntaxbaum
-
Herstellung der Chomsky-Normalform aus kontextfreier Grammatik G(V,T,S,P) der Größe s(G)
- (1) Regeln so umbauen, dass auf rechter Seite genau 1 Terminalsymbol oder nur Nichtterminalsymbole
- (2) Iterativ Regeln der Form A->B0...Bn+2 ersetzen durch A->B0C0 und C->B1...Bn+2
- (3) ε-Regeln ersetzen
- (4)Kettenregeln ersetzen
- -Graph der Nichtterminalsymbole kreisfrei machen
- -im topologisch sortierten Graph Kettenregeln ersetzen
-
Pumping Lemma für kontextfreie Sprachen
- für kontextfreie Sprache L gibt es n∈N so dass jedes Wort z∈L mit |z|≥n sich als uvwxy darstellen lässt und

-
äquivalenter Zustand
- p und q äq. gdw.
 
-
Nerode-Relation
- Für L⊆Σ* sei Binärrelation RL in Σ* x Σ* wie folgt erklärt:

-
Deterministischer Endlicher Automat (DEA)
Definition
- A = (Q,Σ,q0,δ,F)
- Q und Σ endlich, paarweise disjunkt
- q0∈Q
- F⊆Q
- δ:QxΣ->Q
- erweitertes δ: δ*: QxΣ*->Qδ*(q,e) = q
- δ*(q,ax)=δ*(δ(q,a),x)
-
Typ 3-Grammatik
- auch: rechtslinear od. regulär
- alle kontextfreien Grammatiken mit folgenden Bedingungen:
gilt entweder v=ε oder v ist Wort der Form aB mit a∈T und B∈H - die von regulären Grammatiken erzeugten Sprachen sind genau die regulären Sprachen
-
Definition Typ 1-Grammatik
- auch: kontextsensitiv
- für alle Regeln (u,v)∈R gelten entweder u∈H+, v∈((H∪T){s})+ und |u|≤|v| oder aber u=s und v=ε
-
Satz von Nerode
- Für L⊆Σ* sind äquivalent:
- (1) L wird von einem DEA A akzeptiert (d.h. L = L(A))
- (2) L ist Vereinigung einiger Äquivalenzklassen einer rechtsinvarianten Äquivalenzrelation mit endlichem Index
- (3) RL hat endlichen Index (mit RL = Nerode-Relation)
-
-
von G erzeugte Sprache?
(G=(T,G,s,R))
Menge L(G) mit
L(G)={x|x∈T*,s->G*x}
-
Nichtdeterministischer Endlicher Automat (NEA)
Definition
- A = (Q,Σ,q0,δ,F)
- (a) Q und Σ endlich paarweise disjunkt
- (b) q0 ∈ Q
- (c) F ⊆ Q
- (d) δ eine Abbildung δ:QxΣ->P(Q)
- erweitertes δ:
- (a) δ*(q,ε)={q}
- (b) δ*(q,wx) =
-
 - akzeptierte Sprache: {x∈Σ*|δ*(q0,x)∩F≠∅}
-
Definition reguläre Sprache
Eine Sprache, durch endlich viele Anwendungen der Operationen Verkettung, Vereinigung und Iteration aus endlichen Sprachen über einem Alphabet Σ gebildet werden kann, heißt reguläre Sprache über Σ
-
-
Beweise: Für einen DEA A kann in linearer Zeit entschieden werden, ob L(A) unendlich ist.
- (1) alle überflüssigen Zustände entfernen -> A'
- (2) L(A) unendlich gdw. A' enthält Kreis, von dem aus akzeptierender Zustand erreichbar
- (3) Richtung der Kanten umgkehren. Mit Breitensuche entscheiden, ob von den akzeptierenden Zuständen ausgehend Rückkanten auftreten
-
Beweise: Für einen DEA A kann in linearer Zeit ein DEA A' konstruiert werden, der das Komplement  akzeptiert.
F durch QF ersetzen
-
Beweise:
Für einen DEA A kann in linearer Zeit entschieden werden, ob L(A) leer ist.
Automat A als kantenbewerteten Graph auffassen. Knotenmenge = Zustandsmenge, Kantenmenge : {(q,δ(q,a))|q∈ Q, a∈Σ}
Mittels Breitensuche entscheiden, ob kein akzeptierter Zustand vom Startzustand aus erreichbar ist.
-
Beweise:
Für einen DEA A mit Alphabet Σ kann in linearer Zeit entschieden werden, ob L(A) = Σ* gilt.
Mittels Breitensuche entscheiden, ob alle nichtakzeptierten Zustände unerreichbar.
-
Typ 2-Grammatik
kontextfrei (Def. fehlt)
-
Konstruktion eines (NEA) Automaten für Sprache L(A)+
- Q'=Q q0'=q0
 - {δ(q,a)} q∈QF oder
- {δ(q,a),δ(q0,a)} q∈F
- F'=F
-
Beispiele schwieriger Probleme
Rucksackproblem (Entscheidbarkeitsvariante)
- engl. Knapsack
- E: Folgen von nat. Zahlen {gi}ni=1 (Größen von Objekten) und {ai}ni=1 (Werte von Objekten) sowie nat Zahl G (Größenlimit) und N (gewünschter Gesamtwert)
- Frage: gibt es Teilmenge J⊆{1...n} mit Σj∈J aj = N und Σj∈J gj ≤ G
-
Chomsky Normalform
- Alle Produktionen haben die Form
- A:=BC oder
- A:= a
- für A,B,C ∈ H, a ∈ T
-
Automat konstruieren, der die Vereinigung L(A1) ∪ L(A2) akzeptiert
 - δ((q,q'),a) = (δ1(q,a,δ2(q',a))
- F= Q1xF2 ∪ F1xQ2
-
Überflüssiger Zustand
Zustand eines DEA A=(Q,Σ,q0,δ,F), der vom Anfangszustand nicht erreicht wird, d.h. für den es kein w∈Σ* gibt mit δ*(q0,w) = q
-
rechtsinvariant
- Äquivalenzrelation R auf Σ* heißt rechtsinvariant genau dann wenn
 
-
Definition Grammatik
G=(T,H,s,R)
- (a) T,H,R endl. Mengen
- (b) H ∩ T = ∅
- (c) R ⊆ ((H∪T)*T*)x(H∪T)*
- (d) s ∈ H
- T - Terminalsymbole
- H - Nichtterminalsymbole
- s - Startsymbol
- R - Regeln
-
Konstruktion eines (NEA) Automaten für Sprache L(A)*
- Schritt 1: L(A)+ konstruieren
- Schritt 2: L(A)* = L(A)+ ∪ {ε}
- d.h. Automat konstruieren, der das leere Wort akzeptiert, dann Vereinigung aus diesem mit dem aus Schritt 1 erzeugten Automaten
-
Definition Typ 0-Grammatik
Alle Grammatiken (Lt. Def. 3.1) ohne Einschränkungen
-
Konstruktion eines DEA ausgehend von einem NEA (Potenzmengenkonstruktion)
- Q' = P(Q)
- qo' = {q0}
, a∈Σ:δ'(q',a)= - F'={q'∈Q'|q'∩F≠∅}
- danach minimieren und überflüssige Zustände entfernen
-
Wann ist Wort y über T∪H direkt ableitbar aus Wort x∈(T∪H)*?
- Regel (l,r)∈R existiert und Wörter u,v∈(T∪H)* mit
- x = ulv und
- y = urv
- Notation:
- x->R y
-
Turingmaschinen
Semantische Fuktion
f:Γ*->Γ*
- Eine i.a. partielle Funktion f:Γ*->Γ* heißt semantische Funktion für Turingmaschine M, falls: f(w)=
- v ... v ist Bandinschrift nach einer terminierenden Berechnung, die mit Bandinschrift w startet
- undefiniert ... es gibt keine terminierende Berechnung, die mit Bandinschrift w startet
-
Bandinschrift
Zeichenkette ab Kopfposition bis zur Position unmittelbar vor dem ersten Blanksymbol auf dem Band
-
Definition:
Verkettung von Sprachen L und L'
Notation:
LL'
LL' = { xy | x ∊ L , y ∊ L' }
-
Beweise:
Es gilt
L(A1) = L(A2)
für DEA A1 und A2
- L(A1) = L(A2) ,gdw.
- L(A1) ∩ ¬ L(A2) = ∅
- und
- ¬ L(A1) = L(A2) = ∅
-
Universelle Sprache:
- rekursiv?
- aufzählbar?
L(U) ist Menge der kodierten Paare (M,w), wobei M Code einer TM ist und w von der druch M kodierten TM akzeptiert wird.
- ist rekursiv aufzählbar
- ist nicht rekursiv
-
Ist das Postsche Korrespondenzproblem (PKP) entscheidbar?
Begründung?
- PKP nicht entscheidbar.
- Reduktion von U auf MPKP möglich. (Modifikation: Erstes Wertepaar der Aufgabenstellung ist erste Wertepaar der Lösung)
- Reduktion von MPKP auf PKP.
-
Ld Diagonalisierungssprache
-entscheidbar?
-rekusiv aufzählbar?
- Ld ist Menge der Kodierungen w solcher Tm M, für die gilt:
- w ∉ L(Mw)
- nicht rekursiv aufzählbar
- nicht entscheidbar
-
Beweisidee für Lne = { M | L(M) ≠ ∅ } ist nicht rekursiv
Ln auf Lne reduzieren
-
Beweise:
Lne = { M | L(M) ≠ ∅ } ist rekuriv aufzählbar
- Aus TM Mu für U eine NDTM M mit LM = Lne konstruieren: NDTM M enthält TM-Code C, wählt w simuliert MC für Eingabe w
- Ergebnis der Simulation wird ausgegeben (soweit vorhanden)
-
Cliquenproblem informal
Es ist zu entscheiden, ob für gegebene k ∊ N in einem Graphen eine Clique mit k Knoten existiert.
-
Sprache rekursiv aufzählbar
Sprache L über Σ rekursiv aufzählbar, wenn es Tm M gibt, mit L = L(M). Es ist nicht vorausgesetzt, das TM M stets anhält- Gehört ein Wort w nicht zur Sprache, wird M u.U. bei dessen Bearbeitung nicht terminieren. In diesem Fall nicht entscheidbar, ob w ∊ L(M) oder w ∉ L(M)
-
Σ rechtsinvariante Äquivalente Relation R in Σ* mit endlichem Index
Aufgabenstellung:
Konstruiere DEA der Sprache akz., die die Vereinigung Äquiv.klassen der Relation R ist
- Alphabet Σ
- Zustandsmenge; Äquiv.klasse bez. R
- Anfangszustand [ε]R deren Vereinigung die Sprache ist
- Zuerst Überführungsfunktion:
- δ([w]R ,a) = [wa]R
|
|