Theoretische Informatik

Nichtdeterministischer Kellerautomat
Konstruieren Sie einen nichtdeterministischen Kellerautomaten, der folgende Sprache über dem Alphabet {a, b} akzeptiert.
L = {wav | w, v ∈ {a, b}^* ∧ |w| = |v|}

Kontextsensitive Grammatik
Geben Sie eine kontextsensitive Grammatik für folgende Sprache über dem Alphabet {a} an.
L = {a²ⁿ |n ≥ 0}

Menge in P
Geben Sie ein Python-Programm an, das folgende Menge in Polynomialzeit entscheidet. Begründen Sie, dass Ihr Programm in Polynomialzeit arbeitet (verwenden Sie die O-Notation).
A = {(x,y,z)􏰂􏰂x,y,z ∈ N mit x^y = z}

deterministisches Python-Programm für TSP
Geben Sie ein Python-Programm an, das folgende Menge in Exponentialzeit entscheidet. Be- gru ̈nden Sie, dass Ihr Programm in Exponentialzeit arbeitet (verwenden Sie die O-Notation).
TSP = {(m,K,k)􏰂􏰂m,k ∈ N, K ∈ N^m×m, ∃s₁,...,s_m mit {s₁,...,s_m}={1,...,m} und 􏰇 􏰉m−1 K(s_i, s_i+1)􏰈 + K(s_m, s₁) ≤ k }

Nichtkontextfreie Sprache
Zeigen Sie, dass die Sprache L = {aⁱb^j | i, j ∈ N ∧ j = i²} nicht kontextfrei ist.

Ausdrücke in While-Programmen
Geben Sie eine Grammatik in Chomsky-Normalform an, die die Ausdrücke von While-Programmen (Seite 22 im Skript) erzeugt. Tragen Sie Ihre Grammatik in den CYK-Algorithmus (das Gerüst finden Sie in WueCampus) ein, testen Sie das Programm und laden Sie es in WueCampus hoch. Es sind folgende Vereinfachungen erlaubt:

1. Der Test auf reservierte Bezeichner kann vernachlässigt werden. D.h. (and+or(if)) stellt in dieser Aufgabe einen korrekten Ausdruck dar.
2. Verwenden Sie das Terminalalphabet Σ = {0,...,9,a,...,z,(,),+,−,Komma}. D.h. es sind keine Großbuchstaben in Bezeichnern erlaubt.
3. Verwenden Sie A → [a..z] als Abkürzung für die Regeln A → a, A → b, . . ., A → z. Verwenden Sie analog die Abkürzungen A → [0..9] und A → [1..9]. Im CYK-Algorithmus können diese Abkürzungen dann durch if w[i] in Maz: A[i][i]=1 behandelt werden, wobei Maz = {’a’,’b’,’c’,’d’,’e’,’f’,’g’,’h’,’i’, ’j’,’k’,’l’,’m’,’n’,’o’,’p’,’q’,’r’,’s’,’t’,’u’,’v’,’w’,’x’,’y’,’z’}.