TIMI an der LMU München | Karteikarten & Zusammenfassungen

Lernmaterialien für TIMI an der LMU München

Greife auf kostenlose Karteikarten, Zusammenfassungen, Übungsaufgaben und Altklausuren für deinen TIMI Kurs an der LMU München zu.

TESTE DEIN WISSEN

Disjunktheit kontextfreier Sprachen

Lösung anzeigen
TESTE DEIN WISSEN

Das Disjunktheitsproblem DISJ:

Geg. Zwei KVG G1 und G2

Frage: Ist L(G1) ∩ L(G2) = ∅?


-> Das Disjunktheitsproblem für KVG ist unentscheidbar


-> Beweis durch Reduktion

Lösung ausblenden
TESTE DEIN WISSEN

Konjunktive Normalform

Lösung anzeigen
TESTE DEIN WISSEN

>  Ein Literal a ist eine Variable x oder negierte Variable ¬x. Abkürzung: x ̄ statt ¬x.

>  Eine Klausel ist eine Disjunktion C = a1 ∨ . . . ∨ ak von Literalen.

>  Eine Formel in KNF ist eine Konjunktion F = C1 ∧ ...Cm von Klauseln.                            

> Eine Formel in KNF ist in k-KNF, wenn jede Klausel höchstens k Literale enthält.


KNF-SAT ist das Problem SAT für Formeln in KNF 

k-SAT ist das Problem SAT für Formeln in k-KNF

Lösung ausblenden
TESTE DEIN WISSEN

Welche Methoden kennen Sie, um zu beweisen, dass eine Sprache:

unentscheidbar ist?

Lösung anzeigen
TESTE DEIN WISSEN
  • Beweis eines Widerspruchs (Halteproblem)
  • Reduktion auf ein unentscheidbares Problem (z.B. Halteproblem)
Lösung ausblenden
TESTE DEIN WISSEN

Determinisierung

Lösung anzeigen
TESTE DEIN WISSEN

Ziel: für jeden NEA A gibt es einen äquivalenten DEA AD
Idee: 

  • zu jedem Zeitpunkt Menge von möglichen Zuständen S ⊆ Q 
  • |Q| endlich ->endlich viele Teilmengen 
  •  für S ⊆ Q und Eingabe a ist die Menge der möglichen Folgezustände eindeutig
Lösung ausblenden
TESTE DEIN WISSEN

Kleene’sche Hülle


Lösung anzeigen
TESTE DEIN WISSEN

Beispiel:
L = {01, 110} 

L∗ =, 01, 110, 0101, 01110, 11001, 010101, 110110, 0101110, 0111001, 1100101, 01010101, ... Eigenschaften: 

  • (L*)* = L*
  •  ∅* = {} 
  •  {}∗ = {} 
  • L* ist unendlich, außer in diesen 2 Fällen


Lösung ausblenden
TESTE DEIN WISSEN

Reguläre Ausdrücke


Lösung anzeigen
TESTE DEIN WISSEN

Reguläre Ausdrücke und ihre Sprachen sind induktiv definiert: 

  • Konstanten  und ∅ sind reguläre Ausdrücke, mit L() = {} und L(∅) = ∅ 
  •  Für a ∈ Σ ist a ein regulärer Ausdruck, mit L(a) = {a}
  • Sind E,F reguläre Ausdrücke, dann auch (E + F), mit L(E + F) = L(E)∪L(F) 
  • Sind E,F reguläre Ausdrücke, dann auch (E ·F), mit L(E ·F) = L(E)·L(F) 
  • Ist E regulärer Ausdruck, dann auch E*, mit L(E*) = L(E)*


Lösung ausblenden
TESTE DEIN WISSEN

Hüllenbildung


Lösung anzeigen
TESTE DEIN WISSEN

Sei A = (Q,Σ,δ,q0,F) ein -NEA.
Für P ⊆ Q ist die ɛ -Hülle(P) induktiv definiert durch: 

  •  P ⊆ ɛ -Hülle(P) 
  • Ist p ∈ ɛ -Hülle(P) und q ∈ δ(p,), dann ist q ∈ ɛ -Hülle(P).


Lösung ausblenden
TESTE DEIN WISSEN

Ausdrucksst¨arke


Lösung anzeigen
TESTE DEIN WISSEN
  • Regul¨are Ausdr¨ucke beschreiben genau die Sprachen, die von DEA (oder NEA, ɛ -NEA) erkannt werden.
  • F¨ur jeden regulären Ausdruck R gibt es einen ɛ -NEA AR mit L(AR) = L(R).
  • Für jeden NEA A gibt es einen regulären Ausdruck RA mit L(RA) = L(A).






Lösung ausblenden
TESTE DEIN WISSEN

            

                                                           

Berechenbare Funktionen

                                               


       

Lösung anzeigen
TESTE DEIN WISSEN

            

                                                           

Eine (partielle) Funktion f : Nk → N ist berechenbar, wenn es einen Algorithmus gibt, der

                       

- bei Eingabe von (n1, . . . , nk ) genau dann terminiert, wenn f(n1,...,nk) definiert ist,

                       

- und dann den Wert f(n1,...,nk) ausgibt.

                                               


           

Lösung ausblenden
TESTE DEIN WISSEN

            

                                                           

Turing-Maschine: Definition

                                               


           

Lösung anzeigen
TESTE DEIN WISSEN

            

                                                           

Eine deterministische Turing-Maschine (DTM) M mit Alphabet Σ besteht aus:

                       

-Zust ̈ande Q
-Bandalphabet Γ ⊇ Σ
-Leerzeichen 􏰓 ∈ Γ \ Σ
-U ̈bergangsfunktion δ:Q×Γ→Q×Γ×{L,R}                          

-Anfangszustand q0 ∈ Q 

-Endzust ̈ande F ⊆ Q

                       

Kurzschreibweise:   

M = (Q,Σ,Γ,􏰓,δ,q0,F)

                                               


           

Lösung ausblenden
TESTE DEIN WISSEN

            

                                                           

Konfigurationen

                                               


           

Lösung anzeigen
TESTE DEIN WISSEN

Eine Konfiguration α von M ist eine Zeichenkette 

α = a1a2 ...ai−1 q aiai+1 ...an

                       

mit ai ∈ Γ fu ̈r i ≤ n und q∈Q.                  

Interpretation:
-M ist in Zustand q
-Der Kopf ist auf Bandzelle i, in der ai steht
- a1a2 ...ai−1 ist der Bandinhalt links vom Kopf 

- Links von a1 sind nur 􏰓 auf dem Band
- ai +1 . . . an ist der Bandinhalt rechts vom Kopf 

- Rechts von an sind nur 􏰓 auf dem Band

 

Lösung ausblenden
TESTE DEIN WISSEN

Regeln zum Vereinfachen


Lösung anzeigen
TESTE DEIN WISSEN


  • Kommutativgesetz 
    • (R + S) = (S + R) 
  • Neutrale Elemente 
    • ∅+ R = R +∅ = R 
  • Absorption 
    • ∅R = R∅ = ∅ 
  • Distributivgesetze
    •  R(S + T) = RS + RT 
    • (S + T)R = SR + TR 
  • Gesetze über Kleene-Stern
    • (R*)* = R* 
    • ∅* =ɛ   
    • ɛ *=ɛ  


Lösung ausblenden
  • 561168 Karteikarten
  • 7985 Studierende
  • 555 Lernmaterialien

Beispielhafte Karteikarten für deinen TIMI Kurs an der LMU München - von Kommilitonen auf StudySmarter erstellt!

Q:

Disjunktheit kontextfreier Sprachen

A:

Das Disjunktheitsproblem DISJ:

Geg. Zwei KVG G1 und G2

Frage: Ist L(G1) ∩ L(G2) = ∅?


-> Das Disjunktheitsproblem für KVG ist unentscheidbar


-> Beweis durch Reduktion

Q:

Konjunktive Normalform

A:

>  Ein Literal a ist eine Variable x oder negierte Variable ¬x. Abkürzung: x ̄ statt ¬x.

>  Eine Klausel ist eine Disjunktion C = a1 ∨ . . . ∨ ak von Literalen.

>  Eine Formel in KNF ist eine Konjunktion F = C1 ∧ ...Cm von Klauseln.                            

> Eine Formel in KNF ist in k-KNF, wenn jede Klausel höchstens k Literale enthält.


KNF-SAT ist das Problem SAT für Formeln in KNF 

k-SAT ist das Problem SAT für Formeln in k-KNF

Q:

Welche Methoden kennen Sie, um zu beweisen, dass eine Sprache:

unentscheidbar ist?

A:
  • Beweis eines Widerspruchs (Halteproblem)
  • Reduktion auf ein unentscheidbares Problem (z.B. Halteproblem)
Q:

Determinisierung

A:

Ziel: für jeden NEA A gibt es einen äquivalenten DEA AD
Idee: 

  • zu jedem Zeitpunkt Menge von möglichen Zuständen S ⊆ Q 
  • |Q| endlich ->endlich viele Teilmengen 
  •  für S ⊆ Q und Eingabe a ist die Menge der möglichen Folgezustände eindeutig
Q:

Kleene’sche Hülle


A:

Beispiel:
L = {01, 110} 

L∗ =, 01, 110, 0101, 01110, 11001, 010101, 110110, 0101110, 0111001, 1100101, 01010101, ... Eigenschaften: 

  • (L*)* = L*
  •  ∅* = {} 
  •  {}∗ = {} 
  • L* ist unendlich, außer in diesen 2 Fällen


Mehr Karteikarten anzeigen
Q:

Reguläre Ausdrücke


A:

Reguläre Ausdrücke und ihre Sprachen sind induktiv definiert: 

  • Konstanten  und ∅ sind reguläre Ausdrücke, mit L() = {} und L(∅) = ∅ 
  •  Für a ∈ Σ ist a ein regulärer Ausdruck, mit L(a) = {a}
  • Sind E,F reguläre Ausdrücke, dann auch (E + F), mit L(E + F) = L(E)∪L(F) 
  • Sind E,F reguläre Ausdrücke, dann auch (E ·F), mit L(E ·F) = L(E)·L(F) 
  • Ist E regulärer Ausdruck, dann auch E*, mit L(E*) = L(E)*


Q:

Hüllenbildung


A:

Sei A = (Q,Σ,δ,q0,F) ein -NEA.
Für P ⊆ Q ist die ɛ -Hülle(P) induktiv definiert durch: 

  •  P ⊆ ɛ -Hülle(P) 
  • Ist p ∈ ɛ -Hülle(P) und q ∈ δ(p,), dann ist q ∈ ɛ -Hülle(P).


Q:

Ausdrucksst¨arke


A:
  • Regul¨are Ausdr¨ucke beschreiben genau die Sprachen, die von DEA (oder NEA, ɛ -NEA) erkannt werden.
  • F¨ur jeden regulären Ausdruck R gibt es einen ɛ -NEA AR mit L(AR) = L(R).
  • Für jeden NEA A gibt es einen regulären Ausdruck RA mit L(RA) = L(A).






Q:

            

                                                           

Berechenbare Funktionen

                                               


       

A:

            

                                                           

Eine (partielle) Funktion f : Nk → N ist berechenbar, wenn es einen Algorithmus gibt, der

                       

- bei Eingabe von (n1, . . . , nk ) genau dann terminiert, wenn f(n1,...,nk) definiert ist,

                       

- und dann den Wert f(n1,...,nk) ausgibt.

                                               


           

Q:

            

                                                           

Turing-Maschine: Definition

                                               


           

A:

            

                                                           

Eine deterministische Turing-Maschine (DTM) M mit Alphabet Σ besteht aus:

                       

-Zust ̈ande Q
-Bandalphabet Γ ⊇ Σ
-Leerzeichen 􏰓 ∈ Γ \ Σ
-U ̈bergangsfunktion δ:Q×Γ→Q×Γ×{L,R}                          

-Anfangszustand q0 ∈ Q 

-Endzust ̈ande F ⊆ Q

                       

Kurzschreibweise:   

M = (Q,Σ,Γ,􏰓,δ,q0,F)

                                               


           

Q:

            

                                                           

Konfigurationen

                                               


           

A:

Eine Konfiguration α von M ist eine Zeichenkette 

α = a1a2 ...ai−1 q aiai+1 ...an

                       

mit ai ∈ Γ fu ̈r i ≤ n und q∈Q.                  

Interpretation:
-M ist in Zustand q
-Der Kopf ist auf Bandzelle i, in der ai steht
- a1a2 ...ai−1 ist der Bandinhalt links vom Kopf 

- Links von a1 sind nur 􏰓 auf dem Band
- ai +1 . . . an ist der Bandinhalt rechts vom Kopf 

- Rechts von an sind nur 􏰓 auf dem Band

 

Q:

Regeln zum Vereinfachen


A:


  • Kommutativgesetz 
    • (R + S) = (S + R) 
  • Neutrale Elemente 
    • ∅+ R = R +∅ = R 
  • Absorption 
    • ∅R = R∅ = ∅ 
  • Distributivgesetze
    •  R(S + T) = RS + RT 
    • (S + T)R = SR + TR 
  • Gesetze über Kleene-Stern
    • (R*)* = R* 
    • ∅* =ɛ   
    • ɛ *=ɛ  


TIMI

Erstelle und finde Lernmaterialien auf StudySmarter.

Greife kostenlos auf tausende geteilte Karteikarten, Zusammenfassungen, Altklausuren und mehr zu.

Jetzt loslegen

Das sind die beliebtesten StudySmarter Kurse für deinen Studiengang TIMI an der LMU München

Für deinen Studiengang TIMI an der LMU München gibt es bereits viele Kurse, die von deinen Kommilitonen auf StudySmarter erstellt wurden. Karteikarten, Zusammenfassungen, Altklausuren, Übungsaufgaben und mehr warten auf dich!

Das sind die beliebtesten TIMI Kurse im gesamten StudySmarter Universum

TI 3

Universität Hamburg

Zum Kurs
TMMI

Technische Hochschule Ingolstadt

Zum Kurs
TIA

Beuth Hochschule für Technik

Zum Kurs
TIM MẠCH

Can-Tho University

Zum Kurs
tite

Central Luzon State University

Zum Kurs

Die all-in-one Lernapp für Studierende

Greife auf Millionen geteilter Lernmaterialien der StudySmarter Community zu
Kostenlos anmelden TIMI
Erstelle Karteikarten und Zusammenfassungen mit den StudySmarter Tools
Kostenlos loslegen TIMI