Select your language

Suggested languages for you:
Login Anmelden

Lernmaterialien für Theoretische Informatik an der Universität Tübingen

Greife auf kostenlose Karteikarten, Zusammenfassungen, Übungsaufgaben und Altklausuren für deinen Theoretische Informatik Kurs an der Universität Tübingen zu.

TESTE DEIN WISSEN

Reguläre Ausdrücke 
Menge Reg(Σ)

Lösung anzeigen
TESTE DEIN WISSEN

Kleinste Menge mit:

  • ∅,ε  ∈ Reg(Σ), Σ ⊆ Reg(Σ)
  • Wenn α, β ∈ Reg(Σ), dann auch αβ, (α|β), (α)∗ ∈ Reg(Σ)
Lösung ausblenden
TESTE DEIN WISSEN

Sei Σ ein Alphabet.

(endliches) Wort


Lösung anzeigen
TESTE DEIN WISSEN

(eventuell leere) Folge w = a1a2 . . . an von Symbolen ai ∈ Σ

Beispiel:

Sei Σ = {0, 1}. Wörter: ε, 0, 1, 00, 01, ...

Sei Σ = {a, b, c}. Wörter: 

ε, a, b, c, aa, abc, ac, ba, bb, bc, ca, cb, cc

Lösung ausblenden
TESTE DEIN WISSEN

kontextfreie Grammatik

Lösung anzeigen
TESTE DEIN WISSEN

linken Seite: Genau 1 Nicht-Terminal

Lösung ausblenden
TESTE DEIN WISSEN

Ist Ableiten ein deterministischer  oder ein nicht-deterministischer Prozess?

Lösung anzeigen
TESTE DEIN WISSEN

Nicht-deterministisch:

Für ein u ∈ (V ∪ Σ)* kann es entweder gar kein, ein oder mehrere v geben mit u ⇒G v.

⇒G ist KEINE Funktion

Lösung ausblenden
TESTE DEIN WISSEN

 Sei Menge M, Relationen R, R' ⊆ M ×M:

Was ist das Produkt RR' ?


Lösung anzeigen
TESTE DEIN WISSEN

RR' := {(x, z) ∈ M ×M|

∃y∈M (x, y) ∈ R ∧ (y, z) ∈ R'}

Lösung ausblenden
TESTE DEIN WISSEN

Sei w = a1a2 . . . an und x = b1b2 . . . bm Wörter über Σ:

Konkatenation

Lösung anzeigen
TESTE DEIN WISSEN
  1. wx = a1a2 . . . anb1b2 . . . bm
  2. εw = wε = w
  3. x^n = xxx . . . x (n-mal)
Lösung ausblenden
TESTE DEIN WISSEN

Was bedeuten diese Symbole:

ε, |w|, Σ∗, Σ+, ∅

Lösung anzeigen
TESTE DEIN WISSEN
  • ε = das leere Wort
  • |w| = n (Länge des Wortes w)
  • Σ* = Menge aller endlichen Wörter über Σ
  • Σ+ = Σ∗ \ {ε} (Menge aller nicht-leeren Wörter)
  • = die leere Sprache ∅ ≠ {ε}
Lösung ausblenden
TESTE DEIN WISSEN

Monoid

Lösung anzeigen
TESTE DEIN WISSEN

Die algebraische Struktur (Σ, ◦) eine Halbgruppe mit neutralem Element,

Lösung ausblenden
TESTE DEIN WISSEN

Satzform

Lösung anzeigen
TESTE DEIN WISSEN

Wort aus (V ∪ Σ)*

Lösung ausblenden
TESTE DEIN WISSEN

Sei x,y,z ∈ Menge M und R(~) Relation:

Äquivalenzrelation


Lösung anzeigen
TESTE DEIN WISSEN
  1. reflexiv: ∀x∈ M: x ~ x
  2. symmetrisch: ∀x,y ∈ M: 
    x ~ y ⇔ y ~ x
  3. transitiv: ∀x,y,z ∈ M: 
    x ~ y ∧ y ~ z ⇒ x ~ z

⇒ zerlegt M in disjunkte Klassen

Lösung ausblenden
TESTE DEIN WISSEN

Sei G = (V, Σ, P, S) eine Grammatik und seien u, v ∈ (V ∪ Σ)*:

Was bedeutet ⇒G ?

Lösung anzeigen
TESTE DEIN WISSEN

Falls Produktion (l → r) ∈ P und Wörter x, y ∈ (V ∪ Σ)* existieren mit u = xly und v = xry

u ⇒G v (u geht unter G unmittelbar über in v),

Lösung ausblenden
TESTE DEIN WISSEN

Wie können Ableitungen enden?

Lösung anzeigen
TESTE DEIN WISSEN
  1. Wort
  2. Kein Wort (ewig lange Ableitungen):
    S ⇒ aSBC ⇒ aaSBCBC ⇒ aaaSBCBCBC ⇒ . . .
  3. Sackgasse (keine Regel mehr anwendbar):
    S ⇒ aSBC ⇒ aaBCBC ⇒ aabCBC ⇒ aabcBC ⇏ 
Lösung ausblenden
  • 294599 Karteikarten
  • 3546 Studierende
  • 103 Lernmaterialien

Beispielhafte Karteikarten für deinen Theoretische Informatik Kurs an der Universität Tübingen - von Kommilitonen auf StudySmarter erstellt!

Q:

Reguläre Ausdrücke 
Menge Reg(Σ)

A:

Kleinste Menge mit:

  • ∅,ε  ∈ Reg(Σ), Σ ⊆ Reg(Σ)
  • Wenn α, β ∈ Reg(Σ), dann auch αβ, (α|β), (α)∗ ∈ Reg(Σ)
Q:

Sei Σ ein Alphabet.

(endliches) Wort


A:

(eventuell leere) Folge w = a1a2 . . . an von Symbolen ai ∈ Σ

Beispiel:

Sei Σ = {0, 1}. Wörter: ε, 0, 1, 00, 01, ...

Sei Σ = {a, b, c}. Wörter: 

ε, a, b, c, aa, abc, ac, ba, bb, bc, ca, cb, cc

Q:

kontextfreie Grammatik

A:

linken Seite: Genau 1 Nicht-Terminal

Q:

Ist Ableiten ein deterministischer  oder ein nicht-deterministischer Prozess?

A:

Nicht-deterministisch:

Für ein u ∈ (V ∪ Σ)* kann es entweder gar kein, ein oder mehrere v geben mit u ⇒G v.

⇒G ist KEINE Funktion

Q:

 Sei Menge M, Relationen R, R' ⊆ M ×M:

Was ist das Produkt RR' ?


A:

RR' := {(x, z) ∈ M ×M|

∃y∈M (x, y) ∈ R ∧ (y, z) ∈ R'}

Mehr Karteikarten anzeigen
Q:

Sei w = a1a2 . . . an und x = b1b2 . . . bm Wörter über Σ:

Konkatenation

A:
  1. wx = a1a2 . . . anb1b2 . . . bm
  2. εw = wε = w
  3. x^n = xxx . . . x (n-mal)
Q:

Was bedeuten diese Symbole:

ε, |w|, Σ∗, Σ+, ∅

A:
  • ε = das leere Wort
  • |w| = n (Länge des Wortes w)
  • Σ* = Menge aller endlichen Wörter über Σ
  • Σ+ = Σ∗ \ {ε} (Menge aller nicht-leeren Wörter)
  • = die leere Sprache ∅ ≠ {ε}
Q:

Monoid

A:

Die algebraische Struktur (Σ, ◦) eine Halbgruppe mit neutralem Element,

Q:

Satzform

A:

Wort aus (V ∪ Σ)*

Q:

Sei x,y,z ∈ Menge M und R(~) Relation:

Äquivalenzrelation


A:
  1. reflexiv: ∀x∈ M: x ~ x
  2. symmetrisch: ∀x,y ∈ M: 
    x ~ y ⇔ y ~ x
  3. transitiv: ∀x,y,z ∈ M: 
    x ~ y ∧ y ~ z ⇒ x ~ z

⇒ zerlegt M in disjunkte Klassen

Q:

Sei G = (V, Σ, P, S) eine Grammatik und seien u, v ∈ (V ∪ Σ)*:

Was bedeutet ⇒G ?

A:

Falls Produktion (l → r) ∈ P und Wörter x, y ∈ (V ∪ Σ)* existieren mit u = xly und v = xry

u ⇒G v (u geht unter G unmittelbar über in v),

Q:

Wie können Ableitungen enden?

A:
  1. Wort
  2. Kein Wort (ewig lange Ableitungen):
    S ⇒ aSBC ⇒ aaSBCBC ⇒ aaaSBCBCBC ⇒ . . .
  3. Sackgasse (keine Regel mehr anwendbar):
    S ⇒ aSBC ⇒ aaBCBC ⇒ aabCBC ⇒ aabcBC ⇏ 
Theoretische Informatik

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 Theoretische Informatik an der Universität Tübingen

Für deinen Studiengang Theoretische Informatik an der Universität Tübingen 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 Theoretische Informatik Kurse im gesamten StudySmarter Universum

Theoretische Informatik III

Universität Stuttgart

Zum Kurs
Theoretische Informatik I

Duale Hochschule Baden-Württemberg

Zum Kurs

Die all-in-one Lernapp für Studierende

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