Theoretische Informatik:Klausur

Klausur vom 8.2.2007

zur Diskussionsanregung meine Antworten (kein Anspruch auf Korrektheit)

2 Gruppen:

• mit Aufgabe zur "Ackermannfunktion"

1.  NJN ( ... ) - ( regulär => endlich ) - ( |L|→∞ => kontextfrei )
2.  JNN
3.  NNJ
4.  JNJ
5.  NJJ (30039 binär dargestellt: 111010101010111)  (Kodierung einer norm.TM - Wort der Sprach einer norm.TM - Wort einer nichtregulären Sprache)
6.  JJN (L Є L2-L3 und L epsilonfrei)               (kontextfrei - nicht kontextsensitiv - regulär)
7.  NJJ (A->ε, A→aA, A→Bb, B→Bb, B→ε)               (regulär - kontextfrei - kontextsensitiv)
8.  JNN
9.  NJJ
10. NJN
11. NJJ
12. JNN (Automat: (1)°(2)°(3)° ['o'='+']) 
13. JNJ (Ausdruck: d*c°)
14. NJJ
15. JNJ
16. NJN

• mit Aufgabe zu "Türmen von Hanoi"

...