Clear
NrSubjectsTypeTaskDifficultyCreditsTagsFlagsNote
1Theoretical computer scienceNameEs sei die akzeptierende Turing-Maschine ´M = ({a,b,c}, Z, z\_0, {q\_1, q\_2}, …0.6
6hpituring machineHPI, 2014-04-01, Theoretische Informatik 2, Aufgabe 1
2Theoretical computer scienceNameGib eine akzeptierende Turing-Maschine an, die die Sprache ´{a^(2^n) | n >= 0}´ …0.6
4hpituring machineHPI, 2014-04-01, Theoretische Informatik 2, Aufgabe 2
3Theoretical computer scienceNameGib eine akzeptierende Turing-Maschine an, die die Sprache ´{a^n b^n c^n | n >= …0.6
6hpituring machineHPI, 2014-04-01, Theoretische Informatik 2, Aufgabe 3
4Theoretical computer scienceDrawGegeben ist folgender deterministischer endliche Automat: ´A = ({a, b, c}, {z_0…0.6
6hpideterministic finite automatonHPI, 2014-04-12, Theoretische Informatik 2, Blatt 2, Aufgabe 1
5Theoretical computer scienceNameGib deterministische endliche Automaten an, die folgende Sprachen über dem Alpha…0.6
9hpideterministic finite automatonHPI, 2014-04-12, Theoretische Informatik 2, Blatt 2, Aufgabe 2
6Theoretical computer scienceNameGegeben ist der nichtdeterministische endliche Automat ´A = ({a, b}, {q_0, q_1,…0.6
9hpinondeterministic finite automatonHPI, 2014-04-12, Theoretische Informatik 2, Blatt 2, Aufgabe 3
7Theoretical computer scienceNameGegeben sei die reguläre Grammatik ´G = ({S, A_1, A_2, A_3}, {a, b, c}, P, S)´ …0.5
5hpideterministic finite automatonHPI, 2014-04-12, Theoretische Informatik 2, Blatt 2, Aufgabe 4
8Theoretical computer scienceNameGegeben sei folgender endlicher Automat: ´A = ({a, b, c}, {z_0, z_1, z_2, z_3},…0.5
4hpifinite automatonregular grammarHPI, 2014-04-12, Theoretische Informatik 2, Blatt 2, Aufgabe 5
9Theoretical computer scienceNameGib einen Kellerautomaten an, der folgende Sprache akzeptiert: ´L = {w in {a, b…0.5
4hpipushdown automatonHPI, 2014-04-26, Theoretische Informatik 2, Blatt 3, Aufgabe 1
10Theoretical computer scienceNameGib einen Kellerautomaten an, der folgende Sprache akzeptiert: ´L = {a^m b^n in…0.6
4hpipushdown automatonHPI, 2014-04-26, Theoretische Informatik 2, Blatt 3, Aufgabe 2
11Theoretical computer scienceNameEs sei folgender Kellerautomat gegeben: ´M = ({a, b}, {z_0, z_1}, {a}, z_0, {z_…0.5
3hpipushdown automatonHPI, 2014-04-26, Theoretische Informatik 2, Blatt 3, Aufgabe 3
12Theoretical computer scienceNameEs sei ´G = ({S,B,U}, {a,b}, R, S)´ eine kontextfreie Grammatik mit ´R = {S -> …0.6
8hpipushdown automatoncontext-free grammarHPI, 2014-04-29, Theoretische Informatik 2, Blatt 4, Aufgabe 1
13Theoretical computer scienceProofBeweise, dass für jede reguläre Sprache ´L sube T^(\*\*)´ und jeden Buchstaben ´…0.7
5hpiregular languageHPI, 2014-04-29, Theoretische Informatik 2, Blatt 4, Aufgabe 2
14Theoretical computer scienceProofBeweise, dass für jede reguläre Sprache ´L sube T^(\*\*)´ und jeden Buchstaben ´…0.7
6hpiregular languageHPI, 2014-04-29, Theoretische Informatik 2, Blatt 4, Aufgabe 3
15Theoretical computer scienceProofBeweise, dass für jede kontextfreie Sprache ´L sube T^+´ und jeden Buchstaben ´a…0.7
5hpicontext-free languageHPI, 2014-04-29, Theoretische Informatik 2, Blatt 4, Aufgabe 4
16Theoretical computer scienceProofEine kontextfreie Grammatik ´G = (N, T, P, S)´ heißt linear, wenn alle Regeln au…0.8
5hpicontext-free languageHPI, 2014-05-07, Theoretische Informatik 2, Blatt 5, Aufgabe 1
17Theoretical computer scienceProofUntersuche, ob die Menge der linearen Sprachen unter Vereinigung, Durchschnitt, …0.7
4hpilinear languageHPI, 2014-05-07, Theoretische Informatik 2, Blatt 5, Aufgabe 2
18Theoretical computer scienceExplainUntersuche, ob die Menge der rekursiven Sprachen (für die es eine Turing- Maschi…0.7
4hpirecursive languageHPI, 2014-05-07, Theoretische Informatik 2, Blatt 5, Aufgabe 3
19Theoretical computer scienceName1. Bestimme die den folgenden Mengen zugeordneten regulären Ausdrücke: - Alle …0.5
5hpiregular expressionHPI, 2014-05-13, Theoretische Informatik 2, Blatt 6, Aufgabe 1
20Theoretical computer scienceNameBestimme nach der im Beweis des Satzes von Kleene gegebenen Methode zu folgendem…0.6
4hpiregular expressionfinite automatonHPI, 2014-05-13, Theoretische Informatik 2, Blatt 6, Aufgabe 2
21Theoretical computer scienceNameBestimme für den regulären Ausdruck ´(((a + b)^(\*\*) \* (b \* b)) + a^(\*\*))´ …0.6
4hpiregular expressionregular grammarHPI, 2014-05-13, Theoretische Informatik 2, Blatt 6, Aufgabe 3
22Theoretical computer scienceAssignGegeben seien die Grammatik ´G = ({S, A, B, C}, {a, b}, P, S)´ mit ´P = {´ ´S…0.6
6hpicyk algorithmHPI, 2014-05-20, Theoretische Informatik 2, Blatt 7, Aufgabe 1
23Theoretical computer scienceExplainDas Inklusionsproblem ist folgendermaßen definiert: Gegeben: Grammatiken ´G_1´ …0.7
4hpiinklusionsproblemHPI, 2014-05-20, Theoretische Informatik 2, Blatt 7, Aufgabe 2
24Theoretical computer scienceNameEs sei die deterministische akzeptierende 1-Band-Turing-Maschine M gegeben, die …0.6
7hpituring machinedeterministic turing machinetime complexityspace complexityHPI, 2014-05-26, Theoretische Informatik 2, Blatt 8, Aufgabe 1
25Theoretical computer scienceCalculateEs sei folgende deterministische akzeptierende Turing-Maschine gegeben: ´M = ({…0.7
8hpituring machinedeterministic turing machinetime complexityspace complexityHPI, 2014-05-26, Theoretische Informatik 2, Blatt 8, Aufgabe 2
26Theoretical computer scienceNameEs sei die deterministische akzeptierende 1-Band-Turing-Maschine M gegeben, die …0.8
4hpideterministicturing machineHPI, 2014-06-12, Theoretische Informatik 2, Blatt 9, Aufgabe 1
27Theoretical computer scienceCalculateEs sei folgende deterministische akzeptierende Turing-Maschine gegeben: ´M = ({…0.6
3hpideterministic turing machineturing machineHPI, 2014-06-12, Theoretische Informatik 2, Blatt 9, Aufgabe 2
28Theoretical computer scienceCalculateGegeben ist ein Graph ´G = (V, E)´. Eine Überdeckung von ´G´ ist eine Menge ´V'…0.6
5hpigraphgraph coloringclique problemHPI, 2014-06-12, Theoretische Informatik 2, Blatt 9, Aufgabe 3
29Theoretical computer scienceProofBeweise, dass das 3-SAT Problem NP-vollständig ist. **Gegeben:** ´n´ Variable ´…0.7
5hpi3-satnp-completeHPI, 2014-06-20, Theoretische Informatik 2, Blatt 10, Aufgabe 1
30Theoretical computer scienceProofZeige, dass es genau dann einen polynomialen Algorithmus für das Cliquenproblem …0.6
3hpiclique problemHPI, 2014-06-20, Theoretische Informatik 2, Blatt 10, Aufgabe 2
31Theoretical computer scienceProofZeige, dass das Äquivalenzproblem für kontextfreie Grammatiken auf das Leerheits…0.6
3hpicontext-free grammarnoncontracting grammarHPI, 2014-06-20, Theoretische Informatik 2, Blatt 10, Aufgabe 3
32Theoretical computer scienceProofEs sei ´L sube {a}^\*\*´ eine nichtleere reguläre Sprache. Beweise, dass es natü…0.6
4hpiregular languageHPI, 2014-06-26, Theoretische Informatik 2, Blatt 11, Aufgabe 1
33Theoretical computer scienceAssignUntersuche mittels des Satzes von Myhill/Nerode, ob die folgenden Sprachen regul…0.7
6hpimyhill–nerode theoremregular languageHPI, 2014-06-26, Theoretische Informatik 2, Blatt 11, Aufgabe 2
34Theoretical computer scienceExplainZeige, dass das Problem der Existenz eines Hamiltonkreises für gerichtete Graphe…0.7
4hpihamiltonian pathHPI, 2014-06-26, Theoretische Informatik 2, Blatt 11, Aufgabe 3
35Theoretical computer scienceTransformGegeben sei der deterministische endliche Automat ´A = ({a, b}, {z\_0, z\_1, z\…0.7
4hpideterministic finite automatonHPI, 2014-07-03, Theoretische Informatik 2, Blatt 12, Aufgabe 1
36Theoretical computer scienceNameEs sei ´L = {aw | w in {a,b}^\*\* ,|w| " ist gerade"}´ Bestimme ´z(L)´.…0.6
3hpiregular languageHPI, 2014-07-03, Theoretische Informatik 2, Blatt 12, Aufgabe 2
37Theoretical computer scienceProof1. Beweise, dass für jede reguläre unäre Sprache ´L´ (unär heißt, dass ´L´ eine …0.8
6hpiregular languageHPI, 2014-07-03, Theoretische Informatik 2, Blatt 12, Aufgabe 3