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.