Theoretische Informatik an der Universität Tübingen

Karteikarten und Zusammenfassungen für Theoretische Informatik an der Universität Tübingen

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

Beispielhafte Karteikarten für Theoretische Informatik an der Universität Tübingen auf StudySmarter:

Reguläre Ausdrücke 
Menge Reg(Σ)

Beispielhafte Karteikarten für Theoretische Informatik an der Universität Tübingen auf StudySmarter:

Was bedeuten diese Symbole:

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

Beispielhafte Karteikarten für Theoretische Informatik an der Universität Tübingen auf StudySmarter:

Sei G = (V, Σ, P, S):

Typ 1 Grammatik (monoton bzw. kontextsensitiv)

Das war nur eine Vorschau der Karteikarten auf StudySmarter.
Flascard Icon Flascard Icon

Über 50 Mio Karteikarten von Schülern erstellt

Flascard Icon Flascard Icon

Erstelle eigene Karteikarten in Rekordzeit

Flascard Icon Flascard Icon

Kostenlose Karteikarten zu STARK Inhalten

Kostenlos anmelden

Beispielhafte Karteikarten für Theoretische Informatik an der Universität Tübingen auf StudySmarter:

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

Konkatenation

Beispielhafte Karteikarten für Theoretische Informatik an der Universität Tübingen auf StudySmarter:

Wie können Ableitungen enden?

Beispielhafte Karteikarten für Theoretische Informatik an der Universität Tübingen auf StudySmarter:

Wie ist die Produktion einer Grammatik aufgebaut?

Beispielhafte Karteikarten für Theoretische Informatik an der Universität Tübingen auf StudySmarter:

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

Was bedeutet ⇒G ?

Das war nur eine Vorschau der Karteikarten auf StudySmarter.
Flascard Icon Flascard Icon

Über 50 Mio Karteikarten von Schülern erstellt

Flascard Icon Flascard Icon

Erstelle eigene Karteikarten in Rekordzeit

Flascard Icon Flascard Icon

Kostenlose Karteikarten zu STARK Inhalten

Kostenlos anmelden

Beispielhafte Karteikarten für Theoretische Informatik an der Universität Tübingen auf StudySmarter:

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

Was ist das Produkt RR' ?


Beispielhafte Karteikarten für Theoretische Informatik an der Universität Tübingen auf StudySmarter:

Produktion aus P

Beispielhafte Karteikarten für Theoretische Informatik an der Universität Tübingen auf StudySmarter:

Satzform

Beispielhafte Karteikarten für Theoretische Informatik an der Universität Tübingen auf StudySmarter:

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

Äquivalenzrelation


Das war nur eine Vorschau der Karteikarten auf StudySmarter.
Flascard Icon Flascard Icon

Über 50 Mio Karteikarten von Schülern erstellt

Flascard Icon Flascard Icon

Erstelle eigene Karteikarten in Rekordzeit

Flascard Icon Flascard Icon

Kostenlose Karteikarten zu STARK Inhalten

Kostenlos anmelden

Beispielhafte Karteikarten für Theoretische Informatik an der Universität Tübingen auf StudySmarter:

Grammatik G

Kommilitonen im Kurs Theoretische Informatik an der Universität Tübingen. 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 Theoretische Informatik an der Universität Tübingen auf StudySmarter:

Theoretische Informatik

Reguläre Ausdrücke 
Menge Reg(Σ)

Kleinste Menge mit:

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

Theoretische Informatik

Was bedeuten diese Symbole:

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

  • ε = 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 ∅ ≠ {ε}

Theoretische Informatik

Sei G = (V, Σ, P, S):

Typ 1 Grammatik (monoton bzw. kontextsensitiv)

falls |l| ≤ |r| für alle Produktionen (l → r) ∈ P gilt

Theoretische Informatik

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

Konkatenation

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

Theoretische Informatik

Wie können Ableitungen enden?

  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

Wie ist die Produktion einer Grammatik aufgebaut?

linke Seiterechte Seite

Es können zwei Typen sein:

  1. Nicht-Terminal (Variablen)
  2. Terminal ('eigentliche' Symbole)

Theoretische Informatik

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

Was bedeutet ⇒G ?

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

Theoretische Informatik

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

Was ist das Produkt RR' ?


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

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

Theoretische Informatik

Produktion aus P

Ist ein Paar (l,r) von Wörtern  über V ∪ Σ (geschrieben: l → r )

Es gilt: l,r bestehen aus Nicht-terminale (großgeschrieben) Terminalsymbole (kleingeschrieben)

Theoretische Informatik

Satzform

Wort aus (V ∪ Σ)*

Theoretische Informatik

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

Äquivalenzrelation


  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

Theoretische Informatik

Grammatik G

4-Tupel G = (V, Σ, P, S):

  1. V ist Alphabet (Nicht-Terminale)
  2. Σ ist Alphabet (Terminale)
  3. P ⊆ (V ∪ Σ)+ × (V ∪ Σ)* ist endliche Menge von Produktionen
  4. S ∈ V ist die Startvariable (Axiom)

Melde dich jetzt kostenfrei an um alle Karteikarten und Zusammenfassungen für Theoretische Informatik an der Universität Tübingen zu sehen

Singup Image Singup Image
Wave

Andere Kurse aus deinem Studiengang

Für deinen Studiengang Theoretische Informatik an der Universität Tübingen gibt es bereits viele Kurse auf StudySmarter, denen du beitreten kannst. Karteikarten, Zusammenfassungen und vieles mehr warten auf dich.

Zurück zur Universität Tübingen Übersichtsseite

theoretische Informatik

Robotik

Informatik der Systeme

Grundlagen des Internets

Software Engineering

Theoretische Informatik

Einführung in die theoretische Informatik an der

TU München

Theoretische Informatik III an der

Universität Stuttgart

theoretische Grundlagen der Informatik an der

Hochschule für Wirtschaft und Recht Berlin

Theoretische Informatik I an der

Duale Hochschule Baden-Württemberg

Theorethische Informatik 3 (Arras) an der

Duale Hochschule Baden-Württemberg

Ähnliche Kurse an anderen Unis

Schau dir doch auch Theoretische Informatik an anderen Unis an

Zurück zur Universität Tübingen Übersichtsseite

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

StudySmarter - Die Lernplattform für Studenten

StudySmarter

4.5 Stars 1100 Bewertungen
Jetzt entdecken
X

Gute Noten in der Uni? Kein Problem mit StudySmarter!

89% der StudySmarter Nutzer bekommen bessere Noten in der Uni.

50 Mio Karteikarten & Zusammenfassungen
Erstelle eigene Lerninhalte mit Smart Tools
Individueller Lernplan & Statistiken


Lerne mit über 1 Millionen Nutzern in der kostenlosen StudySmarter App.

Du bist schon registriert? Hier geht‘s zum Login