Theoretische Informatik — Automaten, formale Sprachen, Berechenbarkeit, Komplexität — Informatik · Abitur-Zusammenfassung

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

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

DEA für L = { w ∈ {a,b}* | w endet auf ab }

Abb. 1Übergangstabelle des deterministischen endlichen Automaten mit drei Zuständen: δ(Zustand, Eingabe) = Folgezustand. Startzustand q0, akzeptierender Zustand q2 (erreicht nach „ab"). Beispiel „aab": q0 → q1 → q1 → q2 ⇒ akzeptiert.

Der endliche Automat ist das einfachste Berechnungsmodell: Er liest ein Eingabewort von links nach rechts und besitzt als einzigen Speicher seinen aktuellen Zustand — also nur endlich viel Gedächtnis. Genau das modelliert Systeme mit beschränktem Gedächtnis (Getränkeautomat, Ampel, Lexer, Protokollzustände). Ein deterministischer endlicher Automat (DEA) ist formal ein 5-Tupel (Q, Σ, δ, q₀, F): die endliche Zustandsmenge Q, das Eingabealphabet Σ, die Übergangsfunktion δ: Q×Σ → Q (total — zu jedem Paar aus Zustand und Symbol gibt es genau einen Nachfolger), der Startzustand q₀ und die Menge F ⊆ Q der akzeptierenden (End-)Zustände. Der DEA akzeptiert ein Wort w genau dann, wenn er nach dem Lesen des gesamten w von q₀ aus in einem Zustand aus F endet.

Beim nichtdeterministischen endlichen Automaten (NEA) liefert die Übergangsfunktion δ: Q×Σ → 𝒫(Q) eine Menge möglicher Nachfolgezustände (keinen, einen oder mehrere), oft erweitert um ε-Übergänge ohne Eingabe. Ein NEA akzeptiert w, wenn mindestens ein Berechnungspfad in einem Endzustand endet — man darf sich also „den günstigsten Pfad raten". Zentrale Erkenntnis (Rabin–Scott 1959): NEA und DEA erkennen exakt dieselbe Sprachklasse, die regulären Sprachen. Der NEA ist meist kleiner und leichter zu entwerfen, der DEA leichter mechanisch auszuführen.

Die Gleichmächtigkeit zeigt die Potenzmengenkonstruktion (Subset Construction): Man baut einen DEA, dessen Zustände Teilmengen der NEA-Zustände sind (die jeweils erreichbare Zustandsmenge), Start ist die ε-Hülle von {q₀}, akzeptierend ist jede Teilmenge, die einen NEA-Endzustand enthält. Im Worst Case entstehen dabei 2^|Q| Zustände — ein NEA mit n Zuständen kann also einen exponentiell größeren DEA erzwingen; gleich mächtig heißt eben nicht gleich groß.

Reguläre Ausdrücke beschreiben dieselben regulären Sprachen kompakt aus drei Operationen (Kleene 1956): Verkettung, Alternative `|` und Kleene-Stern `` (beliebige Wiederholung, auch nullmal). Beispiele: `a` (beliebig viele a), `(ab|ba)+` (mindestens einmal ab oder ba), `[0-9]{3,5}` (drei bis fünf Ziffern). Der Satz von Kleene besagt: reguläre Ausdrücke und endliche Automaten beschreiben genau dieselbe Sprachklasse und sind ineinander überführbar. Anwendungen: lexikalische Analyse im Compilerbau, Mustersuche (grep/RegEx-Engines), Eingabevalidierung, Verifikation endlicher Protokollautomaten.

Als konkretes Beispiel (siehe Abb. zum DEA) erkennt folgender DEA L = {w ∈ {a,b} | w endet auf ab}: q0 (Start), q1 (zuletzt ein a gelesen), q2 (zuletzt „ab" gelesen, akzeptierend), mit den Übergängen q0 −a→ q1, q0 −b→ q0, q1 −a→ q1, q1 −b→ q2, q2 −a→ q1, q2 −b→ q0. Probelauf für „aab": q0 −a→ q1 −a→ q1 −b→ q2 — Endzustand q2 ∈ F, also akzeptiert; für „aba": q0 −a→ q1 −b→ q2 −a→ q1, Endzustand q1 ∉ F, also verworfen*.

Die Grenze des Modells: Ein DEA besitzt nur endlich viele Zustände und kann daher nicht unbeschränkt zählen — er kann sich nicht merken, wie viele a er gesehen hat. Deshalb ist L = {aⁿbⁿ | n ≥ 1} nicht regulär (kein endlicher Automat erkennt sie); bewiesen wird das mit dem Pumping-Lemma (siehe Abschnitt Kellerautomaten und Pumping-Lemma). Genau diese Lücke motiviert den Kellerautomaten, der über einen Stapel ein „Zählgedächtnis" erhält.

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 — ein DEA muss für jedes Symbol jedes Zustands definiert sein (sonst ist er nicht total).
NEA-Pfade als „muss auf allen Pfaden ankommen" interpretiert — gemeint ist, dass mindestens ein Pfad akzeptiert.
Akzeptanzkriterium am Eingabeende vergessen — akzeptiert wird nur, wenn das gesamte Wort gelesen wurde und der Automat dann in F steht.
NEA und DEA für unterschiedlich mächtig gehalten — sie erkennen exakt dieselben (regulären) Sprachen.
Reguläre Ausdrücke für „alles" gehalten — Klammerbalance/aⁿbⁿ ist nicht regulär.

LK-Vertiefung

eA-Vertiefung: Überführen Sie einen kleinen NEA per Potenzmengenkonstruktion in einen DEA (Zustände = erreichbare Teilmengen, ε-Hüllen bilden) und begründen Sie damit die Rabin–Scott-Äquivalenz. Konstruieren Sie zudem eine Sprachfamilie (z. B. „das k-letzte Symbol ist eine 1"), deren NEA k+1 Zustände hat, der minimale DEA aber 2^k — als Beispiel der exponentiellen Zustandsexplosion.

Aktive Wiederholung

Konstruieren Sie einen DEA für L = {w ∈ {0,1}* | w enthält genau drei Einsen} und geben Sie Zustandsübergangstabelle und -diagramm an; prüfen Sie anschließend die Wörter „11011" und „0111".

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Formale Grammatiken und Chomsky-Hierarchie#

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

Ableitungsbaum kontextfreier Grammatik

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

Während ein Automat eine Sprache erkennt, erzeugt eine formale Grammatik sie — beide sind zwei Sichten auf dieselbe Sprachklasse. Eine Grammatik ist ein 4-Tupel (V, Σ, P, S): die Variablen V (Nichtterminale, meist Großbuchstaben), die Terminale Σ (die Symbole der erzeugten Wörter), die Produktionen P (Ersetzungsregeln der Form „linke Seite → rechte Seite") und das Startsymbol S ∈ V. Eine Ableitung ersetzt, von S ausgehend, wiederholt eine linke Seite durch eine rechte, bis nur noch Terminale übrig sind; die erzeugte Sprache L(G) ist die Menge aller so ableitbaren Terminalwörter.

Die Chomsky-Hierarchie (Noam Chomsky 1956) ordnet Grammatiken nach der Strenge ihrer Regeln in vier echt ineinander geschachtelte Typen, jeder einem Automatenmodell zugeordnet: • Typ 0 (rekursiv aufzählbar, unbeschränkte Regeln) ↔ Turingmaschine • Typ 1 (kontextsensitiv, Regeln α → β mit |α| ≤ |β|) ↔ linear beschränkter Automat • Typ 2 (kontextfrei, Regeln A → β mit einer Variablen links) ↔ Kellerautomat • Typ 3 (regulär, Regeln A → aB bzw. A → a) ↔ endlicher Automat Es gilt Typ 3 ⊂ Typ 2 ⊂ Typ 1 ⊂ Typ 0: Je höher die Typnummer, desto strenger die Regeln und desto kleiner (spezieller) die Sprachklasse.

Eine kontextfreie (Typ-2-)Beispielsprache ist L = {aⁿbⁿ | n ≥ 1} mit der Grammatik S → aSb | ab. Sie ist Typ 2, weil jede linke Regelseite aus genau einer Variablen besteht. Ableitung von „aaabbb" (n = 3): S ⇒ aSb ⇒ aaSbb ⇒ aaabbb. Diese Sprache ist nicht regulär — ein endlicher Automat kann die Anzahl der a nicht zählen (Beweis mit dem Pumping-Lemma im Abschnitt Kellerautomaten); das ist das Standardbeispiel für die echte Trennung von Typ 2 und Typ 3.

Die Backus-Naur-Form (BNF) notiert kontextfreie Grammatiken kompakt — `::=` steht für „ist definiert als", `|` für die Alternative —, und die EBNF ergänzt Wiederholung und Option. BNF/EBNF spezifizieren die Syntax von Programmier- und Datenformaten (z. B. JSON, ECMAScript) und sind damit die formale Brücke zwischen Theorie und Compilerbau.

Der Ableitungsbaum (Parsebaum) macht die Struktur einer Erzeugung sichtbar: Die Wurzel ist S, innere Knoten sind Nichtterminale, die Blätter von links nach rechts ergeben das erzeugte Wort. Wichtig ist die Unterscheidung zwischen der Ableitung (einer Folge von Ersetzungsschritten, z. B. Links- oder Rechtsableitung) und dem Ableitungsbaum (der zugrunde liegenden Struktur) — der Operator „darstellen" verlangt den Baum. Eine Grammatik heißt mehrdeutig (ambig), wenn mindestens ein Wort zwei verschiedene Ableitungsbäume besitzt; das ist im Compilerbau unerwünscht (klassisch das „dangling else" oder Ausdrucksgrammatiken ohne Vorrangregeln) und wird durch Umschreiben der Grammatik beseitigt.

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 (kein Zählgedächtnis im endlichen Automaten).
Ableitung (Schrittfolge) statt Ableitungsbaum (Struktur) gezeigt — der Operator „darstellen" erwartet den Baum.
Mehrdeutigkeit der Grammatik übersehen — ein Wort kann mehrere Ableitungsbäume besitzen.
Typ-Zuordnung an der Sprache statt an der Regelform vorgenommen — entscheidend ist die Gestalt der Produktionen.
Variablen (Nichtterminale) und Terminale vertauscht — nur Terminale stehen im erzeugten Wort.

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.

Aktive Wiederholung

Modellieren Sie eine kontextfreie Grammatik für die Sprache L = {aⁿbⁿcᵐ | n, m ≥ 1} und zeichnen Sie den Ableitungsbaum für das Wort „aabbcc".

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Turingmaschine, Berechenbarkeit und Halteproblem#

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

Turingmaschinen-Band mit Lese-/Schreibkopf

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

Die Turingmaschine (Alan Turing, „On Computable Numbers", 1936) ist das mächtigste Modell der Hierarchie (Typ 0) und definiert formal, was überhaupt mechanisch berechenbar ist. Sie besteht aus einem beidseitig unendlichen Band aus Zellen, einem Lese-/Schreibkopf und einer endlichen Steuerung. Formal ist sie ein 7-Tupel (Q, Σ, Γ, δ, q₀, □, F): Zustände Q, Eingabealphabet Σ, Bandalphabet Γ ⊇ Σ (enthält das Blank-Symbol □), die Übergangsfunktion δ: Q×Γ → Q×Γ×{L, R} (lies das Symbol unter dem Kopf, schreibe ein Symbol, bewege den Kopf nach links/rechts, wechsle den Zustand), Startzustand q₀ und akzeptierende Zustände F.

Eine Konfiguration beschreibt den Gesamtzustand: aktueller Zustand, Bandinhalt und Kopfposition; ein Rechenschritt wendet δ einmal an. Es genügt dieses denkbar einfache Modell, um jede heutige Programmiersprache nachzubilden — und die universelle Turingmaschine, die eine beliebige Turingmaschine aus deren Beschreibung simuliert, ist das theoretische Vorbild des speicherprogrammierten von-Neumann-Rechners (Querverweis Systeme und Netze).

Die Church-Turing-These besagt: Jede intuitiv (effektiv) berechenbare Funktion ist Turing-berechenbar. Sie ist keine beweisbare Aussage (der Begriff „intuitiv berechenbar" ist nicht formal), sondern eine These — empirisch aber unangefochten, weil jedes ernsthaft vorgeschlagene Berechnungsmodell (λ-Kalkül, μ-rekursive Funktionen, Registermaschinen, jede reale Programmiersprache) sich als genau gleich mächtig wie die Turingmaschine erwiesen hat.

Eine Sprache L heißt entscheidbar, wenn eine Turingmaschine bei jeder Eingabe terminiert und korrekt „akzeptiert" oder „verwirft". Schwächer ist semi-entscheidbar (rekursiv aufzählbar): Die Maschine hält und akzeptiert für Wörter in L, darf für Wörter außerhalb L aber ewig laufen. Es gilt: entscheidbar ⊂ semi-entscheidbar — und genau diese Lücke macht das Halteproblem so wichtig.

Das Halteproblem fragt: Hält ein beliebiges Programm P bei Eingabe w, oder läuft es ewig? Turing 1936: Das Halteproblem ist unentscheidbar — es gibt keine total berechenbare Funktion H(P, w), die das für alle P und w stets korrekt mit „hält"/„hält nicht" beantwortet. Das ist eine prinzipielle Grenze, kein Mangel an Cleverness oder Rechenleistung.

Die Beweisidee ist ein Widerspruch per Diagonalisierung: Angenommen, ein solches H existiert. Dann konstruiere ein Programm D, das auf eine Programmbeschreibung x angewandt das Gegenteil von H(x, x) tut — falls H(x, x) = „hält", läuft D endlos; sonst hält D. Nun betrachte den Selbstaufruf D(D): Sagt H „D(D) hält", so läuft D laut Konstruktion endlos (hält also nicht) — Widerspruch; sagt H „D(D) hält nicht", so hält D — wieder Widerspruch. Da beide Fälle scheitern, kann H nicht existieren (siehe das nebenstehende Rechenbeispiel).

Die Konsequenz verallgemeinert der Satz von Rice (1953): Jede nicht-triviale semantische Eigenschaft von Programmen ist unentscheidbar — etwa „gibt P je 0 aus?", „sind P und Q äquivalent?", „ist diese Code-Stelle erreichbar?". Daher kann es keine allgemeine, perfekte statische Analyse geben (kein vollautomatischer Korrektheitsbeweis für beliebigen Code, keine perfekte Virenerkennung). Eingeschränkte, konservative Verfahren bleiben aber möglich: Sie entscheiden eine Teilklasse oder approximieren sicher (z. B. „beweise Terminierung über eine erkannte Terminierungsfunktion, sonst antworte unbekannt").

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

Unentscheidbarkeit des Halteproblems

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

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 der Terminationsanalyse eines konkreten Programms verwechselt — für einzelne Programme ist die Frage oft entscheidbar, nur nicht allgemein für ALLE.
Church-Turing-These als Theorem ausgegeben — sie ist eine (nicht beweisbare) These.
Diagonalisierungsbeweis ohne den Selbstaufruf D(D) und den beidseitigen Widerspruch abgekürzt.
„Unentscheidbar" als „sehr schwer / dauert lange" missverstanden — es heißt: prinzipiell von KEINEM Algorithmus lösbar.
Entscheidbar und semi-entscheidbar gleichgesetzt — bei semi-entscheidbar darf die Maschine außerhalb L ewig laufen.

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.

Aktive Wiederholung

Erläutern Sie die Unentscheidbarkeit des Halteproblems anhand der Diagonalisierung und beurteilen Sie eine konkrete Konsequenz für die Compilerbau-Praxis.

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

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

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

Die Komplexitätstheorie fragt nicht mehr „ist es berechenbar?", sondern „ist es effizient berechenbar?" — gemessen an der Worst-Case-Laufzeit als Funktion der Eingabegröße n. Als Faustregel für „praktikabel/handhabbar" gilt polynomielle Laufzeit O(n^k) (These von Cobham–Edmonds), während exponentielle Verfahren schon bei mittlerem n unbezahlbar werden (vgl. die Wachstumsklassen im Topic Algorithmen).

Die Klasse P umfasst alle Entscheidungsprobleme, die eine deterministische Turingmaschine in polynomieller Zeit löst — die „leicht lösbaren" Probleme wie Sortieren, kürzeste Wege, das Matching oder der Primzahltest (AKS 2002). Die Klasse NP umfasst Probleme, deren Ja-Instanzen sich mit einem Zertifikat (einem vorgeschlagenen Lösungskandidaten) in polynomieller Zeit verifizieren lassen; äquivalent: Probleme, die eine nichtdeterministische Turingmaschine in polynomieller Zeit entscheidet. NP steht also für „nichtdeterministisch polynomiell", NICHT für „nicht polynomiell" — der Kern ist die schnelle Prüfung, nicht die schnelle Lösung. Anschauung: Ein gefülltes Sudoku ist trivial zu prüfen, das Lösen erscheint schwer.

Offensichtlich gilt P ⊆ NP (wer schnell lösen kann, kann auch schnell prüfen — er rechnet die Lösung einfach nach). Ob auch P = NP gilt, ist eine der größten offenen Fragen der Informatik und eines der sieben Millennium-Probleme (Clay Mathematics Institute, 2000, ausgeschrieben mit 1 Mio. US-Dollar). Die ganz überwiegende Vermutung lautet P ≠ NP — bewiesen ist sie nicht.

Die NP-vollständigen Probleme sind die schwersten in NP: Jedes Problem aus NP lässt sich in polynomieller Zeit auf sie reduzieren. Daraus folgt die Schlüsseleigenschaft — fände man für ein einziges NP-vollständiges Problem einen polynomiellen Algorithmus, so wäre P = NP und alle NP-Probleme effizient lösbar. Der Satz von Cook–Levin (1971) wies als erstes Problem SAT (Erfüllbarkeit aussagenlogischer Formeln) als NP-vollständig nach; Karp (1972) ergänzte 21 weitere.

Klassische NP-vollständige Probleme sind SAT, 3-SAT, das Problem des Handlungsreisenden (Travelling Salesman, Entscheidungsversion „Gibt es eine Rundreise ≤ k?"), Vertex Cover, Subset Sum, Graphfärbung, der Hamiltonkreis und verallgemeinertes Sudoku. Scharf zu trennen ist NP-schwer (mindestens so schwer wie alle NP-Probleme, eventuell außerhalb NP — etwa die TSP-Optimierungsversion oder das Halteproblem) von NP-vollständig (NP-schwer und selbst in NP).

Die praktische Konsequenz: Für NP-vollständige Probleme ist kein effizientes (polynomielles) Verfahren bekannt — bewiesen unmöglich ist es aber nicht. Man behilft sich mit Heuristiken, Approximationsalgorithmen (mit Gütegarantie), in der Praxis schnellen SAT-/ILP-Solvern oder schränkt die Eingabe ein. Kryptographischer Bezug: Die Sicherheit von RSA stützt sich darauf, dass die Faktorisierung großer Zahlen praktisch schwer ist (Querverweis Kryptographie); ein Beweis P = NP mit konstruktivem Verfahren würde viele kryptographische Annahmen erschüttern — wobei die Faktorisierung zwar in NP liegt, aber nicht als NP-vollständig bekannt ist.

Typische Fehler

„NP" als „nicht polynomiell" interpretiert — tatsächlich „nichtdeterministisch polynomiell" (schnelle Verifikation).
NP-schwer mit NP-vollständig gleichgesetzt — NP-vollständig liegt in NP, NP-schwer kann außerhalb NP liegen.
Travelling Salesman als „in NP, nicht in P" behauptet, als wäre das bewiesen — korrekt: „in NP, aber nicht bekannt in P".
P ⊆ NP für „bewiesen P ≠ NP" gehalten — die Gleichheit ist offen, nur die Inklusion P ⊆ NP ist klar.
Optimierungs- und Entscheidungsversion vermischt — NP/NP-vollständig sind über Entscheidungsprobleme definiert.

LK-Vertiefung

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

Aktive Wiederholung

Beurteilen Sie, warum das Problem „Existiert ein Hamiltonkreis in Graph G?" als NP-vollständig gilt; diskutieren Sie die Konsequenzen für praktische Routenplanungsanwendungen.

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Kellerautomaten und das Pumping-Lemma#

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

Kellerautomat (PDA) für L = { aⁿbⁿ | n ≥ 1 }

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

Ein Kellerautomat (PDA, pushdown automaton) erweitert den endlichen Automaten um einen unbeschränkten Stapel (Keller) nach dem LIFO-Prinzip — und genau dieser Stapel ist das „Zählgedächtnis", das dem endlichen Automaten fehlt. Der PDA erkennt exakt die kontextfreien Sprachen (Typ 2) und ist damit das Maschinenmodell zur Typ-2-Grammatik. Eine Besonderheit (anders als beim endlichen Automaten): Der nichtdeterministische PDA ist echt mächtiger als der deterministische; deterministische PDA erkennen nur eine Teilklasse (die deterministisch kontextfreien Sprachen).

Eine Konfiguration des PDA besteht aus dem aktuellen Zustand, der restlichen Eingabe und dem Kellerinhalt. Ein Übergang darf das oberste Kellersymbol lesen und es entfernen (pop) oder durch eine Symbolfolge ersetzen (push); ε-Übergänge erlauben Kelleroperationen ohne Eingabe zu lesen. Akzeptiert wird wahlweise über Endzustand oder über leeren Keller (am Eingabeende). Ein Bodensymbol markiert den anfänglich leeren Keller.

Am Beispiel L = {aⁿbⁿ | n ≥ 1}: Der PDA legt für jedes gelesene `a` ein Symbol auf den Keller und entfernt für jedes `b` eines; er akzeptiert, wenn der Keller genau dann leer ist, wenn die Eingabe endet (gleich viele a wie b, in der richtigen Reihenfolge). Ein endlicher Automat kann das nicht — ihm fehlt das Gedächtnis für die unbeschränkte Anzahl. Das ist die konkrete, anschauliche Begründung, warum {aⁿbⁿ} Typ 2 (kontextfrei) und nicht Typ 3 (regulär) ist.

Dass {aⁿbⁿ} nicht regulär ist, beweist man mit dem Pumping-Lemma für reguläre Sprachen — einem notwendigen Kriterium: Zu jeder regulären Sprache L existiert eine Pumping-Länge n, sodass sich jedes Wort z ∈ L mit |z| ≥ n zerlegen lässt als z = uvw mit (1) |uv| ≤ n, (2) |v| ≥ 1 und (3) uvⁱw ∈ L für alle i ≥ 0 (der mittlere Teil v lässt sich beliebig oft „aufpumpen" oder weglassen, ohne L zu verlassen).

Daraus wird ein Widerspruchsbeweis der Nicht-Regularität — wichtig ist die Rollenverteilung wie in einem Spiel: Der „Gegner" liefert n und (später) die Zerlegung, du wählst geschickt ein Wort und das i. Schema: (1) Annahme, L sei regulär, also existiert ein n. (2) Wähle ein konkretes z ∈ L mit |z| ≥ n. (3) Betrachte alle zulässigen Zerlegungen z = uvw mit |uv| ≤ n, |v| ≥ 1. (4) Finde zu jeder ein i, sodass uvⁱw ∉ L. (5) Widerspruch zur Pumping-Eigenschaft ⇒ L ist nicht regulär.

Durchgeführt für L = {aⁿbⁿ}: Annahme regulär, Pumping-Länge n, wähle z = aⁿbⁿ (|z| = 2n ≥ n). Da |uv| ≤ n, liegt v vollständig im a-Block, also v = a^k mit k ≥ 1. Pumpe i = 2: uv²w = a^(n+k) bⁿ hat mehr a als b und liegt damit nicht in L — Widerspruch. Also ist {aⁿbⁿ} nicht regulär. Für kontextfreie Sprachen gibt es ein eigenes Pumping-Lemma (z = uvwxy, v und x werden gemeinsam gepumpt); damit zeigt man z. B., dass L = {aⁿbⁿcⁿ} nicht kontextfrei ist. Achtung: Das Pumping-Lemma ist stets nur notwendig — besteht eine Sprache den Pump-Test, ist sie deshalb noch nicht als regulär (bzw. kontextfrei) bewiesen.

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 (|uv| ≤ n, |v| ≥ 1).
Kellerautomat ohne Bodensymbol oder ohne definiertes Akzeptanzkriterium (Endzustand bzw. leerer Keller) angegeben.
Wort z mit |z| < n gewählt — die Voraussetzung |z| ≥ n wird verletzt, der Beweis ist hinfällig.
v in einen gemischten a/b-Bereich gelegt, statt aus |uv| ≤ n zu folgern, dass v nur aus a besteht.

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.

Aktive Wiederholung

Beweisen Sie mit dem Pumping-Lemma für reguläre Sprachen, dass L = {aᵏbᵏ | k ≥ 0} nicht regulär ist, und modellieren Sie anschließend einen Kellerautomaten, der L erkennt.

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

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

StandardNRW-IF4BY-Inf-5

DEA für L = { w ∈ {a,b}* | w endet auf ab }

Abb. 5Übergangstabelle des deterministischen endlichen Automaten mit drei Zuständen: δ(Zustand, Eingabe) = Folgezustand. Startzustand q0, akzeptierender Zustand q2 (erreicht nach „ab"). Beispiel „aab": q0 → q1 → q1 → q2 ⇒ akzeptiert.

Die Kleene-Äquivalenz schließt den Kreis der regulären Welt: Reguläre Ausdrücke, NEA und DEA beschreiben exakt dieselbe Sprachklasse (die regulären Sprachen) und lassen sich verlustfrei ineinander überführen — drei Darstellungen desselben Gegenstands, je nach Aufgabe wählt man die handlichste.

Die Konstruktionswege sind: regulärer Ausdruck → NEA per Thompson-Konstruktion (Bausteine mit ε-Übergängen für Verkettung, Alternative und Stern), NEA → DEA per Potenzmengenkonstruktion, NEA mit ε → NEA ohne ε per ε-Hülle, und DEA → regulärer Ausdruck per Zustandselimination (Kleene-Algorithmus). So gelangt man von jeder Darstellung zu jeder anderen.

Die Minimierung eines DEA läuft in zwei Schritten: (1) unerreichbare Zustände entfernen (vom Start aus nie betretbar), (2) äquivalente Zustände verschmelzen — zwei Zustände sind äquivalent, wenn sie für jedes Restwort dasselbe Akzeptanzverhalten zeigen. Praktisch nutzt man das Tabellenfüllverfahren: Man markiert zuerst alle Paare (akzeptierend, nicht-akzeptierend) als unterscheidbar und propagiert die Unterscheidbarkeit dann iterativ über die Übergänge, bis nichts Neues mehr markiert wird; die nicht markierten Paare sind äquivalent und werden verschmolzen.

Der Satz von Myhill–Nerode liefert die theoretische Grundlage: Er charakterisiert reguläre Sprachen über die Rechtskongruenz (zwei Wörter sind äquivalent, wenn sie sich durch keine Fortsetzung bezüglich L unterscheiden lassen). Es gilt: L ist regulär genau dann, wenn diese Relation endlich viele Äquivalenzklassen hat, und ihre Anzahl ist genau die Zustandszahl des minimalen DEA. Das gibt zugleich ein zweites, elegantes Nicht-Regularitäts-Argument: {aⁿbⁿ} hat unendlich viele Klassen (jedes aⁿ ist von jedem anderen unterscheidbar) und ist daher nicht regulär.

Der minimale DEA ist bis auf Umbenennung der Zustände eindeutig — eine Normalform der regulären Sprache. Daraus folgt ein praktisches Äquivalenzverfahren: Zwei Automaten erkennen genau dann dieselbe Sprache, wenn ihre minimalen DEA isomorph sind. Anwendungen sind die Optimierung von Lexern/Scannern im Compilerbau, RegEx-Engines und die Verifikation endlicher Protokoll- und Schaltungsautomaten.

Typische Fehler

Bei der Potenzmengenkonstruktion den Fangzustand (für fehlende Übergänge) vergessen.
Unerreichbare Zustände bei der Minimierung nicht zuerst entfernt.
Äquivalente Zustände zu früh verschmolzen, ohne das Akzeptanzverhalten für ALLE Restwörter zu prüfen.
Akzeptierende und nicht-akzeptierende Zustände im Tabellenfüllverfahren als potenziell äquivalent behandelt — sie sind sofort unterscheidbar.
Reguläre Ausdrücke und kontextfreie Grammatiken verwechselt — Klammerbalance/aⁿbⁿ 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.

Aktive Wiederholung

Stellen Sie für den regulären Ausdruck (a|b)*abb einen NEA auf, überführen Sie ihn per Potenzmengenkonstruktion in einen DEA und minimieren Sie diesen.

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.