Notizen · InformatikAT · Matura

INF-Th - Theoretische Informatik

Automaten, formale Sprachen, Berechenbarkeit und Komplexitätstheorie geben Antworten auf "Was ist berechenbar?" und "Was ist effizient berechenbar?".

3Abschnitteca. 9Min Lesezeit4KompetenzenNiveauStandard 1 · Vertiefung 2Stand 06/2026

T·0888 / 12

Prüfungsprofil

INF-Th-1 · Endliche Automaten und reguläre Sprachen unterscheidenINF-Th-2 · Kellerautomaten und kontextfreie Sprachen kennenINF-Th-3 · Berechenbarkeit und Halteproblem verstehenINF-Th-4 · P, NP und NP-vollständige Probleme einordnen

Tiefe

Schrift

Inhalt · 3 Abschnitte

INF-Th - Theoretische Informatik

Endliche Automaten und reguläre Sprachen#

StandardINF-Th-1.1

Die theoretische Informatik fragt, was Maschinen überhaupt berechnen können - und beginnt beim einfachsten Modell, dem endlichen Automaten. Er besitzt nur endlich viele Zustände und keinen zusätzlichen Speicher; sein „Gedächtnis" ist allein der aktuelle Zustand ().

DFA für Sprache aller Bitfolgen mit gerader Anzahl Einsen

Abb. 1Zwei Zustände: q0 (gerade), q1 (ungerade); Akzeptanz in q0.

Ein DFA (deterministischer endlicher Automat) ist formal das Tupel

M=(Q,\Sigma,\delta,q_{0},F)

: Zustände

Q

, Eingabealphabet

\Sigma

, Übergangsfunktion

\delta: Q\times\Sigma \to Q

, Startzustand

q_{0}

und Endzustände

F

. Er liest die Eingabe Zeichen für Zeichen, wechselt deterministisch den Zustand und akzeptiert, wenn er nach dem letzten Zeichen in einem Endzustand steht.

Ein NFA (nichtdeterministisch) darf zu einem Zeichen mehrere Folgezustände haben (und ε-Übergänge). Er ist trotzdem nicht mächtiger: Jeder NFA lässt sich per Potenzmengenkonstruktion in einen äquivalenten DFA übersetzen - NFAs sind nur oft kompakter zu entwerfen.

Reguläre Ausdrücke beschreiben dieselbe Sprachklasse algebraisch: Verkettung (`ab`), Alternative (`a|b`), Stern (`a`, beliebig oft) und Klammern. Der Satz von Kleene sichert die Gleichmächtigkeit zu: Eine Sprache ist genau dann regulär*, wenn ein endlicher Automat sie erkennt bzw. ein regulärer Ausdruck sie beschreibt (siehe Beispiel).

Endliche Automaten können nicht zählen, weil ihr Gedächtnis endlich ist. Die Sprache

\{a^{n}b^{n} \mid n \geq 0\}

(gleich viele a wie b) ist daher nicht regulär - man bräuchte einen Zähler, also einen Kellerautomaten mit Stack. Solche Nicht-Regularität beweist man mit dem Pumping-Lemma.

Anwendungen sind allgegenwärtig: der Lexer in Compilern, Suchmuster (grep) und Eingabevalidierung (etwa E-Mail-Format). Häufige Fehler: NFA und DFA gleichsetzen, die Akzeptanzbedingung vergessen (Endzustand erst nach der gesamten Eingabe), oder regex `a+` (mindestens eins) und `a*` (auch null) verwechseln.

M = (Q,\Sigma,\delta,q_{0},F),\quad \delta: Q\times\Sigma \to Q

Definition eines deterministischen endlichen Automaten

Musterbeispiel

Regulärer Ausdruck und Sprache

Beschreibe die Sprache des regulären Ausdrucks `(0|1)*1` und gib einen DFA an.

Sprache interpretieren
$(0|1)^{*}$ steht für beliebig viele 0/1; das angehängte 1 erzwingt, dass das letzte Zeichen 1 ist.
Beispiele
"1", "01", "11", "001", "10101" gehören dazu; "10", "0", "100" nicht.
DFA-Zustände
q0 = "letzter Buchstabe = 0 oder leer" (nicht akzeptierend), q1 = "letzter Buchstabe = 1" (akzeptierend).
Übergänge
q0 --0--> q0, q0 --1--> q1; q1 --0--> q0, q1 --1--> q1. Startzustand q0, F = {q1}.

Ergebnis: Sprache aller Bitstrings, die mit 1 enden. Reguläre Sprachen entsprechen genau den DFA-akzeptierten Sprachen (Satz von Kleene).

Schritt-für-Schritt Erklärung3 Schritte

1
Endliche Automaten sind das einfachste Berechnungsmodell - sie merken sich nur einen Zustand.
DFA für Sprache aller Bitfolgen mit gerader Anzahl Einsen
Abb.Zwei Zustände: q0 (gerade), q1 (ungerade); Akzeptanz in q0.
2
Reguläre Ausdrücke sind dieselbe Macht wie endliche Automaten - das ist der Satz von Kleene.
3
Sobald du zählen musst (z.B. Klammern), reicht ein DFA nicht mehr - du brauchst einen Kellerautomaten.

SRDP-Aufgaben

SelbsttestAus der Fragenbank7 Punkte

Aufgabenstellung

Erkläre den Begriff "endlicher Automat". Konstruiere einen DFA für die Sprache aller Binärstrings mit gerader Anzahl Einsen.

Deine Antwortwird nicht automatisch bewertet

Typische Fehler

NFA mit DFA gleichgesetzt und immer mehrere Folgezustände erlaubt.
Akzeptanzbedingung vergessen (Endzustand nach kompletter Eingabe).
Regex `a+` und `a` verwechselt (+ = mindestens 1, = mindestens 0).

Aktive Wiederholung

Konstruiere einen DFA, der genau die Strings akzeptiert, die mit "ab" beginnen und mit "ba" enden (Alphabet {a,b}).

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Quellen: Sipser: Introduction to the Theory of Computation (Cengage)

Berechenbarkeit und Halteproblem#

VertiefungINF-Th-3.1

Manche Probleme sind nicht nur teuer, sondern grundsätzlich unlösbar - kein Algorithmus kann sie für alle Eingaben korrekt entscheiden. Die Berechenbarkeitstheorie zieht genau diese Grenze des überhaupt Machbaren.

Eine Funktion heißt berechenbar, wenn es einen Algorithmus (formalisiert als Turingmaschine) gibt, der sie für jede Eingabe in endlich vielen Schritten berechnet. Bei Entscheidungsproblemen (Ja/Nein-Fragen) spricht man von entscheidbar.

Die Church-Turing-These behauptet, dass alles intuitiv „Berechenbare" genau dem Turing-Berechenbaren entspricht - ob man Turingmaschinen, λ-Kalkül oder reale Programmiersprachen nimmt, sie alle erfassen dieselbe Klasse. Sie ist eine These (nicht beweisbar, aber bislang unwiderlegt).

Man unterscheidet drei Stufen (): entscheidbar (der Algorithmus hält immer mit ja/nein), semi-entscheidbar (er hält bei „ja", läuft bei „nein" aber eventuell ewig) und unentscheidbar (kein Algorithmus bewältigt alle Eingaben).

Entscheidbarkeitsklassen

Abb. 2Probleme lassen sich nach der Stärke des möglichen Algorithmus einordnen.

Das berühmteste unentscheidbare Problem ist das Halteproblem: Kein Programm kann für jedes Programm

P

und jede Eingabe

x

entscheiden, ob

P

bei

x

hält. Der Beweis per Diagonalisierung (Turing 1936) nimmt einen solchen Entscheider an und baut daraus ein Programm, das sich selbst widerspricht (siehe Beispiel). Nach dem Satz von Rice sind auch Programmäquivalenz und „erreicht Zeile X je?" unentscheidbar.

Praktische Folge: Kein Werkzeug kann jeden Bug oder jede Endlosschleife finden - aber statische Analyse, Linter und Typsysteme entscheiden viele Fälle korrekt (konservativ, mit Fehlalarmen). Häufige Fehler: Unentscheidbarkeit für „zu schwer für heutige Rechner" halten (sie ist prinzipiell, keine Frage der Leistung), das Halteproblem auf eine einzelne Sprache beziehen, oder Berechenbarkeit mit Effizienz verwechseln.

Musterbeispiel

Halteproblem - Beweisidee

Skizziere den Beweis (Diagonalisierung), dass das Halteproblem unentscheidbar ist.

Annahme
Es gibt ein Programm H(P, x), das für jedes Programm P und Eingabe x in endlicher Zeit ja/nein liefert, ob P bei x hält.
Konstruktion D
Definiere D(P): wenn H(P, P) = "hält" -> Endlosschleife; sonst -> halten.
Anwenden auf D selbst
Was sagt H(D, D)?
Widerspruch
Wenn H(D,D) = "hält": dann macht D bei Eingabe D Endlosschleife - Widerspruch. Wenn H(D,D) = "hält nicht": dann hält D bei D - Widerspruch.

Ergebnis: Beide Fälle führen zum Widerspruch. Folglich existiert H nicht. Das Halteproblem ist unentscheidbar (Turing 1936).

Schritt-für-Schritt Erklärung3 Schritte

1
Berechenbarkeit fragt: lässt sich etwas überhaupt berechnen? Komplexität fragt: wie schnell?
2
Das Halteproblem ist das berühmteste Beispiel eines unlösbaren Problems.
3
Die Diagonalargumentation von Turing ist eine der elegantesten Beweisideen der Informatik.

SRDP-Aufgaben

SelbsttestAus der Fragenbank7 Punkte

Aufgabenstellung

Erläutere die Begriffe Berechenbarkeit und Entscheidbarkeit. Skizziere den Beweis, dass das Halteproblem unentscheidbar ist, und nenne praktische Konsequenzen.

Deine Antwortwird nicht automatisch bewertet

Typische Fehler

Unentscheidbarkeit wird als "zu schwer für heutige Computer" missverstanden.
Halteproblem nur in einer Sprache (z.B. nur Python) angenommen.
Berechenbarkeit mit Effizienz verwechselt.

Aktive Wiederholung

Erkläre die Konsequenzen der Unentscheidbarkeit des Halteproblems für die Softwareentwicklung. Warum gibt es trotzdem statische Codeanalyse?

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Quellen: Turing: On Computable Numbers (1936) (Proc. London Math. Soc.)

P, NP und NP-vollständige Probleme#

VertiefungINF-Th-4.1

Während die Berechenbarkeit fragt „überhaupt lösbar?", fragt die Komplexitätstheorie „effizient lösbar?". Die zentrale Trennlinie verläuft zwischen den Klassen P und NP ().

Komplexitätshierarchie P, NP, NP-vollständig, NP-schwer

Abb. 3P ⊆ NP; NP-vollständige Probleme bilden den schwierigsten Teil von NP.

P ist die Klasse der Entscheidungsprobleme, die sich in polynomieller Zeit lösen lassen (

O(n^{k})

). „Polynomiell" gilt als praktisch handhabbar - Sortieren, kürzeste Wege und der Primzahltest liegen in P.

NP ist die Klasse der Probleme, deren Lösung sich in polynomieller Zeit verifizieren lässt, auch wenn das Finden schwer scheint. NP steht für „nichtdeterministisch polynomiell", nicht für „nicht polynomiell" - ein verbreitetes Missverständnis. Eine erfüllende SAT-Belegung zu prüfen ist leicht, sie zu finden vermutlich schwer (siehe Beispiel).

Offensichtlich gilt

P \subseteq NP

(was man lösen kann, kann man auch verifizieren). Ob umgekehrt

NP \subseteq P

, also P = NP, ist seit 1971 offen und eines der mit je 1 Mio. Dollar dotierten Millennium-Probleme; die meisten Fachleute vermuten

P \neq NP

Ein Problem ist NP-vollständig, wenn es (a) in NP liegt und (b) sich jedes andere NP-Problem in polynomieller Zeit darauf reduzieren lässt - es ist also „mindestens so schwer" wie alle NP-Probleme. SAT war das erste (Satz von Cook-Levin); weitere Klassiker sind 3-SAT, TSP (Travelling Salesman), Subset Sum und das Cliquen-Problem. Die Tragweite: Fände man für ein NP-vollständiges Problem einen Polynomialalgorithmus, wäre sofort

P=NP

Solange

P \neq NP

gilt, behilft man sich bei NP-schweren Problemen mit Approximationsalgorithmen, Heuristiken und leistungsfähigen SAT-Solvern, die viele reale Instanzen schnell lösen. Häufige Fehler: NP als „nicht polynomiell" deuten, NP-vollständig mit unentscheidbar gleichsetzen (NP-Probleme sind lösbar, nur evtl. langsam), oder eine Approximation für die exakte Lösung halten.

P \subseteq NP \subseteq EXPTIME

Hierarchie der Komplexitätsklassen

Musterbeispiel

Eine SAT-Belegung verifizieren (Zertifikat)

Prüfe, ob die Belegung $x_{1}=1,\ x_{2}=0,\ x_{3}=1$ die Formel $(x_{1} \lor \lnot x_{2}) \land (\lnot x_{1} \lor x_{3}) \land (x_{2} \lor x_{3})$ erfüllt.

Klausel 1
$(x_{1} \lor \lnot x_{2}) = (1 \lor \lnot 0) = (1 \lor 1) = 1$ .
Klausel 2
$(\lnot x_{1} \lor x_{3}) = (\lnot 1 \lor 1) = (0 \lor 1) = 1$ .
Klausel 3
$(x_{2} \lor x_{3}) = (0 \lor 1) = 1$ .
Konjunktion
Alle Klauseln sind erfüllt: $1 \land 1 \land 1 = 1$ - die Belegung erfüllt die Formel.
Bedeutung
Das Prüfen einer gegebenen Belegung kostet nur $O(\text{Anzahl Klauseln})$ - deshalb liegt SAT in NP. Eine erfüllende Belegung zu finden erfordert im Worst Case das Durchsuchen von $2^{n}$ Kombinationen.

Ergebnis: Die Belegung $x_{1}=1, x_{2}=0, x_{3}=1$ ist ein „Zertifikat", das die Erfüllbarkeit in linearer Zeit nachweist. Verifizieren ist leicht (NP), Finden ist schwer - SAT ist NP-vollständig (Cook-Levin).

Schritt-für-Schritt Erklärung3 Schritte

1
P und NP sind die zwei wichtigsten Komplexitätsklassen - sie definieren, was praktisch lösbar ist.
Komplexitätshierarchie P, NP, NP-vollständig, NP-schwer
Abb.P ⊆ NP; NP-vollständige Probleme bilden den schwierigsten Teil von NP.
2
NP-vollständig heisst: ist eines davon effizient lösbar, sind sie alle effizient lösbar.
3
Solange P != NP gilt, vertrauen wir auf approximative Lösungen, Heuristiken und SAT-Solver.

SRDP-Aufgaben

SelbsttestAus der Fragenbank7 Punkte

Aufgabenstellung

Erkläre die Komplexitätsklassen P und NP. Was bedeutet NP-vollständig? Diskutiere die Bedeutung der offenen Frage P = NP an einem Beispiel.

Deine Antwortwird nicht automatisch bewertet

Typische Fehler

NP wird als "nicht polynomiell" interpretiert (richtig: "nichtdeterministisch polynomiell").
NP-vollständig wird mit "unentscheidbar" gleichgesetzt.
Approximationsalgorithmen werden mit exakter Lösung verwechselt.

Aktive Wiederholung

Erkläre, warum SAT NP-vollständig ist (Satz von Cook-Levin). Welche praktischen Strategien wendet man auf NP-schwere Probleme an?

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Quellen: Cook: The Complexity of Theorem-Proving Procedures (STOC 1971) · Clay Mathematics Institute - P vs NP Problem (CMI)

Belege & Quellen

Quellen

Cengage

Sipser: Introduction to the Theory of Computation

Proc. London Math. Soc.

Turing: On Computable Numbers (1936)

STOC 1971

Cook: The Complexity of Theorem-Proving Procedures

CMI

Clay Mathematics Institute - P vs NP Problem