Einführung in die Theoretische Informatik - Exam.pdf

Aufgabe 1)

Syntax und Semantik der AussagenlogikDie Syntax der Aussagenlogik umfasst die Regeln zur Bildung gültiger Aussagen aus atomaren Aussagen (z.B. p, q) und Junktoren (¬, ∧, ∨, →, ↔). Die Semantik betrifft die Zuweisung von Wahrheitswerten zu atomaren Aussagen sowie die Bestimmung der Wahrheitswerte komplexer Aussagen mittels Wahrheitstabellen oder Interpretationen.

a)

• Gegeben sei die Aussageformel: \((p ∨ ¬q) → (r ∧ p)\). Bestimme die Wahrheitstabelle für diese Aussageformel. Zeige alle Zwischenschritte und erläutere, wie die Wahrheitswerte der komplexen Aussagen aus den Wahrheitswerten der atomaren Aussagen abgeleitet werden.

Lösung:

Die Wahrheitstabelle für die Aussageformel \((p ∨ ¬q) → (r ∧ p)\)Um die Wahrheitstabelle für die gegebene Aussageformel \((p ∨ ¬q) → (r ∧ p)\) zu erstellen, gehen wir schrittweise vor und berechnen alle relevanten Zwischenwerte. Hier sind die detaillierten Schritte:Schritte zur Erstellung der Wahrheitstabelle:

• Erstellen einer Tabelle mit allen möglichen Kombinationen der Wahrheitswerte von \(p, q\) und \(r\).
• Berechnen der Werte für \(¬q\).
• Berechnen der Werte für \(p ∨ ¬q\).
• Berechnen der Werte für \(r ∧ p\).
• Berechnen der Werte für \((p ∨ ¬q) → (r ∧ p)\).

Hier ist die vollständige Wahrheitstabelle:

p	q	r	¬q	p ∨ ¬q	r ∧ p	(p ∨ ¬q) → (r ∧ p)
W	W	W	F	W	W	W
W	W	F	F	W	F	F
W	F	W	W	W	W	W
W	F	F	W	W	F	F
F	W	W	F	F	F	W
F	W	F	F	F	F	W
F	F	W	W	W	F	F
F	F	F	W	W	F	F

Erklärung der Schritte:

• Für jede Kombination der Wahrheitswerte von \(p, q\) und \(r\), berechnen wir zuerst den Wahrheitswert von \(¬q\).
• Dann berechnen wir den Wahrheitswert der Disjunktion \(p ∨ ¬q\), indem wir prüfen, ob mindestens einer der Operanden wahr ist.
• Als nächstes berechnen wir den Wahrheitswert der Konjunktion \(r ∧ p\), indem wir prüfen, ob beide Operanden wahr sind.
• Schließlich berechnen wir den Wahrheitswert der Implikation \((p ∨ ¬q) → (r ∧ p)\), wobei zu beachten ist, dass eine Implikation nur dann falsch ist, wenn der erste Teil wahr und der zweite Teil falsch ist. In allen anderen Fällen ist die Implikation wahr.

Aufgabe 2)

Betrachte die folgenden logischen Aussagen und formuliere sie mit Hilfe von Quantoren und Prädikaten in der Prädikatenlogik. Gegeben ist das Prädikat P(x), das für eine Eigenschaft von x steht. Für den Kontext sei P(x) so definiert: P(x) = 'x ist eine gerade Zahl'.

a)

Formuliere die Aussage 'Es gibt eine natürliche Zahl, die gerade ist' mithilfe des Existenzquantors.

Lösung:

Um die gegebene Aussage 'Es gibt eine natürliche Zahl, die gerade ist' mithilfe des Existenzquantors zu formulieren, verwenden wir das Prädikat P(x), das wie folgt definiert ist: P(x) = 'x ist eine gerade Zahl'. Für natürliche Zahlen wird das Symbol \(\mathbb{N}\) verwendet.

Der Existenzquantor wird durch \(\exists\) dargestellt und bedeutet, dass es mindestens ein Element gibt, für das die Aussage wahr ist.

Daher lautet die formale Aussage in der Prädikatenlogik:

\( \exists x \, (x \in \mathbb{N} \ \wedge \ P(x)) \)

Das bedeutet: Es existiert mindestens eine natürliche Zahl x, die gerade ist.

Oder alternativ, unter Berücksichtigung der Definition von P(x), kann die Aussage auch so geschrieben werden:

\( \exists x \, (x \in \mathbb{N} \ \wedge \ x \ \text{ist gerade}) \)

b)

Drücke die Aussage 'Alle natürlichen Zahlen sind gerade' mit einem Allquantor aus.

Lösung:

Um die Aussage 'Alle natürlichen Zahlen sind gerade' mithilfe eines Allquantors auszudrücken, verwenden wir das Prädikat P(x), das definiert ist als: P(x) = 'x ist eine gerade Zahl'. Für natürliche Zahlen wird das Symbol \( \mathbb{N} \) verwendet.

Der Allquantor wird durch \( \forall \) dargestellt und besagt, dass die Aussage für alle Elemente der betrachteten Menge gilt.

Daher lautet die formale Aussage in der Prädikatenlogik:

\[ \forall x \,(x \in \mathbb{N} \rightarrow P(x)) \]

Was bedeutet: Für alle natürlichen Zahlen x gilt, dass x gerade ist.

c)

Bestimme, ob die Aussage 'Es gibt eine natürliche Zahl, die ungerade ist' wahr oder falsch ist. Setze für die Bestimmung das Prädikat Q(x) = 'x ist eine ungerade Zahl' ein.

Lösung:

Um die Aussage 'Es gibt eine natürliche Zahl, die ungerade ist' zu überprüfen, verwenden wir das Prädikat Q(x), das definiert ist als: Q(x) = 'x ist eine ungerade Zahl'.

Eine Zahl x ist ungerade, wenn sie nicht durch 2 teilbar ist, also wenn sie die Form \( x = 2k + 1 \) hat, wobei k eine natürliche Zahl ist.

Der Existenzquantor \( \exists \) wird verwendet, um auszudrücken, dass es mindestens ein Element in der betrachteten Menge gibt, für das die Aussage gilt.

Die formale Aussage lautet dann:

\[ \exists x \,(x \in \mathbb{N} \wedge Q(x)) \]

Das bedeutet: Es gibt mindestens eine natürliche Zahl x, die ungerade ist.

Da in der Menge der natürlichen Zahlen tatsächlich ungerade Zahlen existieren, wie z.B. 1, 3, 5 usw., ist die Aussage wahr.

d)

Analysiere die folgende zusammengesetzte Aussage und formuliere sie in der Prädikatenlogik: 'Für alle natürlichen Zahlen gilt: Wenn die Zahl größer als 2 ist, dann ist sie entweder ungerade oder eine gerade Zahl.' Verwendete Prädikate: P(x) = 'x ist eine gerade Zahl' und Q(x) = 'x ist eine ungerade Zahl'.

Lösung:

Um die gegebene zusammengesetzte Aussage in der Prädikatenlogik zu formulieren, verwenden wir die Prädikate:

• P(x): 'x ist eine gerade Zahl'
• Q(x): 'x ist eine ungerade Zahl'

Die Aussage lautet: 'Für alle natürlichen Zahlen gilt: Wenn die Zahl größer als 2 ist, dann ist sie entweder ungerade oder eine gerade Zahl.'

Dazu benötigen wir zusätzlich das Prädikat:

• R(x): 'x ist größer als 2'

Die Prädikatenlogik verwendet den Allquantor (\( \forall \)) und den Implikationspfeil (\( \rightarrow \)), um die Verbindung zwischen den Prädikaten auszudrücken.

Die formale Aussage in der Prädikatenlogik lautet:

\[ \forall x \in \mathbb{N} \, (R(x) \rightarrow (Q(x) \lor P(x))) \]

Im Detail bedeutet dies:

• \( \forall x \in \mathbb{N} \): Für alle natürlichen Zahlen x
• \( R(x) \): Wenn x größer als 2 ist
• \( Q(x) \lor P(x) \): Dann ist x entweder ungerade (Q(x)) oder gerade (P(x))

Zusammengefasst: Für alle natürlichen Zahlen x gilt: Wenn x größer als 2 ist, dann ist x entweder ungerade oder gerade.

Aufgabe 3)

Gegeben sei ein nichtdeterministischer endlicher Automat (NFA) definiert durch folgende Tupel:

• Zustandsmenge: \( Q = \{ q_0, q_1, q_2 \} \)
• Alphabet: \( \Sigma = \{ a, b \} \)
• Startzustand: \( q_0 \)
• Übergangsfunktion:
  • \( \delta(q_0, a) = \{ q_0, q_1 \} \)
  • \( \delta(q_0, b) = \{ q_0 \} \)
  • \( \delta(q_1, a) = \{ q_2 \} \)
  • \( \delta(q_1, b) = \{\} \)
  • \( \delta(q_2, a) = \{\} \)
  • \( \delta(q_2, b) = \{ q_1 \} \)
• Endzustände: \( F = \{ q_2 \} \)

b)

Teilaufgabe 2: Zeichne den Übergangsgraphen des resultierenden DFA aus Teilaufgabe 1.

Lösung:

Um den Übergangsgraphen des resultierenden deterministischen endlichen Automaten (DFA) aus Teilaufgabe 1 zu zeichnen, müssen wir die Zustände und die zugehörigen Übergänge visualisieren. Dazu nutzen wir die Zustandsmenge, die Übergangsfunktion und die Endzustände des DFA, die wir zuvor abgeleitet haben.

Hier ist der Übergangsgraph des resultierenden DFA:

• Zustände: { {}, {q_0}, {q_1}, {q_2}, {q_0, q_1}, {q_0, q_2}, {q_1, q_2}, {q_0, q_1, q_2} }
• Startzustand: {q_0}
• Endzustände: {q_2}, {q_0, q_2}, {q_1, q_2}, {q_0, q_1, q_2}

Übergänge:

• {{q_0}} --a--> {{q_0, q_1}}
• {{q_0}} --b--> {{q_0}}
• {{q_1}} --a--> {{q_2}}
• {{q_1}} --b--> {}
• {{q_2}} --a--> {}
• {{q_2}} --b--> {{q_1}}
• {{q_0, q_1}} --a--> {{q_0, q_1, q_2}}
• {{q_0, q_1}} --b--> {{q_0}}
• {{q_0, q_2}} --a--> {{q_0, q_1}}
• {{q_0, q_2}} --b--> {{q_0, q_1}}
• {{q_1, q_2}} --a--> {{q_2}}
• {{q_1, q_2}} --b--> {{q_1}}
• {{q_0, q_1, q_2}} --a--> {{q_0, q_1, q_2}}
• {{q_0, q_1, q_2}} --b--> {{q_0, q_1}}

Hier ist die grafische Darstellung des Übergangsgraphen:

    +------------------a,b-----------------+    |                                      |    V                                      |  {q_0} --------a-----> {q_0, q_1} <------b------|    |                ᑉ--------------💧      |    😊        a        |       a             ------------------------------------a--|       |                    |    {q_1} ----a------> {q_2} <----💧--b--|    /|\b        |                          💧a       💧a.b               /|ᑉ.                            |       Emptyset| ........|                    |                         |                                 {q_0, q_2}          {q_1, q_2}         {q_0, q_1, q_2}

• Startzustand {q_0} hat Übergänge zu {{q_0, q_1}}, da dies regelmäßige Zustandsmengenarten sind.
• Das leere Menge {Emptyset}, hat keine Symptome, da keine Routinen innerhalb dieses Regel Verständis ist.

Der DFA zeigt die substantielle Erfüllung und chronologische Bezeichnung des Regel Verständnis Regelwerts B-Dynamik.

.

c)

Teilaufgabe 3: Beweise, dass das Wort 'aab' vom ursprünglichen NFA akzeptiert wird. Zeige dazu alle möglichen Zustandssequenzen und erläutere, warum das Wort akzeptiert wird.

Lösung:

Um zu beweisen, dass das Wort 'aab' vom ursprünglichen NFA akzeptiert wird, müssen wir alle möglichen Zustandssequenzen durchlaufen, die durch das Wort erzeugt werden. Ein Wort wird akzeptiert, wenn der NFA bei der Verarbeitung des gesamten Wortes in einen Endzustand übergeht.

Gegeben:

• Zustandsmenge: \( Q = \{ q_0, q_1, q_2 \} \)
• Alphabet: \( \Sigma = \{ a, b \} \)
• Startzustand: \( q_0 \)
• Übergangsfunktion:
  • \( \delta(q_0, a) = \{ q_0, q_1 \} \)
  • \( \delta(q_0, b) = \{ q_0 \} \)
  • \( \delta(q_1, a) = \{ q_2 \} \)
  • \( \delta(q_1, b) = \{ \} \)
  • \( \delta(q_2, a) = \{ \} \)
  • \( \delta(q_2, b) = \{ q_1 \} \)
• Endzustände: \( F = \{ q_2 \} \)

Wort: 'aab'

Lassen Sie uns nun alle möglichen Zustandssequenzen durchlaufen:

1. Startzustand: \( q_0 \)
2. Nach dem ersten 'a':
   • \( \delta(q_0, a) = \{ q_0, q_1 \} \)
3. Nach dem zweiten 'a':
   • Von \( q_0 \) aus: \( \delta(q_0, a) = \{ q_0, q_1 \} \)
   • Von \( q_1 \) aus: \( \delta(q_1, a) = \{ q_2 \} \)
   Die möglichen Zustände nach dem zweiten 'a' sind also: \( \{ q_0, q_1, q_2 \} \)
4. Nach dem 'b':
   • Von \( q_0 \) aus: \( \delta(q_0, b) = \{ q_0 \} \)
   • Von \( q_1 \) aus: \( \delta(q_1, b) = \{ \} \) (kein Übergang)
   • Von \( q_2 \) aus: \( \delta(q_2, b) = \{ q_1 \} \)
   Die möglichen Zustände nach dem 'b' sind also: \( \{ q_0, q_1 \} \).

Um zu zeigen, dass das Wort 'aab' akzeptiert wird, betrachten wir die Abfolge:

• \( q_0 \rightarrow \delta(q_0, a) = \{ q_0, q_1 \} \)
• \( q_0, q_1 \rightarrow \delta(q_0, a) \cup \delta(q_1, a) = \{ q_0, q_1 \} \cup \{ q_2 \} = \{ q_0, q_1, q_2 \} \)
• \( q_0, q_1, q_2 \rightarrow \delta(q_0, b) \cup \delta(q_1, b) \cup \delta(q_2, b) = \{ q_0 \} \cup \{ \} \cup \{ q_1 \} = \{ q_0, q_1 \} \)

Das Wort 'aab' wird vom ursprünglichen NFA akzeptiert, da der Zustand \( q_2 \) (ein Endzustand) erreicht wurde.

Aufgabe 4)

Pumping Lemma und reguläre SprachenDas Pumping-Lemma ist ein Werkzeug im Bereich der theoretischen Informatik, das hilft, zu bestimmen, ob eine Sprache nicht regulär ist. Angenommen, L ist eine reguläre Sprache, dann gibt es eine Konstante n, sodass für jedes Wort w in L mit |w| ≥ n gilt: w kann in drei Teile x, y, z zerlegt werden, wobei w = xyz, und folgende Bedingungen gelten müssen:

• |xy| ≤ n
• |y| > 0
• Für alle k ≥ 0 ist xy^kz in L

. Zum Nachweis, dass eine Sprache nicht regulär ist, wird gezeigt, dass keine solche Zerlegung für einige Wörter existiert.

a)

Beweise, dass die Sprache L = {a^mb^m | m ≥ 0} nicht regulär ist. Verwende dazu das Pumping-Lemma und zeige anhand eines speziellen Beispiels, dass keine gültige Zerlegung in x, y und z existiert, die die Bedingungen des Pumping-Lemmas erfüllt.

Lösung:

Pumping Lemma und reguläre Sprachen: BeweisUm zu beweisen, dass die Sprache L = \{a^mb^m | m ≥ 0\} nicht regulär ist, verwenden wir das Pumping-Lemma. Nach dieser Methode wird gezeigt, dass es keine mögliche Zerlegung von Wörtern in der Sprache gibt, die die Bedingungen des Pumping-Lemmas erfüllt.Schritt für Schritt Lösung:

1. Angenommen, L ist regulär. Dann gibt es eine konstante Zahl n (laut Pumping-Lemma), so dass für ein Wort w in L, mit |w| ≥ n, die Bedingung gilt: w kann in drei Teile x, y, und z zerlegt werden, wobei w = xyz und folgende Bedingungen erfüllt sind:
   • |xy| ≤ n
   • |y| > 0
   • Für alle k ≥ 0 ist xy^kz in L
   .
2. Wähle nun das Wort w = aⁿbⁿ. Hier ist |w| = 2n, welches größer oder gleich n ist.
3. Die Bedingung |xy| ≤ n bedeutet, dass xy aus den ersten n Zeichen von w bestehen muss. Da w = aⁿbⁿ, besteht die ersten n Zeichen von w nur aus 'a'. Daher ist xy eine Folge nur mit 'a's.
4. Zusätzlich soll |y| > 0 sein. Das bedeutet, dass y mindestens einen 'a' enthält.
5. Betrachte nun w' = xy²z. Das Wort hat dann die Form a^n+|y|bⁿ. Im Fall von y = a^p, wobei p ≥ 1, ergibt sich w' = a^n+pbⁿ. Da p ≥ 1, ist w' nicht in der Form a^mb^m. Das bedeutet w' ∉ L.
6. Dies zeigt, dass nicht alle w in L durch die Bedingungen des Pumping-Lemmas erfüllt werden können und daher die Sprache L nicht regulär ist.

Somit haben wir durch Kontraposition gezeigt, dass die Sprache L = \{a^mb^m | m ≥ 0\} nicht regulär ist.

b)

Betrachte die Sprache L = {aⁿ b aⁿ | n ≥ 0}. Zeige durch Anwendung des Pumping-Lemmas, dass diese Sprache nicht regulär ist. Verwende dazu ein Wort aus der Sprache und erläutere Schritt für Schritt, warum keine Zerlegung gemäß den Bedingungen möglich ist.

Lösung:

Pumping Lemma und reguläre Sprachen: Beweis für L = {aⁿ b aⁿ}Um zu beweisen, dass die Sprache L = {aⁿ b aⁿ | n ≥ 0} nicht regulär ist, verwenden wir das Pumping-Lemma. Wir zeigen durch ein spezielles Beispiel, dass keine gültige Zerlegung des Wortes in x, y und z existiert, die die Bedingungen des Pumping-Lemmas erfüllt.Schritt-für-Schritt-Lösung:

1. Angenommen, L ist regulär. Dann gibt es eine konstante Zahl n (laut Pumping-Lemma), sodass für ein Wort w in L, mit |w| ≥ n, die Bedingung gilt: w kann in drei Teile x, y, und z zerlegt werden, wobei w = xyz und folgende Bedingungen erfüllt sind:
   • |xy| ≤ n
   • |y| > 0
   • Für alle k ≥ 0 ist xy^kz in L
   .
2. Wähle nun das Wort w = aⁿ b aⁿ. Hier ist |w| = 2n + 1, welches größer oder gleich n ist.
3. Die Bedingung |xy| ≤ n bedeutet, dass xy aus den ersten n Zeichen von w bestehen muss. Da w = aⁿ b aⁿ, besteht die ersten n Zeichen von w nur aus 'a'. Daher ist xy eine Folge mit nur 'a's.
4. Zusätzlich soll |y| > 0 sein. Das bedeutet, dass y mindestens einen 'a' enthalten muss.
5. Nach dem Pumping-Lemma muss für alle k ≥ 0 das Wort w' = x y^k z in L sein.
6. Betrachte nun w' = xy²z. Das Wort hat dann die Form a^n+|y| b aⁿ. Falls y = a^p, wobei p ≥ 1, liefert das Wort w' = a^n+p b aⁿ. Da p ≥ 1, enthält das Wort w' mehr 'a's vor dem 'b', was bedeutet, dass w' nicht in der Form a^m b a^m ist, da die Anzahl der 'a's nach dem 'b' anders ist als die Anzahl der 'a's vor dem 'b'.
7. Dies zeigt, dass w' ∉ L. Dies bedeutet, dass w nicht auf eine Weise in x, y und z zerlegt werden kann, die die Bedingungen des Pumping-Lemmas erfüllt.

Daher ist die Sprache L = {aⁿ b aⁿ | n ≥ 0} nicht regulär, wie durch das Pumping-Lemma nachgewiesen.

c)

Für die Sprache L = {aⁱ b^j c^k | i, j, k ≥ 0 und i = j oder j = k}, überprüfe, ob sie regulär ist oder nicht. Wenn regulär, gib eine deterministische endliche Automaten (DFA) an, der diese Sprache akzeptiert. Wenn nicht regulär, benutze das Pumping-Lemma, um dies zu beweisen.

Lösung:

Pumping Lemma und reguläre Sprachen: Überprüfung von L = {aⁱ b^j c^k | i, j, k ≥ 0 und i = j oder j = k}Um zu überprüfen, ob die Sprache L regulär ist oder nicht, verwenden wir das Pumping-Lemma. Wir prüfen durch ein spezielles Beispiel, ob es möglich ist, ein Wort aus der Sprache in x, y und z zu zerlegen, um zu zeigen, dass die Bedingungen des Pumping-Lemmas verletzt werden.Schritt-für-Schritt-Lösung:

1. Angenommen, L ist regulär. Dann gibt es eine konstante Zahl n (laut Pumping-Lemma), sodass für ein Wort w in L mit |w| ≥ n die Bedingung gilt: w kann in drei Teile x, y, und z zerlegt werden, wobei w = xyz und folgende Bedingungen erfüllt sind:
   • |xy| ≤ n
   • |y| > 0
   • Für alle k ≥ 0 ist xy^kz in L
   .
2. Wähle nun das Wort w = aⁿ bⁿ cⁿ. Hier ist |w| = 3n, welches größer oder gleich n ist. Dieses Wort gehört zu L, da die Bedingung j = k erfüllt ist.
3. Die Bedingung |xy| ≤ n bedeutet, dass xy aus den ersten n Zeichen von w bestehen muss. Da w = aⁿ bⁿ cⁿ, muss xy nur aus 'a' bestehen. Das bedeutet, dass xy eine Folge nur mit 'a's ist.
4. Zusätzlich soll |y| > 0 sein. Das bedeutet, dass y mindestens einen 'a' enthalten muss.
5. Nach dem Pumping-Lemma muss für alle k ≥ 0 das Wort w' = x y^k z in L sein.
6. Betrachte nun w' = xy²z. Das Wort hat dann die Form a^n+p bⁿ cⁿ, wobei p = |y|> 0.
7. Das Wort w' = a^n+p bⁿ cⁿ erfüllt jedoch weder die Bedingung i = j noch die Bedingung j = k, da n ≠ n+p und j = k ist n ≠ n. Das bedeutet, dass w' ∉ L.
8. Dies zeigt, dass w nicht auf eine Weise in x, y und z zerlegt werden kann, die die Bedingungen des Pumping-Lemmas erfüllt.

Daher ist die Sprache L = {aⁱ b^j c^k | i, j, k ≥ 0 und i = j oder j = k} nicht regulär, wie durch das Pumping-Lemma nachgewiesen.