Reguläre Grammatik

Definition

Eine Grammatik G wird durch ein 4-Tupel (N, T, S, P) definiert:

• N ist die Menge der Nichtterminalsymbole.
• T ist die Menge der Terminalsymbole.
• S ∈ N ist das Startsymbol.
• P ist die Menge der Produktionsregeln.

reguläre Grammatik: Grammatiken, bei denen alle Produktionen die folgenden Formen haben, sind regulär:

• A → aB      d.h. A wird ersetzt durch ein Terminalsymbol gefolgt von einem Nichtterminalsymbol'
• A → a      d.h. A wird ersetzt durch ein Terminalsymbol.
• A → ε      d.h. A wird ersetzt durch nichts. (ε steht für nichts.)

Beispiel

Die KGB-Sprache:

Die KGB-Sprache besteht aus allen Ziffernfolgen, die irgendwo die Zahlenkette "007" enhalten.

Die Grammatik G der KGB-Sprache kann wie folgt definiert werden:

• G= (N, T, S, P)
• Nichtterminalsymbole N = {S, A, B, C}
• Terminalsymbole T = {0,...,9}
• Startsymbol S = S
• Produktionsregeln P = {
  • S → 0A | 0S | 1S | 2S | ... | 9S
  • A → 0B
  • B → 7C
  • C → ε | 0C | ... | 9C
• }

Beispiel für die Ableitung eines Wortes

Dass das Wort "060074" zu der KGB-Sprache gehört, lässt sich durch folgende Ableitung zeigen:

• S → 0S → 06S → 060A → 0600B → 06007C → 06007

Bei der letzten Ableitung wurde das C durch nichts (ε) ersetzt.

Beziehung zu deterministischen endlichen Automaten

• Zu jeder regulären Grammatik gibt es einen deterministischen endlichen Automaten.
  
  • Dazu erstellt man aus der regulären Grammatik erst einen Nicht-deterministischen endlichen Automaten, indem man aus jedem Nichtterminalsymbol einen Zustand macht und aus jeder Produktionsregel einen Übergang.
  • Aus dem Nicht-deterministischen endlichen Automaten kann man einen deterministischen endlichen Automaten erstellen. Das ist mühsam, aber es ist bewiesen, dass das immer geht!
• Zu jedem deterministischen endlichen Automaten gibt es eine reguläre Grammatik.
  Diese lässt sich leicht aus dem Übergangsgraphen konstruieren.