Endliche Automaten und formale Sprachen: Grammatiken und Regex

Kurz: Endliche Automaten erkennen einfache Sprachmuster (reguläre Ausdrücke), Kellerautomaten und kontextfreie Grammatiken beschreiben Programmiersprachen, Turingmaschinen berechnen alles Berechenbare.

Genauer: Die theoretische Informatik erklärt, was Rechner prinzipiell können. Praxis: Regex, Parser/Compiler, Protokolle, Spiele-KI (Zustandsautomaten) und Prüfungsthemen (Zustandsdiagramme).

Im Detail

Endlicher Automat (DFA/NFA)

Ein endlicher Automat hat Zustände, ein Alphabet, Übergänge, einen Startzustand und Endzustände. Er liest ein Wort Zeichen für Zeichen und akzeptiert, wenn er in einem Endzustand endet. Beispiel: Binärwörter mit gerader Anzahl Einsen: Zustände gerade (Start, Ende) und ungerade; bei 1 wechseln, bei 0 bleiben. DFA (deterministisch) vs. NFA (nichtdeterministisch, mehrere Folgezustände/ε-Übergänge): beide erkennen dieselben Sprachen (reguläre Sprachen), NFA lassen sich in DFA umbauen (Potenzmengenkonstruktion). Er hat keinen Speicher außer dem aktuellen Zustand: Er kann nicht „gleich viele a und b“ zählen.

Reguläre Ausdrücke

Äquivalent zu endlichen Automaten: a|b, a*, a+, a?, [0-9]{4}. Engines wandeln Regex in Automaten um (Thompson-Konstruktion). Praktische Regex haben Rückverweise/Lookahead und sind mächtiger/unsicherer (ReDoS: katastrophales Backtracking). Grenzen: Verschachtelte Klammern, HTML/JSON/Programmcode sind nicht regulär: dafür braucht man einen Parser.

Chomsky-Hierarchie

1. Typ 3 – Regulär (Automat, Regex): Tokens, Zahlen, E-Mail-Muster.
2. Typ 2 – Kontextfrei (Kellerautomat, Grammatik wie BNF/EBNF): Programmiersprachen, JSON, Klammerausdrücke.
3. Typ 1 – Kontextsensitiv.
4. Typ 0 – Allgemein (Turingmaschine). Beispiel Grammatik: Ausdruck → Zahl | Ausdruck '+' Ausdruck | '(' Ausdruck ')' (erzeugt Klammer-/Summenausdrücke). Compiler: Lexer (Typ 3) → Parser (Typ 2) → Syntaxbaum.

Turingmaschine und Grenzen

• Turingmaschine: Band, Schreib-/Lesekopf, Zustände; Modell dessen, was berechenbar ist (Church-Turing-These). Jede Programmiersprache ist Turing-vollständig (mit Schleife/Speicher).
• Halteproblem: Es gibt kein Programm, das für jedes Programm entscheidet, ob es anhält (unentscheidbar).
• Komplexitätsklassen P, NP (siehe P-und-NP).
• Praxis: Zustandsautomaten (Ampel, Spiel-KI, Protokolle, UI-Zustände), Parser-Generatoren (ANTLR), Syntax-Highlighter, Validierung von Eingaben.
• Prüfung (IHK/AP): Zustandsdiagramm lesen/zeichnen, Wort prüfen, Regex deuten.

Siehe auch: Regex, Lexer, Parser und Syntaxbaum, Zustandsautomat, P und NP