Theoretische Informatik

Card Set Information

Author:
HahTse
ID:
255677
Filename:
Theoretische Informatik
Updated:
2014-02-11 09:49:41
Tags:
informatik
Folders:

Description:
Flashcards für vorbereitung auf theoretische Informatik
Show Answers:

Home > Flashcards > Print Preview

The flashcards below were created by user HahTse on FreezingBlue Flashcards. What would you like to do?


  1. 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)*
  2. Ogden's Lemma
    • 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
  3. Turingmaschine
    Endkonfiguration
    Konfiguration nqav ist genau dann Endkonfiguration, wenn (q,a,0)∈δ(q,a) gilt

    TM kann in dieser Konfiguration anhalten
  4. Turingmaschinen
    Arten von Nichtdeterminismus
    • (1) Undefiniertheit: |δ(q,a)|<1
    • (2) Mehrdeutigkeit: |δ(q,a)|>1
  5. deterministische Turingmaschine
    wenn |δ(q,a)|=1 für alle (q,a) ∈ Q  Γ
  6. 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
  7. 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
  8. Sprache eindeutig oder inhärent mehrdeutig
    • kontextfreie Sprache eindeutig, wenn G mit L=L(G) eindeutig
    • Andernfalls ist L inhärent mehrdeutig
  9. eindeutige kontextfreie Grammatik
    Für jedes mit G ableitbare Wort gibt es nur einen Syntaxbaum
  10. 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
  11. 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
    • |vx|≥1
    • |vwx|≤n
  12. äquivalenter Zustand
    • p und q äq. gdw.
  13. Nerode-Relation
    • Für L⊆Σ* sei Binärrelation Rin Σ* x Σ* wie folgt erklärt:
  14. 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)
  15. 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
  16. 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=ε
  17. 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)
  18. Äquivalenzklassenautomat
    • A' = (Q',Σ',q0',δ',F')
    • Q' = [Q] /         Σ'=Σ
    • q0'=[q0]
    • F'={[q]|q∈F}
    • δ'([q],a)=[δ(q,a)]
    •  - wohldefiniert und akzeptiert gleiche Sprache wie a
  19. von G erzeugte Sprache?
    (G=(T,G,s,R))
    Menge L(G) mit

    L(G)={x|x∈T*,s->G*x}
  20. 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≠∅}
  21. 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 Σ
  22. Automat konstruieren, der Sprache L(A1)L(A2) akzeptiert
    • Q=Q1 ∪ Q2 (mit Q1 disjunkt zu Q2)
    • q0 = q1
    •  or
    •  or

    • F=
    • F1 ∪ F2 , ε ∈ L(A2)
    • F2        , sonst
  23. 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
  24. Beweise: Für einen DEA A kann in linearer Zeit ein DEA A' konstruiert werden, der das Komplement  akzeptiert.
    F durch QF ersetzen
  25. 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.
  26. 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.
  27. Typ 2-Grammatik
    kontextfrei (Def. fehlt)
  28. 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
  29. 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
  30. Chomsky Normalform
    • Alle Produktionen haben die Form
    • A:=BC oder
    • A:= a
    • für A,B,C ∈ H, a ∈ T
  31. Automat konstruieren, der die Vereinigung L(A1) ∪ L(A2) akzeptiert
    • Q= Q1 x Q2
    • q0 = (q1,q2)

    • δ((q,q'),a) = (δ1(q,a,δ2(q',a))
    • F= Q1xF2 ∪ F1xQ2

  32. Ü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
  33. rechtsinvariant
    • Äquivalenzrelation R auf Σ* heißt rechtsinvariant genau dann wenn
  34. 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
  35. 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
  36. Definition Typ 0-Grammatik
    Alle Grammatiken (Lt. Def. 3.1) ohne Einschränkungen
  37. 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
  38. 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
  39. 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
  40. Bandinschrift
    Zeichenkette ab Kopfposition bis zur Position unmittelbar vor dem ersten Blanksymbol auf dem Band
  41. Definition:
    Verkettung von Sprachen L und L'

    Notation:
    LL'
    LL' = { xy | x ∊ L , y ∊ L' }
  42. 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) = ∅
  43. 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
  44. 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.
  45. 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
  46. Beweisidee für Lne = { M | L(M) ≠ ∅ } ist nicht rekursiv
    Ln auf Lne reduzieren
  47. Beweise:
    Lne = { M | L(M) ≠ ∅ } ist rekuriv aufzählbar
    • Aus TM Mfür U eine NDTM M mit LM = Lne konstruieren: NDTM M enthält TM-Code C, wählt w simuliert Mfür Eingabe w
    • Ergebnis der Simulation wird ausgegeben (soweit vorhanden)
  48. Cliquenproblem informal
    Es ist zu entscheiden, ob für gegebene k ∊ N in einem Graphen eine Clique mit k Knoten existiert.
  49. 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)
  50. Σ 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 [ε]deren Vereinigung die Sprache ist
    • Zuerst Überführungsfunktion:
    •  δ([w]R ,a) = [wa]R

What would you like to do?

Home > Flashcards > Print Preview