Grundlagen der Theoretischen Informatik at Universität Koblenz-Landau

Flashcards and summaries for Grundlagen der Theoretischen Informatik at the Universität Koblenz-Landau

Arrow Arrow

It’s completely free

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

Study with flashcards and summaries for the course Grundlagen der Theoretischen Informatik at the Universität Koblenz-Landau

Exemplary flashcards for Grundlagen der Theoretischen Informatik at the Universität Koblenz-Landau on StudySmarter:

Welche Operationen auf Wörtern gibt es?

Exemplary flashcards for Grundlagen der Theoretischen Informatik at the Universität Koblenz-Landau on StudySmarter:

Welche Operationen auf Sprachen gibt es?

Exemplary flashcards for Grundlagen der Theoretischen Informatik at the Universität Koblenz-Landau on StudySmarter:

Was sind reguläre Ausdrücke?

Exemplary flashcards for Grundlagen der Theoretischen Informatik at the Universität Koblenz-Landau on StudySmarter:

Wie ist eine Grammatik aufgebaut?

Exemplary flashcards for Grundlagen der Theoretischen Informatik at the Universität Koblenz-Landau on StudySmarter:

Was ist eine Dycksprache?

Exemplary flashcards for Grundlagen der Theoretischen Informatik at the Universität Koblenz-Landau on StudySmarter:

Wie ist die Chomsky-Hierarchie?

Exemplary flashcards for Grundlagen der Theoretischen Informatik at the Universität Koblenz-Landau on StudySmarter:

Welchen Regeln folgt eine rechtslineare Grammatik?

Exemplary flashcards for Grundlagen der Theoretischen Informatik at the Universität Koblenz-Landau on StudySmarter:

Welchen Regeln folgt eine kontextfreie Grammatik?

Exemplary flashcards for Grundlagen der Theoretischen Informatik at the Universität Koblenz-Landau on StudySmarter:

Welchen Regeln folgt eine kontextsensitive Grammatik?

Exemplary flashcards for Grundlagen der Theoretischen Informatik at the Universität Koblenz-Landau on StudySmarter:

Welchen Regeln folgt eine beschränkte Grammatik?

Exemplary flashcards for Grundlagen der Theoretischen Informatik at the Universität Koblenz-Landau on StudySmarter:

Was ist ein determinierter endlicher Automat?

Exemplary flashcards for Grundlagen der Theoretischen Informatik at the Universität Koblenz-Landau on StudySmarter:

Was ist ein indeterminierter endlicher Automat?

Your peers in the course Grundlagen der Theoretischen Informatik at the Universität Koblenz-Landau create and share summaries, flashcards, study plans and other learning materials with the intelligent StudySmarter learning app.

Get started now!

Flashcard Flashcard

Exemplary flashcards for Grundlagen der Theoretischen Informatik at the Universität Koblenz-Landau on StudySmarter:

Grundlagen der Theoretischen Informatik

Welche Operationen auf Wörtern gibt es?

  • Verknüpfung (Konkatenation):
    • w ◦ w′
    • assoziativ, oft geschrieben als ww′
  • i-te Potenz:
    • w^0 = ε, w^i+1 = ww^i
  • Reverse:
    • w^R = das Wort w rückwärts

Grundlagen der Theoretischen Informatik

Welche Operationen auf Sprachen gibt es?

  • Konkatenation:
    • L ◦ M = {w ◦ w′ | w ∈ L, w′ ∈ M}
    • oft geschrieben als LM
  • i-te Potenz:
    • L^0 = {ε},
    • L^i+1 := LL^i
  • Reverse:
    • L^R = {w^R | w ∈ L}
  • Kleene-Hülle
    • L^∗ = L^0 ∪ L^1 ∪ L^2 ∪ . . .
  • Variante:
    • L^+ = LL^∗ = L^1 ∪ L^2 ∪ . . .

Grundlagen der Theoretischen Informatik

Was sind reguläre Ausdrücke?

Menge RegΣ der regulären Ausdrücke (über Σ) ist definiert durch:

  1. 0 ist ein regulärer Ausdruck
  2. Für jedes a ∈ Σ ist a ein regulärer Ausdruck
  3. Sind r und s reguläre Ausdrücke, so auch
    • (r + s) (Vereinigung),
    • (rs) (Konkatenation),
    • (r∗) (Kleene Stern)

Klammern können weggelassen werden, dann

  • ∗ hat Vorrang vor Konkatenation
  • Konkatenation hat Vorrang vor +

Grundlagen der Theoretischen Informatik

Wie ist eine Grammatik aufgebaut?

Eine Grammatik G über einem Alphabet Σ ist ein Tupel
G = (V, T, R, S)
Dabei ist
• V eine endliche Menge von Variablen
• T ⊆ Σ eine endliche Menge von Terminalen mit V ∩ T = ∅
• R eine endliche Menge von Regeln
• S ∈ V das Startsymbol

Grundlagen der Theoretischen Informatik

Was ist eine Dycksprache?

Die Dycksprache Dk ist die kleinste Menge, die folgende Bedingungen erfüllt:
1. epsilon ∈ Dk,
2. Falls w ∈ Dk, so auch xiw(xi)^_ .
3. Falls u, v ∈ Dk, so auch uv.

Grundlagen der Theoretischen Informatik

Wie ist die Chomsky-Hierarchie?

Klasse L_3, REG (regulär) = {L(G)|G ist rechtslinear}

Klasse L_2, CFL (kontextfrei) = {L(G)| G ist kontextfrei}

Klasse L_1, CSL (kontextsensitiv) = {L(G)|G ist kontextsensitiv}

Klasse L_1, CSL (beschränkt) = {L(G)|G ist beschränkt}

Klasse L_0, r.e. (aufzählbar) = {L(G)|G beliebig}

Klasse L (beliebige Sprache) = {L|L⊆ Σ^∗}

Grundlagen der Theoretischen Informatik

Welchen Regeln folgt eine rechtslineare Grammatik?

G = (V, T, R, S) rechtslinear <-> "füralle"(P → Q) ∈ R (P ∈ V und Q ∈ T∗ ∪ T^+ V) ==>

  • Links eine einzelne Variable
  • Rechts höchstens eine Variable
  • Wenn rechts eine Variable steht, steht sie ganz rechts im Wort und das Wort enthält mindestens ein Terminalsymbol

Grundlagen der Theoretischen Informatik

Welchen Regeln folgt eine kontextfreie Grammatik?

G = (V, T, R, S) kontextfrei <-> "für alle"(P → Q) ∈ R (P ∈ V und Q ∈ (V ∪ T)^∗)==>

  • Links eine einzelne Variable
  • Die Prämisse macht keine Aussage, was der Kontext dieser Variablen ist(”kontextfrei“)
  • Rechts steht etwas beliebiges

Grundlagen der Theoretischen Informatik

Welchen Regeln folgt eine kontextsensitive Grammatik?

G = (V, T, R, S) kontextsensitiv <-> "für alle"(P → Q) ∈ R:

  1. "es gibt" u, v, α ∈ (V∪T)^∗ "es gibt"A ∈ V (P = uAv und Q = uαv mit |α| ≥ 1)  oder S → ε
  2. S nicht in Q ==>
  • Eine Variable A wird in einen String α mit |α| ≥ 1 überführt
  • Die Ersetzung von A durch α findet nur statt, wenn der in der Regel geforderte Kontext (u und v) vorhanden ist
  • Das Wort wird nicht kürzer, außer bei ε ∈ L

Grundlagen der Theoretischen Informatik

Welchen Regeln folgt eine beschränkte Grammatik?

G = (V, T, R, S) beschränkt <-> "füralle" (P → Q) ∈ R:

  1. |P| ≤ |Q|, oder S → ε
  2. S nicht in Q ==>
  • Die Conclusio ist mindestens so lang wie die Prämisse, außer bei ε ∈ L.
  • Das Wort wird nicht kürzer, außer bei ε ∈ L

Grundlagen der Theoretischen Informatik

Was ist ein determinierter endlicher Automat?

Ein endlicher Automat ist ein Tupel
A = (K, Σ, δ, s_0, F)

  • K endliche Menge von Zuständen,
  • Σ endliches Alphabet,
  • δ : K ×Σ → K Übergangsfunktion,
  • s_0 ∈ K Startzustand
  • F ⊆ K Menge der finalen Zustände.

Grundlagen der Theoretischen Informatik

Was ist ein indeterminierter endlicher Automat?

Ein indeterminierter endlicher Automat (NDEA) ist ein Tupel A = (K, Σ,∆, I, F)

  • K endliche Menge von Zuständen,
  • Σ endliches Alphabet,
  • ∆ ⊆ (K × Σ) ×K Übergangsrelation,
  • I ⊆ K  Menge von Startzuständen,
  • F ⊆ K Menge von finalen Zuständen.

Sign up for free to see all flashcards and summaries for Grundlagen der Theoretischen Informatik at the Universität Koblenz-Landau

Singup Image Singup Image
Wave

Other courses from your degree program

For your degree program Grundlagen der Theoretischen Informatik at the Universität Koblenz-Landau there are already many courses on StudySmarter, waiting for you to join them. Get access to flashcards, summaries, and much more.

Back to Universität Koblenz-Landau overview page

Grundlagen der Softwaretechnik

Grundlagen der IT-Sicherheit

Programmierung und Modellierung

Programierpraktikum

Grundlagen der Funktionalen Programmierung

What is StudySmarter?

What is StudySmarter?

StudySmarter is an intelligent learning tool for students. With StudySmarter you can easily and efficiently create flashcards, summaries, mind maps, study plans and more. Create your own flashcards e.g. for Grundlagen der Theoretischen Informatik at the Universität Koblenz-Landau or access thousands of learning materials created by your fellow students. Whether at your own university or at other universities. Hundreds of thousands of students use StudySmarter to efficiently prepare for their exams. Available on the Web, Android & iOS. It’s completely free.

Awards

Best EdTech Startup in Europe

Awards
Awards

EUROPEAN YOUTH AWARD IN SMART LEARNING

Awards
Awards

BEST EDTECH STARTUP IN GERMANY

Awards
Awards

Best EdTech Startup in Europe

Awards
Awards

EUROPEAN YOUTH AWARD IN SMART LEARNING

Awards
Awards

BEST EDTECH STARTUP IN GERMANY

Awards