TU Wien:Einführung in Theoretische Informatik und Logik VU (Freund)/Prüfung 2019-06-06

Es waren 120 Minuten Zeit. Um positiv zu sein, müssen sowohl auf den Theorie Teil als auch auf den Logik Teil je 10 Punkte erreicht werden

1. Frage

Gegeben war eine Sprache L, sowie eine weitere Sprache D(L) (?).
D(L) = {waa | baw e L, a,b e T}

a)

Es sollte eine kontextfreie Grammatik erstellt werden, mit der Produktion in erweiterter Greibach-Normalform

b)

Die Produktionen der Sprache in strikter Greibach-Normalform

c)

Die Menge der Produktionsregeln als Rewrite-System

d)

Es soll gezeigt werden, dass die Sprache nicht regulär ist, indem eine gsm M mit drei Zuständen konstruiert wird, welcher die Sprache auf die nicht-reguläre Sprache {a^n b^n|n>=0} abbildet. Einer der Zustände ist der Endzustand, auf den mit Z2 übergegangen werden kann.

Nicht mehr zuordenbar

Prädikatenlogik

Es waren zwei prädikatenlogische Formeln gegeben, wobei die eine die andere impliziert. Als Funktionen wurden id (Identitätsfunktion), S (Successor) und * gegeben, als Prädikate <, <=, =, >=, >.
1.) ?
2.) Vz P(f(z), f(g(z,z)))
a) Es sollte ein Modell angegeben werden, sodass die 1. Formel eine Tautologie ist.
b) Es sollte ein Gegenbeispiel angegeben werden, sodass die 1. Formel eine Tautologie und die 2. eine Kontradiktion ist.