Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Diese Umfrage wurde während der Migration geschlossen.
O(n¹) Klausur regulär in O(n) gelöst
O(n²) Klausur kontextfrei, per CYK gelöst
O(n³) CYK-Tabelle vollständig ausgefüllt
O(4â¿) Klausur war NP-schwer
N(achklausur)SPACE Halteproblem auf mein Hirn reduziert.
da es die letzten Male Ungewissheiten zu dem Korrekturstand der Klausur “Berechenbarkeit und formale Sprachen” gab, gibt es ab sofort kostenlos einen neuen Enterprise-Service:
Bei Aufgabe 3b) sollte a_i ∈ {0,1}* dabeistehen und bei 3c) fehlen die {}-Klammern (z ∈ 0 1 * steht da).
Aufgabe 4a) der Übergang von q0 nach q1 war glaube ich eine 0 keine 1.
Aufgabe 2b) nicht y sollte eine Primzahl sein sondern |y|.