Theoretische Informatik

• 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)*

• Für kontextfreie Sprache L gibt es , so dass für jedes Wort  mit |z|≥n gilt: wenigstens n Zeichen in z markiert, dann z in der Form uvwxy darstellbar
• (1) wenigstens ein Zeichen in vx markiert
• (2) höchstens n Zeichen in vwx markiert
• (3) für alle

Konfiguration nqav ist genau dann Endkonfiguration, wenn (q,a,0)∈δ(q,a) gilt

TM kann in dieser Konfiguration anhalten

• (1) Undefiniertheit: |δ(q,a)|<1
• (2) Mehrdeutigkeit: |δ(q,a)|>1

wenn |δ(q,a)|=1 für alle (q,a) ∈ Q  Γ

• 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

• M=(Q,Γ,δ,q₀,F)
• Q Zustandsmenge, endlich
• Σ Eingabealphabet, endlich
• Γ Bandalphabet, enthält B∉Σ, umfasst Eingabealphabet
• q₀∈Q Anfangszustand
• F⊆Q Endzustände:
•  Endzustand
•  Übergangsfunktion

• kontextfreie Sprache eindeutig, wenn G mit L=L(G) eindeutig
• Andernfalls ist L inhärent mehrdeutig

Für jedes mit G ableitbare Wort gibt es nur einen Syntaxbaum

• (1) Regeln so umbauen, dass auf rechter Seite genau 1 Terminalsymbol oder nur Nichtterminalsymbole
• (2) Iterativ Regeln der Form A->B₀...B_n+2 ersetzen durch A->B₀C₀ und C->B₁...B_n+2
• (3) ε-Regeln ersetzen
• (4)Kettenregeln ersetzen
•  -Graph der Nichtterminalsymbole kreisfrei machen
•  -im topologisch sortierten Graph Kettenregeln ersetzen

• 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
• |vx|≥1
• |vwx|≤n
• 

• p und q äq. gdw.
• 
• 

• Für L⊆Σ* sei Binärrelation R_L in Σ* x Σ* wie folgt erklärt:
• 

• A = (Q,Σ,q₀,δ,F)
• Q und Σ endlich, paarweise disjunkt
• q₀∈Q
• F⊆Q
• δ:QxΣ->Q
• erweitertes δ: δ*: QxΣ*->Qδ*(q,e) = q
• δ*(q,ax)=δ*(δ(q,a),x)

• 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

• 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=ε

• 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) R_L hat endlichen Index (mit R_L = Nerode-Relation)

• A' = (Q',Σ',q₀',δ',F')
• Q' = [Q] /         Σ'=Σ
• q₀'=[q₀]
• F'={[q]|q∈F}
• δ'([q],a)=[δ(q,a)]
•  - wohldefiniert und akzeptiert gleiche Sprache wie a

Menge L(G) mit

L(G)={x|x∈T*,s->G*x}

• A = (Q,Σ,q₀,δ,F)
• (a) Q und Σ endlich paarweise disjunkt
• (b) q₀ ∈ Q
• (c) F ⊆ Q
• (d) δ eine Abbildung δ:QxΣ->P(Q)
• erweitertes δ:
• (a) δ*(q,ε)={q}
• (b) δ*(q,wx) =
•     
• akzeptierte Sprache: {x∈Σ*|δ*(q₀,x)∩F≠∅}

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 Σ

• Q=Q₁ ∪ Q₂ (mit Q₁ disjunkt zu Q₂)
• q₀ = q₁
• 
•  or
•  or
• 

• F=
• F₁ ∪ F₂ , ε ∈ L(A₂)
• F₂        , sonst

• (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

F durch QF ersetzen

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.

Mittels Breitensuche entscheiden, ob alle nichtakzeptierten Zustände unerreichbar.

kontextfrei (Def. fehlt)

• Q'=Q       q₀'=q₀
• 
• {δ(q,a)}  q∈QF oder
• {δ(q,a),δ(q₀,a)} q∈F
• F'=F

• engl. Knapsack
• E: Folgen von nat. Zahlen {g_i}ⁿ_i=1 (Größen von Objekten) und {a_i}ⁿ_i=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 a_j = N und Σ_j∈J g_j ≤ G

• Alle Produktionen haben die Form
• A:=BC oder
• A:= a
• für A,B,C ∈ H, a ∈ T

• Q= Q₁ x Q₂
• q₀ = (q₁,q₂)

• 
• δ((q,q'),a) = (δ₁(q,a,δ₂(q',a))
• F= Q₁xF₂ ∪ F₁xQ₂

Zustand eines DEA A=(Q,Σ,q₀,δ,F), der vom Anfangszustand nicht erreicht wird, d.h. für den es kein w∈Σ^* gibt mit δ^*(q₀,w) = q

• Äquivalenzrelation R auf Σ^* heißt rechtsinvariant genau dann wenn
• 

• (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

• 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

Alle Grammatiken (Lt. Def. 3.1) ohne Einschränkungen

• Q' = P(Q)
• q_o' = {q₀}
• , a∈Σ:δ'(q',a)=
• F'={q'∈Q'|q'∩F≠∅}
• danach minimieren und überflüssige Zustände entfernen

• Regel (l,r)∈R existiert und Wörter u,v∈(T∪H)^* mit
• x = ulv und
• y = urv
• Notation:
• x->_R y

• 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

Zeichenkette ab Kopfposition bis zur Position unmittelbar vor dem ersten Blanksymbol auf dem Band

LL' = { xy | x ∊ L , y ∊ L' }

• L(A1) = L(A₂) ,gdw.
•      L(A₁) ∩ ¬ L(A₂)  = ∅
• und
•    ¬  L(A₁) = L(A₂) = ∅

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

• 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.

• L_d ist Menge der Kodierungen w solcher Tm M, für die gilt:
•          w ∉ L(M_w)
• nicht rekursiv aufzählbar 
• nicht entscheidbar

L_n auf L_ne reduzieren

• Aus TM M_u für U eine NDTM M mit L_M = L_ne konstruieren: NDTM M enthält TM-Code C, wählt w simuliert M_C für Eingabe w
• Ergebnis der Simulation wird ausgegeben (soweit vorhanden)

Es ist zu entscheiden, ob für gegebene k ∊ N in einem Graphen eine Clique mit k Knoten existiert.

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)

• Alphabet Σ
• Zustandsmenge; Äquiv.klasse bez. R
• Anfangszustand [ε]_R deren Vereinigung die Sprache ist
• Zuerst Überführungsfunktion:
•  δ([w]_R ,a) = [wa]_R