MINT lernen

Kontextfreie Grammatiken

S → aSb: Eine einzige Regel schafft, woran jeder DEA scheitert — und wer merkt sich die offenen b?

1

Nichtterminale in der Mitte

In einer kontextfreien Grammatik darf die rechte Seite einer Regel beliebig aussehen — auch Nichtterminale in der Mitte oder mehrere hintereinander sind erlaubt.

  • Kontextfreie Grammatik:jede Regel hat links genau ein Nichtterminal und rechts ein beliebiges Wort aus Terminalen und Nichtterminalen (auch \(\varepsilon\)).
  • Kontextfrei:ein Nichtterminal wird ersetzt, egal was links und rechts von ihm steht.
  • Regulär ⊂ kontextfrei:jede reguläre Grammatik ist kontextfrei — umgekehrt nicht.
  • Linksableitung:in jedem Schritt wird das am weitesten links stehende Nichtterminal ersetzt.
  • Ableitungsbaum:Wurzel \(S\), innere Knoten sind Nichtterminale, die Blätter von links nach rechts ergeben das Wort.

Herleitung:

\(S\)
Start
Grammatik: \(S\to aSb\mid\varepsilon\), Startsymbol \(S\).
\(a\textcolor{#7c5fb5}{S}b\)
\(S\to aSb\)
Jedes a bringt ein b auf der anderen Seite mit.
\(aa\textcolor{#7c5fb5}{S}bb\)
\(S\to aSb\)
Das Nichtterminal bleibt in der Mitte — links wachsen die a, rechts die b.
\(a^n\textcolor{#7c5fb5}{S}b^n\)
\(n\)-mal
Nach \(n\) Anwendungen stehen gleich viele a und b um S herum.
\(a^nb^n\)
\(S\to\varepsilon\)
S verschwindet: \(L(G)=\{a^nb^n\mid n\ge 0\}\) — nach 9.2.2 erkennt diese Sprache kein DEA.
Ableitungsbaum für aabb
S a S b a S b ε
Merke

Kontextfreie Grammatik: Links steht genau ein Nichtterminal, rechts ein beliebiges Wort. \(S\to aSb\mid\varepsilon\) erzeugt \(\{a^nb^n\mid n\ge 0\}\) — erkannt von einem Kellerautomaten, nicht von einem DEA.

2

Grammatik und Kellerautomat

Die Regel S → aSb verspricht beim Erzeugen jedes a ein späteres b. Ein Kellerautomat hält solche offenen Versprechen im Keller fest.

  • Keller = offene Versprechen:jedes Zeichen, das später noch „bezahlt“ werden muss, liegt als Kellersymbol bereit; das zuletzt eingegangene liegt oben.
  • Gleiche Sprachen:zu jeder kontextfreien Grammatik gibt es einen Kellerautomaten und umgekehrt (im Allgemeinen nichtdeterministisch) — sie beschreiben die kontextfreien Sprachen.
  • Hierarchie:regulär (DEA, reguläre Grammatik) \(\subset\) kontextfrei (Kellerautomat, kontextfreie Grammatik); \(\{a^nb^nc^n\}\) ist nicht einmal kontextfrei.
  • Anwendung:die Syntax von Programmiersprachen — Klammern, Ausdrücke, verschachtelte Blöcke — wird mit kontextfreien Grammatiken festgelegt und von Parsern geprüft.

Ziehe den Lesekopf über das Eingabeband (oder Pfeiltasten). Oben steht die passende Satzform der Linksableitung, rechts der Keller des Kellerautomaten nach genau so vielen Zeichen — vergleiche die orangefarbenen Zeichen der Satzform mit dem Kellerinhalt.

Ableitung und Keller im Gleichschritt

Halte fest: Was in der Satzform rechts vom Nichtterminal noch aussteht, steht im Keller — ein Kellersymbol für jede offene Verpflichtung, das zuletzt eingegangene oben. Genau dieses Gedächtnis fehlt einem DEA.

3

Allgemeine Hinweise

Ein Nichtterminal reicht nicht

\(S\to aSb\) enthält nur ein Nichtterminal und ist trotzdem nicht regulär. Entscheidend ist, wo es steht — nicht, wie viele es gibt.

Regeln als Bauplan lesen

Lies S als „ein korrektes Stück“: \(S\to(S)S\) heißt „ein geklammertes korrektes Stück, dahinter noch eines“. So lassen sich Grammatiken rekursiv entwerfen.

Mehrdeutige Grammatiken

Mit \(S\to SS\mid(S)\mid\varepsilon\) hat ()()() mehrere Ableitungsbäume. Die Sprache ist dieselbe, aber ein Parser kann sich nicht eindeutig entscheiden.

Videos