Reguläre Grammatik

Aus SibiWiki
Zur Navigation springen Zur Suche springen

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.
  • Zu jedem deterministischen endlichen Automaten gibt es eine reguläre Grammatik.
    • Diese lässt sich leicht aus dem Übergangsgraphen konstruieren, indem man aus jedem Zustand ein Nichtterminalsymbol macht und aus jedem Übergang eine Regel (mit einem Terminalsymbol und einem Nichtterminalsymbol).