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 | 1S | 2S | ... | 9S
  • A → 0B | 1S | 2S | ... | 9S
  • B → 0B | 7C | 1S | 2S | ... | 6S | 8S | 9S
  • C → ε | 0C | ... | 9C