TU Wien:Theoretische Informatik und Logik VU (Gramlich, Oswald)/Prüfung 2011-03-24

Tragen Sie mit Kugelschreiber Kennzahl, Matrikelnummer, Nach- und Vornamen ein. Legen Sie einen Lichtbildausweis bereit. Erlaubte Unterlagen: Skriptum, Vorlesungsfolien; KEINE gelösten Übungsbeispiele. Schreiben Sie alle Lösungen auf diese Blätter und geben Sie die Prüfungsarbeit ohne Zusatzblätter ab. Sie haben 2 Stunden (120 Minuten) zur Bearbeitung der Aufgaben. Viel Erfolg!

Beispiel A/1

Sei $A=⟨\{q_1,q_2,q_3,q_4\},\{\underset{\_}{a},\underset{\_}{b}\},\delta ,q_1,\{q_2,q_3\}⟩$, wobei

$\delta$	$\underset{\_}{a}$	$\underset{\_}{b}$
$q_1$	$\{q_2,q_3\}$	$\{\}$
$q_2$	$\{\}$	$\{q_4\}$
$q_3$	$\{\}$	$\{q_4\}$
$q_4$	$\{q_2,q_3\}$	$\{\}$

a) Geben Sie $ℒ\mathcal{(}𝒜\mathcal{)}$ (also die von $𝒜$ akzeptierte Sprache) als reguläre Menge an. (2 Punkte)

b) Gibt es eine kontextfreie Grammatik, welche $ℒ\mathcal{(}𝒜\mathcal{)}$ erzeugt? Falls ja, geben Sie eine solche an. Falls nein, begründen Sie, warum es eine solche nicht geben kann. (4 Punkte)

c) Geben Sie einen deterministischen endlichen Automaten an, welcher das Komplement von $ℒ\mathcal{(}𝒜\mathcal{)}$ akzeptiert. (Graphische Darstellung genügt.) (4 Punkte)

Lösung

a) $\underset{\_}{a}\cdot (\underset{\_}{b}\cdot \underset{\_}{a})\ast$

b) Eine Grammatik heißt kontextfrei, wenn die linke Seite jeder Produktion ein einzelnes Nonterminalsymbol ist.

$G=⟨\{A,B,C,D\},\{\underset{\_}{a}\underset{\_}{b}\},P,A⟩$ mit

$P=\{A\to \underset{\_}{a}B|\underset{\_}{a}C,B\to \underset{\_}{b}D|ϵ,C\to \underset{\_}{b}D|ϵ,D\to \underset{\_}{a}B|\underset{\_}{a}C\}$

Wenn man sich den Automaten aber einmal näher ansieht, wird man feststellen, dass es sich dabei um einen NEA handelt, der aber zu einem DEA vereinfacht werden kann.

Jetzt wird auch deutlich, dass zu dem Automaten auch eine reguläre Grammatik existiert.

$G=⟨\{A,B\},\{\underset{\_}{a}\underset{\_}{b}\},P,A⟩$ mit

$P=\{A\to \underset{\_}{a}BB\to \underset{\_}{b}A|ϵ\}$

c) Dafür muss lediglich die Falle im DEA von Punkt b) eingebaut werden. Den Automaten, der das Komplement akzeptiert, erhält man dann ganz einfach, indem man alle Endzustände zu Nicht-Endzuständen macht und umgekehrt:

Beispiel A/2

Sei $L_1=\{{\underset{\_}{a}}^{3n}{\underset{\_}{b}}^{2n}{\underset{\_}{c}}^m|n,m\ge 0\}$ und $L_2=\{{\underset{\_}{a}}^n{\underset{\_}{b}}^m{\underset{\_}{c}}^{3m}|n,m\ge 0\}$.

a) Geben Sie kontextfreie Grammatiken $G_1,G_2,G_3$ so an, dass $ℒ(G_1)=L_1,ℒ(G_2)=L_2$ sowie $ℒ(G_3)=L_1\cup L_2$. (6 Punkte)

b) Geben Sie $L_1\cap L_2$ an. (2 Punkte)

c) Ist $L_1\cap L_2$ eine kontextfreie Sprache? Begründen Sie Ihre Antwort. (2 Punkte)

Lösung

TODO

Beispiel A/3

Geben Sie an, ob die folgenden Aussagen richtig oder falsch sind, und begründen Sie Ihre Antworten. (Zwei Punkte für richtige Antworten mit richtiger Begründung, einen Punkt für richtige Antworten mit leicht mangelhafter Begründung, keinen Punkt für falsche Antworten oder fehlerhafte Begründungen.) (10 Punkte)

a)	Jede rekursiv aufzählbare Sprache über einem einelementigen Alphabet ist regulär.	☐ richtig ☒ falsch
b)	Für beliebige Sprachen $L_1$ gilt: $(L_1{L}_1)\ast =L_1\ast L_1\ast$	☐ richtig ☒ falsch
c)	Das Halteproblem für Turingmaschinen ist unentscheidbar.	☒ richtig ☐ falsch
d)	Es gibt einen Homomorphismus, der die Sprache $\{{\underset{\_}{0}}^{2n}|n\ge 0\}$ auf die Sprache $\{{\underset{\_}{1}}^n|n\ge 0\}$	☐ richtig ☒ falsch
e)	Ist $L_1\cup L_2=\{\}$, so ist $L_1-L_2$ nicht kontextsensitiv.	☐ richtig ☐ falsch

Begründung für Punkt a)

TODO

Begründung für Punkt b)

TODO

Begründung für Punkt c)

TODO

Begründung für Punkt d)

TODO

Begründung für Punkt e)

TODO

Beispiel A/4

Gegeben seien die AL-Formeln $F_1=A\supset (\mathrm{\neg }C\wedge B),F_2=A$ und $F_3=B\vee C$. Beweisen Sie mithilfe des Tableau-Kalküls, dass $F_3$ eine logische Konsequenz von $F_1$ und $F_2$ ist, d.h. dass gilt: $F_1,F_2\models F_3$.

Lösung

$F_1,F_2\models F_3$ gilt genau dann, wenn $(F_1\wedge F_2)\supset F_3$ eine gültige Formel ist.

Nehmen wir an, dass $(F_1\wedge F_2)\supset F_3$ widerlegbar ist, also den Wert f annehmen kann. Lässt sich diese Annahme mithilfe des Tableau Kalküls auf einen Widerspruch führen, so gilt $F_1,F_2\models F_3$.

(1)	f:	$((A\supset (\mathrm{\neg }C\wedge B))\wedge A)\supset (B\vee C)$
(2)	t:	$(A\supset (\mathrm{\neg }C\wedge B))\wedge A)$ (von 1)
(3)	f:	$(B\vee C)$ (von 1)
(4)	f:	$B$ (von 3)
(5)	f:	$C$ (von 3)
(6)	t:	$A\supset (\mathrm{\neg }C\wedge B)$ (von 2)
(7)	t:	$A$ (von 2)
(8)	f:	$A$ (von 6)	(9)	t:	$\mathrm{\neg }C\wedge B$ (von 6)
		X wid. 7, 8
			(10)	t:	$\mathrm{\neg }C$ (von 9)
			(11)	t:	$B$ (von 9)
					X wid. 4, 11

Beispiel A/5

Beweisen Sie die prädikatenlogische Formel

$[Q(a,f(f(b)))\wedge (\mathrm{\forall }x)(\mathrm{\forall }y)(Q(x,f(y))\supset Q(g(x),y))]\supset (\mathrm{\exists }y)Q(g(g(a)),y)$

mittels Resolution.

Lösung

TODO

Beispiel A/6

Geben Sie an, ob die folgenden Aussagen richtig oder falsch sind, und begründen Sie Ihre Antworten. (Zwei Punkte für richtige Antworten mit richtiger Begründung, einen Punkt für richtige Antworten mit leicht mangelhafter Begründung, keinen Punkt für falsche Antworten oder fehlerhafte Begründungen.) (10 Punkte)

a)	Eine erfüllbare aussagenlogische Formel kann durch Instanziierung (d.h. Anwendung einer Substitution) unerfüllbar werden.	☒ richtig ☐ falsch
b)	Die Menge der unerfüllbaren prädikatenlogischen Formeln ist rekursiv aufzählbar.	☐ richtig ☐ falsch
c)	Wenn bzgl. einer gegebenen prädikatenlogischen Formel F (ohne frei vorkommende Variablen) ein geschlossenes Tableau für f: F existiert, so ist F widerlegbar.	☐ richtig ☒ falsch
d)	Die prädikatenlogischen Formeln $(\mathrm{\forall }x)P(x)\vee (\mathrm{\forall }y)Q(y)$ und $(\mathrm{\forall }z)(P(z)\vee Q(z))$ sind logisch äquivalent.	☐ richtig ☒ falsch
e)	Jede aussagenlogische Formel, die nur Variablensymbole und als logische Operatoren höchstens $\mathrm{\neg }$ und $\wedge$ enthält sowie eine gerade Anzahl von $\mathrm{\neg }$ hat, ist erfüllbar.	☐ richtig ☒ falsch

Begründung für Punkt a)

TODO

Begründung für Punkt b)

TODO

Begründung für Punkt c)

TODO

Begründung für Punkt d)

Gegenbeispiel - P(x) x ist eine gerade Zahl ; Q(x) x ist eine ungerade Zahl

Begründung für Punkt e)

Gegenbeispiel - unerfüllbar: (A AND NOT(A) AND NOT(A))