TIMI an der LMU München

Karteikarten und Zusammenfassungen für TIMI an der LMU München

Arrow Arrow

Komplett kostenfrei

studysmarter schule studium
d

4.5 /5

studysmarter schule studium
d

4.8 /5

studysmarter schule studium
d

4.5 /5

studysmarter schule studium
d

4.8 /5

Lerne jetzt mit Karteikarten und Zusammenfassungen für den Kurs TIMI an der LMU München.

Beispielhafte Karteikarten für TIMI an der LMU München auf StudySmarter:

Deterministische Automaten


Beispielhafte Karteikarten für TIMI an der LMU München auf StudySmarter:

Konstruktion eines Automaten


Beispielhafte Karteikarten für TIMI an der LMU München auf StudySmarter:

Determinisierung

Beispielhafte Karteikarten für TIMI an der LMU München auf StudySmarter:

Exponentieller Blow-up

Beispielhafte Karteikarten für TIMI an der LMU München auf StudySmarter:

Hüllenbildung


Beispielhafte Karteikarten für TIMI an der LMU München auf StudySmarter:

Kleene’sche Hülle


Beispielhafte Karteikarten für TIMI an der LMU München auf StudySmarter:

Reguläre Ausdrücke


Beispielhafte Karteikarten für TIMI an der LMU München auf StudySmarter:

Regeln zum Vereinfachen


Beispielhafte Karteikarten für TIMI an der LMU München auf StudySmarter:

Ausdrucksst¨arke


Beispielhafte Karteikarten für TIMI an der LMU München auf StudySmarter:

            

                                                           

Berechenbare Funktionen

                                               


       

Beispielhafte Karteikarten für TIMI an der LMU München auf StudySmarter:

            

                                                           

Turing-Maschine: Definition

                                               


           

Beispielhafte Karteikarten für TIMI an der LMU München auf StudySmarter:

            

                                                           

Konfigurationen

                                               


           

Kommilitonen im Kurs TIMI an der LMU München. erstellen und teilen Zusammenfassungen, Karteikarten, Lernpläne und andere Lernmaterialien mit der intelligenten StudySmarter Lernapp. Jetzt mitmachen!

Jetzt mitmachen!

Flashcard Flashcard

Beispielhafte Karteikarten für TIMI an der LMU München auf StudySmarter:

TIMI

Deterministische Automaten


Ein deterministischer endlicher Automat (DEA) A mit Alphabet Σ besteht aus:

  • Zustände Q (endlich viele!) 
  • Übergangsfunktion δ : Q ×Σ→Q 
  • Anfangszustand q0 ∈ Q 
  • Endzustände F ⊆ Q
    Kurzschreibweise: A = (Q,Σ,δ,q0,F)


TIMI

Konstruktion eines Automaten


Beispiel: Menge L der Wörter, die 01 enthalten, also

 L ={u01v ; u,v ∈ {0,1}* }  

  • q0 Anfangszustand, noch keine 0 gelesen
  •  q1 0 gelesen, noch keine 1 
  • q2 01 gelesen, fertig


TIMI

Determinisierung

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

TIMI

Exponentieller Blow-up

Sei Ln :={w ; w = u1v mit |v| = n − 1} .
Ln wird erkannt durch NEA An mit n + 1 Zuständen:


Jeder DEA, der Ln erkennt, hat mindestens 2n Zustände

TIMI

Hüllenbildung


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


TIMI

Kleene’sche Hülle


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


TIMI

Reguläre Ausdrücke


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


TIMI

Regeln zum Vereinfachen



  • 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

Ausdrucksst¨arke


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






TIMI

            

                                                           

Berechenbare Funktionen

                                               


       

            

                                                           

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.

                                               


           

TIMI

            

                                                           

Turing-Maschine: Definition

                                               


           

            

                                                           

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)

                                               


           

TIMI

            

                                                           

Konfigurationen

                                               


           

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

 

Melde dich jetzt kostenfrei an um alle Karteikarten und Zusammenfassungen für TIMI an der LMU München zu sehen

Singup Image Singup Image
Wave

Andere Kurse aus deinem Studiengang

Für deinen Studiengang TIMI an der LMU München gibt es bereits viele Kurse auf StudySmarter, denen du beitreten kannst. Karteikarten, Zusammenfassungen und vieles mehr warten auf dich.

Zurück zur LMU München Übersichtsseite

Betriebssysteme

Datenbanksysteme

rechnernetze

UX II

Was ist StudySmarter?

Was ist StudySmarter?

StudySmarter ist eine intelligente Lernapp für Studenten. Mit StudySmarter kannst du dir effizient und spielerisch Karteikarten, Zusammenfassungen, Mind-Maps, Lernpläne und mehr erstellen. Erstelle deine eigenen Karteikarten z.B. für TIMI an der LMU München oder greife auf tausende Lernmaterialien deiner Kommilitonen zu. Egal, ob an deiner Uni oder an anderen Universitäten. Hunderttausende Studierende bereiten sich mit StudySmarter effizient auf ihre Klausuren vor. Erhältlich auf Web, Android & iOS. Komplett kostenfrei. Keine Haken.

Awards

Bestes EdTech Startup in Deutschland

Awards
Awards

European Youth Award in Smart Learning

Awards
Awards

Bestes EdTech Startup in Europa

Awards
Awards

Bestes EdTech Startup in Deutschland

Awards
Awards

European Youth Award in Smart Learning

Awards
Awards

Bestes EdTech Startup in Europa

Awards

So funktioniert's

Top-Image

Individueller Lernplan

StudySmarter erstellt dir einen individuellen Lernplan, abgestimmt auf deinen Lerntyp.

Top-Image

Erstelle Karteikarten

Erstelle dir Karteikarten mit Hilfe der Screenshot-, und Markierfunktion, direkt aus deinen Inhalten.

Top-Image

Erstelle Zusammenfassungen

Markiere die wichtigsten Passagen in deinen Dokumenten und bekomme deine Zusammenfassung.

Top-Image

Lerne alleine oder im Team

StudySmarter findet deine Lerngruppe automatisch. Teile deine Lerninhalte mit Freunden und erhalte Antworten auf deine Fragen.

Top-Image

Statistiken und Feedback

Behalte immer den Überblick über deinen Lernfortschritt. StudySmarter führt dich zur Traumnote.

1

Lernplan

2

Karteikarten

3

Zusammenfassungen

4

Teamwork

5

Feedback