Reguläre Grammatik: Unterschied zwischen den Versionen
Zur Navigation springen
Zur Suche springen
| Zeile 34: | Zeile 34: | ||
Bei der letzten Ableitung wurde das C durch nichts (ε) ersetzt. | Bei der letzten Ableitung wurde das C durch nichts (ε) ersetzt. | ||
=Beziehung zu deterministischen endlichen Automaten= | |||
* '''Zu jeder [[reguläre Grammatik|regulären Grammatik]] gibt es einen deterministischen endlichen Automaten.'''<br> | * '''Zu jeder [[reguläre Grammatik|regulären Grammatik]] gibt es einen deterministischen endlichen Automaten.'''<br> | ||
** Dazu erstellt man aus der regulären Grammatik erst einen [[Nicht-deterministischer endlicher Automaten|Nicht-deterministischen endlichen Automaten]], indem man aus jedem Nichtterminalsymbol einen Zustand macht und aus jeder Produktionsregel einen Übergang. | ** Dazu erstellt man aus der regulären Grammatik erst einen [[Nicht-deterministischer endlicher Automaten|Nicht-deterministischen endlichen Automaten]], indem man aus jedem Nichtterminalsymbol einen Zustand macht und aus jeder Produktionsregel einen Übergang. | ||
| Zeile 40: | Zeile 40: | ||
* '''Zu jedem deterministischen endlichen Automaten gibt es eine [[reguläre Grammatik]].''' | * '''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). | ** 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). | ||
=Beziehung zu regulären Sprachen= | |||
Aus der Beziehung zu den deterministischen endlichen Automaten folgt direkt: | |||
* '''Jede reguläre Grammatik erzeugt eine reguläre Sprache.''' | |||
** ''Denn zu jeder regulären Grammatik gibt es einen deterministischen endlichen Automaten, und dieser erkennt eine reguläre Sprache.'' | |||
* '''Zu jeder regulären Sprache gibt es eine reguläre Grammatik.''' | |||
** ''reguläre Sprachen sind genau die Sprachen, die von deterministischen endlichen Automaten erkannt werden. Zu jedem deterministischen endlichen Automaten kann man eine reguläre Grammatik finden.'' | |||
Version vom 23. Februar 2015, 08:30 Uhr
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, indem man aus jedem Zustand ein Nichtterminalsymbol macht und aus jedem Übergang eine Regel (mit einem Terminalsymbol und einem Nichtterminalsymbol).
Beziehung zu regulären Sprachen
Aus der Beziehung zu den deterministischen endlichen Automaten folgt direkt:
- Jede reguläre Grammatik erzeugt eine reguläre Sprache.
- Denn zu jeder regulären Grammatik gibt es einen deterministischen endlichen Automaten, und dieser erkennt eine reguläre Sprache.
- Zu jeder regulären Sprache gibt es eine reguläre Grammatik.
- reguläre Sprachen sind genau die Sprachen, die von deterministischen endlichen Automaten erkannt werden. Zu jedem deterministischen endlichen Automaten kann man eine reguläre Grammatik finden.