MINT lernen

Reguläre Grammatiken entwerfen

Drei Regelformen genügen für jede Sprache, die ein DEA erkennt — aber wie findet man die richtigen Regeln?

1

Regeln in fester Form

Eine Grammatik ist regulär, wenn jede Regel höchstens ein Zeichen erzeugt und die weitere Arbeit an genau ein Nichtterminal abgibt.

  • Reguläre Grammatik:jede Produktionsregel hat eine der Formen \(A\to aB\), \(A\to a\) oder \(A\to\varepsilon\) mit \(A,B\in N\) und \(a\in T\).
  • Satzform:enthält höchstens ein Nichtterminal — immer ganz rechts, z. B. aabA.
  • Ein Zeichen je Schritt:\(A\to aB\) hängt \(a\) an und übergibt an \(B\).
  • Abschluss:\(A\to a\) oder \(A\to\varepsilon\) beendet die Ableitung.
  • Nicht regulär:\(S\to aSb\) (Nichtterminal in der Mitte), \(S\to AB\) (zwei Nichtterminale), \(S\to Ab\) (Nichtterminal links).

Baue zu jeder Zielsprache eine reguläre Grammatik: Wähle linke Seite, Zeichen und das Nichtterminal, mit dem es weitergeht, und füge die Regel hinzu. Das Wortraster färbt sich sofort — tippe ein Wort an (oder Pfeiltasten + Enter), um seine Ableitung zu sehen.

Grammatik-Baukasten

Halte fest: Jedes Nichtterminal steht für eine Information über das bisher erzeugte Wort — etwa „schon ein b erzeugt“. Regeln mit \(\varepsilon\) gehören genau zu den Nichtterminalen, bei denen das Wort fertig sein darf.

2

Eine Grammatik entwerfen

Beim Entwurf fragt man wie beim DEA: Was muss man über das bisher erzeugte Anfangsstück wissen? Jede Antwort wird ein Nichtterminal.

  • 1 · Bedeutungen:jede nötige Information wird ein Nichtterminal; das Startsymbol \(S\) heißt „noch nichts erzeugt“.
  • 2 · Regeln:für jedes Nichtterminal \(A\) und jedes Zeichen \(a\): \(A\to aB\), wenn danach die Information \(B\) gilt.
  • 3 · Ende:\(A\to\varepsilon\), wenn das Wort in Situation \(A\) fertig sein darf.
  • 4 · Testen:Ableitungen zu Wörtern der Sprache und zu Gegenbeispielen — auch \(\varepsilon\) und die kürzesten Wörter.

Beispiel: Wörter über {a, b}, die mit ab beginnen. S bedeutet „noch nichts erzeugt“, A „a erzeugt, b fehlt noch“, B „ab erzeugt, der Rest ist frei“.

N = {S, A, B}
T = {a, b}
Startsymbol: S
Produktionsregeln:
S → aA
A → bB
B → aB | bB | ε

Herleitung:

\(S\)
Start
Jede Ableitung beginnt beim Startsymbol.
\(a\textcolor{#7c5fb5}{A}\)
\(S\to aA\)
Das erste Zeichen muss ein a sein — S hat keine andere Regel.
\(ab\textcolor{#7c5fb5}{B}\)
\(A\to bB\)
Jetzt ist der Anfang ab komplett; das Nichtterminal wandert nach rechts.
\(abb\textcolor{#7c5fb5}{B}\)
\(B\to bB\)
In B sind beide Zeichen erlaubt.
\(abba\textcolor{#7c5fb5}{B}\)
\(B\to aB\)
Die Satzform enthält weiterhin genau ein Nichtterminal, ganz rechts.
\(abba\)
\(B\to\varepsilon\)
B darf verschwinden: \(abba\in L(G)\). Für ba gibt es dagegen keine Ableitung — S erzeugt nur a.
Merke

Reguläre Grammatik: Alle Regeln haben die Form \(A\to aB\), \(A\to a\) oder \(A\to\varepsilon\). Jedes Nichtterminal steht für das, was über das bisher erzeugte Wort bekannt ist.

3

Allgemeine Hinweise

Nur rechts anhängen

Mischt man \(A\to aB\) mit Regeln wie \(A\to Ba\), wächst die Satzform an beiden Enden — die Grammatik ist dann nicht mehr regulär.

Lange Regeln zerlegen

\(S\to abA\) hat nicht die feste Form, beschreibt aber nichts Neues: \(S\to aX\) und \(X\to bA\) mit einem neuen Nichtterminal \(X\) leisten dasselbe.

An ε denken

Gehört das leere Wort zur Sprache, braucht das Startsymbol die Regel \(S\to\varepsilon\). Ohne sie fehlt \(\varepsilon\) — ohne Grund gesetzt, entsteht es zu viel.

Videos