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:

Wie sind Gödelnummern von DTMs definiert?

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

Was ist eine Kettenproduktion?

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

Was ist Reduktion von Problemen?

This was only a preview of our StudySmarter flashcards.
Flascard Icon Flascard Icon

Millions of flashcards created by students

Flascard Icon Flascard Icon

Create your own flashcards as quick as possible

Flascard Icon Flascard Icon

Learning-Assistant with spaced repetition algorithm

Sign up for free!

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:

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:

Was sind reguläre Ausdrücke?

This was only a preview of our StudySmarter flashcards.
Flascard Icon Flascard Icon

Millions of flashcards created by students

Flascard Icon Flascard Icon

Create your own flashcards as quick as possible

Flascard Icon Flascard Icon

Learning-Assistant with spaced repetition algorithm

Sign up for free!

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 eine Dycksprache?

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:

Was ist ein indeterminierter endlicher Automat?

This was only a preview of our StudySmarter flashcards.
Flascard Icon Flascard Icon

Millions of flashcards created by students

Flascard Icon Flascard Icon

Create your own flashcards as quick as possible

Flascard Icon Flascard Icon

Learning-Assistant with spaced repetition algorithm

Sign up for free!

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

Welchen Regeln folgt eine kontextfreie Grammatik?

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

Wie sind Gödelnummern von DTMs definiert?

DTMs werden als Gödelzahlen kodiert:

  • DTMs können als Gödelwörter dargestellt werden.
    M 7→ a_i_1 . . . a_i_n
  • Die Buchstaben der Gödelwörter können in Ziffern kodiert werden,
    um Gödelnummern zu bekommen.
    a_i_1 ... a_i_n → p^i_1_1 ... p^i_n_n ∈ N p_i: i-te Primzahl
  • Notation: ˆg(M) für die Gödelnummer der DTM M.

Grundlagen der Theoretischen Informatik

Was ist eine Kettenproduktion?

Eine Regel der Form

A → B mit A, B ∈ V

Grundlagen der Theoretischen Informatik

Was ist Reduktion von Problemen?

Wir geben eine totale, berechenbare Funktion f an, die

  • eine Instanz p1 von P1
  • in eine Instanz p2 von P2 umwandelt,
  • und zwar so, dass die Antwort zu p1 "ja“ ist gdw die Antwort zu p2 ”ja” ist.

Wenn P1 unentscheidbar ist, dann ist auch P2 unentscheidbar.

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

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

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

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

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

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.

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

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

Datenbanken

Grundlagen der Technischen Informatik at

Universität Oldenburg

Grundlagen der Informatik at

Hochschule Ansbach

Mathematische Grundlagen der Informatik at

Hochschule Fulda

theoretische Grundlagen der Informatik at

Hochschule für Wirtschaft und Recht Berlin

Grundlagen der technischen Informatik at

Universität Jena

Similar courses from other universities

Check out courses similar to Grundlagen der Theoretischen Informatik at other universities

Back to Universität Koblenz-Landau overview page

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
X

StudySmarter - The study app for students

StudySmarter

4.5 Stars 1100 Rating
Start now!
X

Good grades at university? No problem with StudySmarter!

89% of StudySmarter users achieve better grades at university.

50 Mio Flashcards & Summaries
Create your own content with Smart Tools
Individual Learning-Plan

Learn with over 1 million users on StudySmarter.

Already registered? Just go to Login