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!
Grundlagen der Theoretischen Informatik
Wie sind Gödelnummern von DTMs definiert?
DTMs werden als Gödelzahlen kodiert:
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
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)
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) ==>
Grundlagen der Theoretischen Informatik
Was sind reguläre Ausdrücke?
Menge RegΣ der regulären Ausdrücke (über Σ) ist definiert durch:
Klammern können weggelassen werden, dann
Grundlagen der Theoretischen Informatik
Welchen Regeln folgt eine beschränkte Grammatik?
G = (V, T, R, S) beschränkt <-> "füralle" (P → Q) ∈ R:
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:
Grundlagen der Theoretischen Informatik
Was ist ein indeterminierter endlicher Automat?
Ein indeterminierter endlicher Automat (NDEA) ist ein Tupel A = (K, Σ,∆, I, F)
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)^∗)==>
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 pageCheck out courses similar to Grundlagen der Theoretischen Informatik at other universities
Back to Universität Koblenz-Landau overview pageStudySmarter 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.
Best EdTech Startup in Europe
Already registered? Just go to Login