DE-Abitur · InformatikT·066 / 8

Theoretische Informatik — Automaten, formale Sprachen, Berechenbarkeit, Komplexität

Die theoretische Informatik bildet das formale Fundament: endliche Automaten und formale Sprachen klären, was eine Maschine modellhaft erkennen kann; Turingmaschinen und Halteproblem zeigen Grenzen der Berechenbarkeit; P/NP markiert die zentrale offene Komplexitätsfrage.

6Abschnitteca. 11Min Lesezeit3Kompetenzen

KB-MI · Modellieren und Implementieren — Automaten und Grammatiken konstruieren.KB-SD · Strukturieren und Darstellen — formale Sprachen mit Grammatiken und Automaten darstellen.KB-BB · Begründen und Bewerten — Berechenbarkeitsgrenzen und Komplexitätsklassen analysieren.

Operatoren:analysieren · modellieren · beweisen · beurteilen · darstellen

grundlegendes Niveau

gA: DEA konstruieren, reguläre Ausdrücke lesen, Grammatik in Chomsky-Hierarchie einordnen.

erhöhtes Niveau

eA: NEA-DEA-Konversion (Potenzmengenkonstruktion), Pumping-Lemma anwenden, Halteproblem als Unentscheidbarkeitsbeweis vollziehen, P/NP-Frage diskutieren.

Inhalt · 6 Abschnitte

Theoretische Informatik — Automaten, formale Sprachen, Berechenbarkeit, Komplexität

Endliche Automaten (DEA/NEA) und reguläre Sprachen#

StandardKMK-EPA-Inf-ModellierenNRW-IF4BY-Inf-5

Kernpunkte

Ein deterministischer endlicher Automat (DEA) ist ein 5-Tupel (Q, Σ, δ, q₀, F): Zustandsmenge, Alphabet, Übergangsfunktion δ: Q×Σ → Q, Startzustand, akzeptierende Zustände.
Nichtdeterministischer endlicher Automat (NEA): δ: Q×Σ → 𝒫(Q); akzeptiert, wenn mindestens ein Pfad in einen F-Zustand führt. NEA und DEA erkennen exakt dieselben Sprachen (reguläre Sprachen).
Reguläre Ausdrücke beschreiben reguläre Sprachen kompakt: `a*`, `(ab|ba)+`, `[0-9]{3,5}`.
Konversion NEA → DEA durch Potenzmengenkonstruktion (Subset Construction); Worst-Case 2^|Q| Zustände.
Anwendungen: Lexikalische Analyse in Compilern, Mustererkennung (grep), Protokoll-Validierung.
DEA für L = {w ∈ {a,b}* | w endet auf ab}: q0 (Start), q1 (zuletzt a), q2 (zuletzt ab, akzeptierend).

DEA FÜR L = { W ∈ {A,B}* | W ENDET AUF AB }

Welche drei Beschriftungen in "DEA für L = { w ∈ {a,b}* | w endet auf ab }" sind prüfungsrelevant?

Folgeaufgabe: Skizziere dasselbe Schema ohne Beschriftungen und ergänze sie aus dem Gedächtnis.

Deterministischer endlicher Automat mit drei Zuständen; akzeptiert genau dann, wenn das letzte gelesene Zeichenpaar „ab" ist.

Musterlösung

DEA konstruieren — Wörter, die auf „ab" enden

Konstruieren Sie einen DEA für L = { w ∈ {a,b}* | w endet auf ab }. Geben Sie Zustandsmenge, Übergangsfunktion, Start- und Endzustand an.

Schritt 1 — Zustandsidee
Drei Zustände: q0 (noch kein passendes Suffix erkannt), q1 (zuletzt a gelesen), q2 (zuletzt ab gelesen → akzeptierend).
Schritt 2 — Übergänge formal
δ(q0, a) = q1, δ(q0, b) = q0, δ(q1, a) = q1, δ(q1, b) = q2, δ(q2, a) = q1, δ(q2, b) = q0.
Schritt 3 — Akzeptanzkriterium
F = {q2}; ein Wort wird genau dann akzeptiert, wenn der Endzustand nach dem Lesen des letzten Symbols q2 ist.
Schritt 4 — Testlauf w = abab
q0 →(a) q1 →(b) q2 →(a) q1 →(b) q2 ∈ F → akzeptiert.
Schritt 5 — Interpretation
Die Sprache ist regulär; der entsprechende reguläre Ausdruck lautet (a|b)*ab.

Ergebnis: DEA = ({q0,q1,q2}, {a,b}, δ, q0, {q2}); regulärer Ausdruck (a|b)*ab.

Typische Fehler

Übergänge für einzelne Symbole vergessen — DEA muss für jedes Symbol eines Zustands definiert sein.
NEA-Pfade als „muss überall ankommen" interpretiert — gemeint ist mindestens ein Pfad.
Akzeptanzkriterium am Eingabeende vergessen — akzeptiert wird nur, wenn das gesamte Wort gelesen wurde und der Automat in einem Endzustand steht.

Formale Grammatiken und Chomsky-Hierarchie#

VertiefungNRW-IF4BY-Inf-5BW-Inf-7

Kernpunkte

Eine formale Grammatik ist 4-Tupel (V, Σ, P, S): Variablen (Nichtterminale), Terminale, Produktionen, Startsymbol.
Chomsky-Hierarchie (1956): • Typ 0 (rekursiv aufzählbar) — Turing-Maschine • Typ 1 (kontextsensitiv) — linear beschränkter Automat • Typ 2 (kontextfrei) — Kellerautomat • Typ 3 (regulär) — endlicher Automat
Beispiel kontextfreie Sprache: L = {aⁿbⁿ | n ≥ 1}, Grammatik S → aSb | ab — nicht regulär (Pumping-Lemma).
Backus-Naur-Form (BNF) beschreibt kontextfreie Grammatiken kompakt; verwendet in Sprachspezifikationen (z.B. JSON, ECMAScript).
Ableitungsbaum visualisiert die Erzeugung eines Wortes; Mehrdeutigkeit führt zu mehreren Bäumen für dasselbe Wort.
Anwendung: Parser im Compilerbau, Syntaxprüfung, BNF-Spezifikation von Programmiersprachen.

ABLEITUNGSBAUM KONTEXTFREIER GRAMMATIK

Welche drei Beschriftungen in "Ableitungsbaum kontextfreier Grammatik" sind prüfungsrelevant?

Folgeaufgabe: Skizziere dasselbe Schema ohne Beschriftungen und ergänze sie aus dem Gedächtnis.

Grammatik G: S → aSb | ε erzeugt Sprache { aⁿbⁿ | n ≥ 0 }; Ableitungsbaum für aabb.

Musterlösung

Kontextfreie Grammatik für L = { aⁿbⁿ | n ≥ 0 }

Geben Sie eine kontextfreie Grammatik G für L an und leiten Sie das Wort aaabbb ab.

Schritt 1 — Grammatik formal
G = ({S}, {a,b}, P, S) mit P = { S → aSb | ε }.
Schritt 2 — Ableitung von aaabbb
S ⇒ aSb ⇒ aaSbb ⇒ aaaSbbb ⇒ aaaεbbb = aaabbb.
Schritt 3 — Klassifikation
L ist kontextfrei, aber nicht regulär (Pumping-Lemma für reguläre Sprachen scheitert).
Schritt 4 — Akzeptor
Erkannt von einem Kellerautomaten (NPDA), nicht von einem DEA.

Ergebnis: G erzeugt L; aaabbb ist in vier Schritten ableitbar; L ist kontextfrei, nicht regulär.

Typische Fehler

Reguläre und kontextfreie Sprachen verwechselt — aⁿbⁿ ist NICHT regulär.
Ableitung statt Ableitungsbaum gezeigt — Operator „darstellen" erwartet Baum.
Mehrdeutigkeit der Grammatik übersehen — Wort hat mehrere Ableitungsbäume.

LK-Vertiefung

eA-Vertiefung: Beweisen Sie mit dem Pumping-Lemma für reguläre Sprachen, dass L = {aⁿbⁿ | n ≥ 0} nicht regulär ist.

Turingmaschine, Berechenbarkeit und Halteproblem#

VertiefungNRW-IF4BY-Inf-5BW-Inf-7

Kernpunkte

Eine Turingmaschine (Turing 1936) hat unendliches Band, Lese-/Schreibkopf und endliche Steuerung; modelliert intuitiv das Berechenbare.
Church-Turing-These: jede intuitiv berechenbare Funktion ist Turing-berechenbar. Nicht beweisbar, aber empirisch unbestritten.
Entscheidbarkeit: Eine Sprache L ist entscheidbar, wenn eine Turingmaschine für jedes Wort terminiert und „akzeptiert/verwirft" ausgibt.
Halteproblem: Frage, ob beliebiges Programm P bei Eingabe w hält. Turing 1936: unentscheidbar — keine total berechenbare Funktion H entscheidet dies.
Beweisidee (Diagonalisierung): konstruiere Programm D, das das Gegenteil von H(P, P) tut → Widerspruch bei D(D).
Konsequenz: Statische Analyse hat fundamentale Grenzen; z.B. Reachability, Äquivalenz von Programmen sind unentscheidbar (Satz von Rice).

UNENTSCHEIDBARKEIT DES HALTEPROBLEMS

\nexists\, H: \{0,1\}^{*}\times\{0,1\}^{*}\to\{0,1\}\;\text{total berechenbar mit}\;H(P,w)=1 \iff P(w) \text{ hält}

Es existiert keine total berechenbare Funktion, die für jedes Paar (Programm, Eingabe) entscheidet, ob das Programm hält.

TURINGMASCHINEN-BAND MIT LESE-/SCHREIBKOPF

Welche drei Beschriftungen in "Turingmaschinen-Band mit Lese-/Schreibkopf" sind prüfungsrelevant?

Folgeaufgabe: Skizziere dasselbe Schema ohne Beschriftungen und ergänze sie aus dem Gedächtnis.

Unendliches Band mit Symbolen; Kopf liest aktuelles Symbol, Steuereinheit entscheidet anhand des Zustands.

Musterlösung

Diagonalisierungsargument für das Halteproblem

Skizzieren Sie den Widerspruchsbeweis, dass das Halteproblem nicht entscheidbar ist.

Schritt 1 — Annahme
Angenommen, es existiert ein totaler Algorithmus H(P, w), der „1" zurückgibt, falls Programm P bei Eingabe w hält, und „0" sonst.
Schritt 2 — Konstruktion eines paradoxen Programms
Definiere D(P) := if H(P, P) = 1 then endlos_schleife() else stop.
Schritt 3 — Selbstanwendung
Betrachte D(D). Falls H(D, D) = 1, so läuft D(D) endlos — Widerspruch. Falls H(D, D) = 0, so stoppt D(D) — auch Widerspruch.
Schritt 4 — Folgerung
Die Annahme der Existenz von H führt zu einem Widerspruch. Folglich ist H nicht berechenbar; das Halteproblem ist unentscheidbar.

Ergebnis: Das Halteproblem ist unentscheidbar (Turing 1936); damit existieren prinzipiell nicht algorithmisch lösbare Probleme.

Typische Fehler

Halteproblem mit Terminationsanalyse für konkrete Programme verwechselt — letztere ist im Einzelfall möglich.
Church-Turing-These als Theorem ausgegeben — ist keine, sondern eine These.
Diagonalisierungsbeweis ohne Widerspruchskonstruktion abgekürzt.

LK-Vertiefung

eA-Vertiefung: Beurteilen Sie, ob aus der Unentscheidbarkeit des Halteproblems folgt, dass keine Software je vollständig statisch verifiziert werden kann — diskutieren Sie eingeschränkte Fragestellungen.

Komplexitätsklassen P, NP und das P-vs-NP-Problem#

VertiefungNRW-IF4BY-Inf-5BW-Inf-7

Kernpunkte

P = Menge der Sprachen, die in polynomieller Zeit deterministisch entscheidbar sind.
NP = Menge der Sprachen, deren Lösungskandidaten in polynomieller Zeit verifiziert werden können (äquivalent: nichtdeterministisch polynomiell entscheidbar).
P ⊆ NP — die offene Frage „P = NP?" gehört zu den sieben Millennium-Problemen (Clay Mathematics Institute 2000).
NP-vollständig: schwerste Probleme in NP; eine effiziente Lösung würde alle NP-Probleme effizient lösen. Cook-Levin (1971): SAT ist NP-vollständig.
Beispiele NP-vollständig: SAT, 3-SAT, Travelling Salesman (Entscheidungsversion), Vertex Cover, Subset Sum, Sudoku.
Praktische Konsequenz: Für NP-vollständige Probleme nutzt man Heuristiken, Approximationsalgorithmen oder Constraint-Solver, kein effizientes Verfahren bekannt.

Typische Fehler

„NP" als „nicht polynomiell" interpretiert — tatsächlich „nichtdeterministisch polynomiell".
NP-schwer mit NP-vollständig gleichgesetzt — NP-vollständig ⊂ NP, NP-schwer evtl. außerhalb NP.
Travelling Salesman als „in NP, nicht in P" angegeben, ohne dass dies bewiesen wäre — tatsächlich nur „nicht bekannt in P".

LK-Vertiefung

eA-Vertiefung: Diskutieren Sie die Konsequenzen eines hypothetischen Beweises P = NP für die Kryptographie, Optimierung und Beweisautomation.

Kellerautomaten und das Pumping-Lemma#

VertiefungNRW-IF4BY-Inf-5BW-Inf-7

Kernpunkte

Ein Kellerautomat (PDA) erweitert den endlichen Automaten um einen Stapel (Keller); er erkennt genau die kontextfreien Sprachen (Typ 2).
Konfiguration: aktueller Zustand, restliche Eingabe, Kellerinhalt; Übergänge dürfen das oberste Kellersymbol lesen, ersetzen oder entfernen.
Beispiel L = {aⁿbⁿ | n ≥ 1}: jedes gelesene `a` legt ein Symbol auf den Keller, jedes `b` entfernt eines; Akzeptanz bei leerem Keller — ein DEA kann das nicht (kein Gedächtnis für die Anzahl).
Das Pumping-Lemma für reguläre Sprachen ist ein notwendiges Kriterium: für jede reguläre Sprache existiert ein n, sodass jedes Wort z mit |z| ≥ n in z = uvw mit |uv| ≤ n, |v| ≥ 1 und uvⁱw ∈ L für alle i ≥ 0 zerlegt werden kann.
Es dient dem Widerspruchsbeweis der Nicht-Regularität: Annahme regulär → Zerlegung → ein „aufgepumptes" Wort verlässt die Sprache → Widerspruch.
Für kontextfreie Sprachen gibt es ein eigenes Pumping-Lemma (z = uvwxy); damit zeigt man z.B., dass L = {aⁿbⁿcⁿ} nicht kontextfrei ist.

KELLERAUTOMAT (PDA) FÜR L = { AⁿBⁿ | N ≥ 1 }

Welche drei Beschriftungen in "Kellerautomat (PDA) für L = { aⁿbⁿ | n ≥ 1 }" sind prüfungsrelevant?

Folgeaufgabe: Skizziere dasselbe Schema ohne Beschriftungen und ergänze sie aus dem Gedächtnis.

Der Keller (Stack) zählt die a-Zeichen; jedes b entfernt ein A. Akzeptanz bei leerem Keller nach dem Lesen des Wortes.

Musterlösung

Kontextfreie Grammatik für L = { aⁿbⁿ | n ≥ 0 }

Geben Sie eine kontextfreie Grammatik G für L an und leiten Sie das Wort aaabbb ab.

Schritt 1 — Grammatik formal
G = ({S}, {a,b}, P, S) mit P = { S → aSb | ε }.
Schritt 2 — Ableitung von aaabbb
S ⇒ aSb ⇒ aaSbb ⇒ aaaSbbb ⇒ aaaεbbb = aaabbb.
Schritt 3 — Klassifikation
L ist kontextfrei, aber nicht regulär (Pumping-Lemma für reguläre Sprachen scheitert).
Schritt 4 — Akzeptor
Erkannt von einem Kellerautomaten (NPDA), nicht von einem DEA.

Ergebnis: G erzeugt L; aaabbb ist in vier Schritten ableitbar; L ist kontextfrei, nicht regulär.

Typische Fehler

Pumping-Lemma als hinreichendes Kriterium für Regularität verwendet — es ist nur notwendig.
Im Beweis nur eine Zerlegung von z betrachtet statt aller zulässigen.
Kellerautomat ohne Bodensymbol oder ohne definiertes Akzeptanzkriterium angegeben.
Wort z mit |z| < n gewählt — die Bedingung |z| ≥ n wird verletzt.

LK-Vertiefung

eA-Vertiefung: Wenden Sie das Pumping-Lemma für kontextfreie Sprachen an, um zu zeigen, dass L = {aⁿbⁿcⁿ | n ≥ 1} nicht kontextfrei ist.

Reguläre Ausdrücke, Automaten-Minimierung und Äquivalenz#

StandardNRW-IF4BY-Inf-5

Kernpunkte

Die Kleene-Äquivalenz besagt: reguläre Ausdrücke, NEA und DEA beschreiben exakt dieselbe Sprachklasse (die regulären Sprachen) und lassen sich ineinander überführen.
Konstruktion regulärer Ausdruck → NEA (Thompson-Konstruktion), NEA → DEA (Potenzmengenkonstruktion), DEA → regulärer Ausdruck (Zustandselimination).
Minimierung eines DEA: unerreichbare Zustände entfernen, dann äquivalente Zustände verschmelzen (Tabellenfüllverfahren bzw. Myhill-Nerode-Klassen).
Der Satz von Myhill-Nerode charakterisiert reguläre Sprachen über die Anzahl der Äquivalenzklassen der Rechtskongruenz; endlich viele Klassen ⇔ regulär.
Der minimale DEA ist bis auf Umbenennung der Zustände eindeutig — nützlich für den Äquivalenznachweis zweier Automaten.
Anwendungen: Optimierung von Lexern/Scannern, Mustererkennung (RegEx-Engines), Verifikation endlicher Protokollautomaten.

DEA FÜR L = { W ∈ {A,B}* | W ENDET AUF AB }

Welche drei Beschriftungen in "DEA für L = { w ∈ {a,b}* | w endet auf ab }" sind prüfungsrelevant?

Folgeaufgabe: Skizziere dasselbe Schema ohne Beschriftungen und ergänze sie aus dem Gedächtnis.

Deterministischer endlicher Automat mit drei Zuständen; akzeptiert genau dann, wenn das letzte gelesene Zeichenpaar „ab" ist.

Typische Fehler

Bei der Potenzmengenkonstruktion den Fangzustand (für fehlende Übergänge) vergessen.
Unerreichbare Zustände bei der Minimierung übersehen.
Äquivalente Zustände zu früh verschmolzen, ohne das Akzeptanzverhalten zu prüfen.
Reguläre Ausdrücke und kontextfreie Grammatiken verwechselt — Klammerbalance ist nicht regulär.

LK-Vertiefung

eA-Vertiefung: Begründen Sie mit dem Satz von Myhill-Nerode, warum L = {aⁿbⁿ | n ≥ 0} unendlich viele Äquivalenzklassen besitzt und damit nicht regulär ist.

Wird geladen

EuraStudy

Dein Lernraum wird vorbereitet — Curriculum, Notizen und KI verbinden sich.

Theoretische Informatik — Automaten, formale Sprachen, Berechenbarkeit, Komplexität

6Abschnitteca. 11Min Lesezeit3Kompetenzen

Operatoren:analysieren · modellieren · beweisen · beurteilen · darstellen

grundlegendes Niveau

gA: DEA konstruieren, reguläre Ausdrücke lesen, Grammatik in Chomsky-Hierarchie einordnen.

erhöhtes Niveau

eA: NEA-DEA-Konversion (Potenzmengenkonstruktion), Pumping-Lemma anwenden, Halteproblem als Unentscheidbarkeitsbeweis vollziehen, P/NP-Frage diskutieren.

Endliche Automaten (DEA/NEA) und reguläre Sprachen#

StandardKMK-EPA-Inf-ModellierenNRW-IF4BY-Inf-5

Kernpunkte

Ein deterministischer endlicher Automat (DEA) ist ein 5-Tupel (Q, Σ, δ, q₀, F): Zustandsmenge, Alphabet, Übergangsfunktion δ: Q×Σ → Q, Startzustand, akzeptierende Zustände.
Nichtdeterministischer endlicher Automat (NEA): δ: Q×Σ → 𝒫(Q); akzeptiert, wenn mindestens ein Pfad in einen F-Zustand führt. NEA und DEA erkennen exakt dieselben Sprachen (reguläre Sprachen).
Reguläre Ausdrücke beschreiben reguläre Sprachen kompakt: `a*`, `(ab|ba)+`, `[0-9]{3,5}`.
Konversion NEA → DEA durch Potenzmengenkonstruktion (Subset Construction); Worst-Case 2^|Q| Zustände.
Anwendungen: Lexikalische Analyse in Compilern, Mustererkennung (grep), Protokoll-Validierung.
DEA für L = {w ∈ {a,b}* | w endet auf ab}: q0 (Start), q1 (zuletzt a), q2 (zuletzt ab, akzeptierend).

DEA FÜR L = { W ∈ {A,B}* | W ENDET AUF AB }

Welche drei Beschriftungen in "DEA für L = { w ∈ {a,b}* | w endet auf ab }" sind prüfungsrelevant?

Folgeaufgabe: Skizziere dasselbe Schema ohne Beschriftungen und ergänze sie aus dem Gedächtnis.

Deterministischer endlicher Automat mit drei Zuständen; akzeptiert genau dann, wenn das letzte gelesene Zeichenpaar „ab" ist.

Musterlösung

DEA konstruieren — Wörter, die auf „ab" enden

Konstruieren Sie einen DEA für L = { w ∈ {a,b}* | w endet auf ab }. Geben Sie Zustandsmenge, Übergangsfunktion, Start- und Endzustand an.

Schritt 1 — Zustandsidee
Drei Zustände: q0 (noch kein passendes Suffix erkannt), q1 (zuletzt a gelesen), q2 (zuletzt ab gelesen → akzeptierend).
Schritt 2 — Übergänge formal
δ(q0, a) = q1, δ(q0, b) = q0, δ(q1, a) = q1, δ(q1, b) = q2, δ(q2, a) = q1, δ(q2, b) = q0.
Schritt 3 — Akzeptanzkriterium
F = {q2}; ein Wort wird genau dann akzeptiert, wenn der Endzustand nach dem Lesen des letzten Symbols q2 ist.
Schritt 4 — Testlauf w = abab
q0 →(a) q1 →(b) q2 →(a) q1 →(b) q2 ∈ F → akzeptiert.
Schritt 5 — Interpretation
Die Sprache ist regulär; der entsprechende reguläre Ausdruck lautet (a|b)*ab.

Ergebnis: DEA = ({q0,q1,q2}, {a,b}, δ, q0, {q2}); regulärer Ausdruck (a|b)*ab.

Typische Fehler

Übergänge für einzelne Symbole vergessen — DEA muss für jedes Symbol eines Zustands definiert sein.
NEA-Pfade als „muss überall ankommen" interpretiert — gemeint ist mindestens ein Pfad.
Akzeptanzkriterium am Eingabeende vergessen — akzeptiert wird nur, wenn das gesamte Wort gelesen wurde und der Automat in einem Endzustand steht.

Formale Grammatiken und Chomsky-Hierarchie#

VertiefungNRW-IF4BY-Inf-5BW-Inf-7

Kernpunkte

Eine formale Grammatik ist 4-Tupel (V, Σ, P, S): Variablen (Nichtterminale), Terminale, Produktionen, Startsymbol.
Chomsky-Hierarchie (1956): • Typ 0 (rekursiv aufzählbar) — Turing-Maschine • Typ 1 (kontextsensitiv) — linear beschränkter Automat • Typ 2 (kontextfrei) — Kellerautomat • Typ 3 (regulär) — endlicher Automat
Beispiel kontextfreie Sprache: L = {aⁿbⁿ | n ≥ 1}, Grammatik S → aSb | ab — nicht regulär (Pumping-Lemma).
Backus-Naur-Form (BNF) beschreibt kontextfreie Grammatiken kompakt; verwendet in Sprachspezifikationen (z.B. JSON, ECMAScript).
Ableitungsbaum visualisiert die Erzeugung eines Wortes; Mehrdeutigkeit führt zu mehreren Bäumen für dasselbe Wort.
Anwendung: Parser im Compilerbau, Syntaxprüfung, BNF-Spezifikation von Programmiersprachen.

ABLEITUNGSBAUM KONTEXTFREIER GRAMMATIK

Welche drei Beschriftungen in "Ableitungsbaum kontextfreier Grammatik" sind prüfungsrelevant?

Folgeaufgabe: Skizziere dasselbe Schema ohne Beschriftungen und ergänze sie aus dem Gedächtnis.

Grammatik G: S → aSb | ε erzeugt Sprache { aⁿbⁿ | n ≥ 0 }; Ableitungsbaum für aabb.

Musterlösung

Kontextfreie Grammatik für L = { aⁿbⁿ | n ≥ 0 }

Geben Sie eine kontextfreie Grammatik G für L an und leiten Sie das Wort aaabbb ab.

Schritt 1 — Grammatik formal
G = ({S}, {a,b}, P, S) mit P = { S → aSb | ε }.
Schritt 2 — Ableitung von aaabbb
S ⇒ aSb ⇒ aaSbb ⇒ aaaSbbb ⇒ aaaεbbb = aaabbb.
Schritt 3 — Klassifikation
L ist kontextfrei, aber nicht regulär (Pumping-Lemma für reguläre Sprachen scheitert).
Schritt 4 — Akzeptor
Erkannt von einem Kellerautomaten (NPDA), nicht von einem DEA.

Ergebnis: G erzeugt L; aaabbb ist in vier Schritten ableitbar; L ist kontextfrei, nicht regulär.

Typische Fehler

Reguläre und kontextfreie Sprachen verwechselt — aⁿbⁿ ist NICHT regulär.
Ableitung statt Ableitungsbaum gezeigt — Operator „darstellen" erwartet Baum.
Mehrdeutigkeit der Grammatik übersehen — Wort hat mehrere Ableitungsbäume.

LK-Vertiefung

eA-Vertiefung: Beweisen Sie mit dem Pumping-Lemma für reguläre Sprachen, dass L = {aⁿbⁿ | n ≥ 0} nicht regulär ist.

Turingmaschine, Berechenbarkeit und Halteproblem#

VertiefungNRW-IF4BY-Inf-5BW-Inf-7

Kernpunkte

Eine Turingmaschine (Turing 1936) hat unendliches Band, Lese-/Schreibkopf und endliche Steuerung; modelliert intuitiv das Berechenbare.
Church-Turing-These: jede intuitiv berechenbare Funktion ist Turing-berechenbar. Nicht beweisbar, aber empirisch unbestritten.
Entscheidbarkeit: Eine Sprache L ist entscheidbar, wenn eine Turingmaschine für jedes Wort terminiert und „akzeptiert/verwirft" ausgibt.
Halteproblem: Frage, ob beliebiges Programm P bei Eingabe w hält. Turing 1936: unentscheidbar — keine total berechenbare Funktion H entscheidet dies.
Beweisidee (Diagonalisierung): konstruiere Programm D, das das Gegenteil von H(P, P) tut → Widerspruch bei D(D).
Konsequenz: Statische Analyse hat fundamentale Grenzen; z.B. Reachability, Äquivalenz von Programmen sind unentscheidbar (Satz von Rice).

UNENTSCHEIDBARKEIT DES HALTEPROBLEMS

\nexists\, H: \{0,1\}^{*}\times\{0,1\}^{*}\to\{0,1\}\;\text{total berechenbar mit}\;H(P,w)=1 \iff P(w) \text{ hält}

Es existiert keine total berechenbare Funktion, die für jedes Paar (Programm, Eingabe) entscheidet, ob das Programm hält.

TURINGMASCHINEN-BAND MIT LESE-/SCHREIBKOPF

Welche drei Beschriftungen in "Turingmaschinen-Band mit Lese-/Schreibkopf" sind prüfungsrelevant?

Folgeaufgabe: Skizziere dasselbe Schema ohne Beschriftungen und ergänze sie aus dem Gedächtnis.

Unendliches Band mit Symbolen; Kopf liest aktuelles Symbol, Steuereinheit entscheidet anhand des Zustands.

Musterlösung

Diagonalisierungsargument für das Halteproblem

Skizzieren Sie den Widerspruchsbeweis, dass das Halteproblem nicht entscheidbar ist.

Schritt 1 — Annahme
Angenommen, es existiert ein totaler Algorithmus H(P, w), der „1" zurückgibt, falls Programm P bei Eingabe w hält, und „0" sonst.
Schritt 2 — Konstruktion eines paradoxen Programms
Definiere D(P) := if H(P, P) = 1 then endlos_schleife() else stop.
Schritt 3 — Selbstanwendung
Betrachte D(D). Falls H(D, D) = 1, so läuft D(D) endlos — Widerspruch. Falls H(D, D) = 0, so stoppt D(D) — auch Widerspruch.
Schritt 4 — Folgerung
Die Annahme der Existenz von H führt zu einem Widerspruch. Folglich ist H nicht berechenbar; das Halteproblem ist unentscheidbar.

Ergebnis: Das Halteproblem ist unentscheidbar (Turing 1936); damit existieren prinzipiell nicht algorithmisch lösbare Probleme.

Typische Fehler

Halteproblem mit Terminationsanalyse für konkrete Programme verwechselt — letztere ist im Einzelfall möglich.
Church-Turing-These als Theorem ausgegeben — ist keine, sondern eine These.
Diagonalisierungsbeweis ohne Widerspruchskonstruktion abgekürzt.

LK-Vertiefung

Komplexitätsklassen P, NP und das P-vs-NP-Problem#

VertiefungNRW-IF4BY-Inf-5BW-Inf-7

Kernpunkte

P = Menge der Sprachen, die in polynomieller Zeit deterministisch entscheidbar sind.
NP = Menge der Sprachen, deren Lösungskandidaten in polynomieller Zeit verifiziert werden können (äquivalent: nichtdeterministisch polynomiell entscheidbar).
P ⊆ NP — die offene Frage „P = NP?" gehört zu den sieben Millennium-Problemen (Clay Mathematics Institute 2000).
NP-vollständig: schwerste Probleme in NP; eine effiziente Lösung würde alle NP-Probleme effizient lösen. Cook-Levin (1971): SAT ist NP-vollständig.
Beispiele NP-vollständig: SAT, 3-SAT, Travelling Salesman (Entscheidungsversion), Vertex Cover, Subset Sum, Sudoku.
Praktische Konsequenz: Für NP-vollständige Probleme nutzt man Heuristiken, Approximationsalgorithmen oder Constraint-Solver, kein effizientes Verfahren bekannt.

Typische Fehler

„NP" als „nicht polynomiell" interpretiert — tatsächlich „nichtdeterministisch polynomiell".
NP-schwer mit NP-vollständig gleichgesetzt — NP-vollständig ⊂ NP, NP-schwer evtl. außerhalb NP.
Travelling Salesman als „in NP, nicht in P" angegeben, ohne dass dies bewiesen wäre — tatsächlich nur „nicht bekannt in P".

LK-Vertiefung

eA-Vertiefung: Diskutieren Sie die Konsequenzen eines hypothetischen Beweises P = NP für die Kryptographie, Optimierung und Beweisautomation.

Kellerautomaten und das Pumping-Lemma#

VertiefungNRW-IF4BY-Inf-5BW-Inf-7

Kernpunkte

Ein Kellerautomat (PDA) erweitert den endlichen Automaten um einen Stapel (Keller); er erkennt genau die kontextfreien Sprachen (Typ 2).
Konfiguration: aktueller Zustand, restliche Eingabe, Kellerinhalt; Übergänge dürfen das oberste Kellersymbol lesen, ersetzen oder entfernen.
Beispiel L = {aⁿbⁿ | n ≥ 1}: jedes gelesene `a` legt ein Symbol auf den Keller, jedes `b` entfernt eines; Akzeptanz bei leerem Keller — ein DEA kann das nicht (kein Gedächtnis für die Anzahl).
Das Pumping-Lemma für reguläre Sprachen ist ein notwendiges Kriterium: für jede reguläre Sprache existiert ein n, sodass jedes Wort z mit |z| ≥ n in z = uvw mit |uv| ≤ n, |v| ≥ 1 und uvⁱw ∈ L für alle i ≥ 0 zerlegt werden kann.
Es dient dem Widerspruchsbeweis der Nicht-Regularität: Annahme regulär → Zerlegung → ein „aufgepumptes" Wort verlässt die Sprache → Widerspruch.
Für kontextfreie Sprachen gibt es ein eigenes Pumping-Lemma (z = uvwxy); damit zeigt man z.B., dass L = {aⁿbⁿcⁿ} nicht kontextfrei ist.

KELLERAUTOMAT (PDA) FÜR L = { AⁿBⁿ | N ≥ 1 }

Welche drei Beschriftungen in "Kellerautomat (PDA) für L = { aⁿbⁿ | n ≥ 1 }" sind prüfungsrelevant?

Folgeaufgabe: Skizziere dasselbe Schema ohne Beschriftungen und ergänze sie aus dem Gedächtnis.

Der Keller (Stack) zählt die a-Zeichen; jedes b entfernt ein A. Akzeptanz bei leerem Keller nach dem Lesen des Wortes.

Musterlösung

Kontextfreie Grammatik für L = { aⁿbⁿ | n ≥ 0 }

Geben Sie eine kontextfreie Grammatik G für L an und leiten Sie das Wort aaabbb ab.

Schritt 1 — Grammatik formal
G = ({S}, {a,b}, P, S) mit P = { S → aSb | ε }.
Schritt 2 — Ableitung von aaabbb
S ⇒ aSb ⇒ aaSbb ⇒ aaaSbbb ⇒ aaaεbbb = aaabbb.
Schritt 3 — Klassifikation
L ist kontextfrei, aber nicht regulär (Pumping-Lemma für reguläre Sprachen scheitert).
Schritt 4 — Akzeptor
Erkannt von einem Kellerautomaten (NPDA), nicht von einem DEA.

Ergebnis: G erzeugt L; aaabbb ist in vier Schritten ableitbar; L ist kontextfrei, nicht regulär.

Typische Fehler

Pumping-Lemma als hinreichendes Kriterium für Regularität verwendet — es ist nur notwendig.
Im Beweis nur eine Zerlegung von z betrachtet statt aller zulässigen.
Kellerautomat ohne Bodensymbol oder ohne definiertes Akzeptanzkriterium angegeben.
Wort z mit |z| < n gewählt — die Bedingung |z| ≥ n wird verletzt.

LK-Vertiefung

eA-Vertiefung: Wenden Sie das Pumping-Lemma für kontextfreie Sprachen an, um zu zeigen, dass L = {aⁿbⁿcⁿ | n ≥ 1} nicht kontextfrei ist.

Reguläre Ausdrücke, Automaten-Minimierung und Äquivalenz#

StandardNRW-IF4BY-Inf-5

Kernpunkte

Die Kleene-Äquivalenz besagt: reguläre Ausdrücke, NEA und DEA beschreiben exakt dieselbe Sprachklasse (die regulären Sprachen) und lassen sich ineinander überführen.
Konstruktion regulärer Ausdruck → NEA (Thompson-Konstruktion), NEA → DEA (Potenzmengenkonstruktion), DEA → regulärer Ausdruck (Zustandselimination).
Minimierung eines DEA: unerreichbare Zustände entfernen, dann äquivalente Zustände verschmelzen (Tabellenfüllverfahren bzw. Myhill-Nerode-Klassen).
Der Satz von Myhill-Nerode charakterisiert reguläre Sprachen über die Anzahl der Äquivalenzklassen der Rechtskongruenz; endlich viele Klassen ⇔ regulär.
Der minimale DEA ist bis auf Umbenennung der Zustände eindeutig — nützlich für den Äquivalenznachweis zweier Automaten.
Anwendungen: Optimierung von Lexern/Scannern, Mustererkennung (RegEx-Engines), Verifikation endlicher Protokollautomaten.

DEA FÜR L = { W ∈ {A,B}* | W ENDET AUF AB }

Welche drei Beschriftungen in "DEA für L = { w ∈ {a,b}* | w endet auf ab }" sind prüfungsrelevant?

Folgeaufgabe: Skizziere dasselbe Schema ohne Beschriftungen und ergänze sie aus dem Gedächtnis.

Deterministischer endlicher Automat mit drei Zuständen; akzeptiert genau dann, wenn das letzte gelesene Zeichenpaar „ab" ist.

Typische Fehler

Bei der Potenzmengenkonstruktion den Fangzustand (für fehlende Übergänge) vergessen.
Unerreichbare Zustände bei der Minimierung übersehen.
Äquivalente Zustände zu früh verschmolzen, ohne das Akzeptanzverhalten zu prüfen.
Reguläre Ausdrücke und kontextfreie Grammatiken verwechselt — Klammerbalance ist nicht regulär.

LK-Vertiefung

eA-Vertiefung: Begründen Sie mit dem Satz von Myhill-Nerode, warum L = {aⁿbⁿ | n ≥ 0} unendlich viele Äquivalenzklassen besitzt und damit nicht regulär ist.