Reguläre Grammatik: Unterschied zwischen den Versionen

Aus SibiWiki
Zur Navigation springen Zur Suche springen
Zeile 16: Zeile 16:
* A → ε       ''d.h. Terminalsymbol wird ersetzt durch nichts. (ε steht für nichts.)''
* A → ε       ''d.h. Terminalsymbol wird ersetzt durch nichts. (ε steht für nichts.)''


=Beispiel=
=Beispiele=
Die '''KGB-Sprache''':
 
==KGB-Sprache==


Die KGB-Sprache besteht aus allen Ziffernfolgen, die irgendwo die Zahlenkette "007" enhalten.  
Die KGB-Sprache besteht aus allen Ziffernfolgen, die irgendwo die Zahlenkette "007" enhalten.  
Zeile 34: Zeile 35:
* '''}'''
* '''}'''


==Beispiel für die Ableitung eines Wortes==
===Beispiel für die Ableitung eines Wortes===
Dass das Wort "060074" zu der KGB-Sprache gehört, lässt sich durch folgende Ableitung zeigen:
Dass das Wort "060074" zu der KGB-Sprache gehört, lässt sich durch folgende Ableitung zeigen:
* S → 0S → 06S → 060A → 0600B → 06007C → 06007
* S → 0S → 06S → 060A → 0600B → 06007C → 06007
Bei der letzten Ableitung wurde das C durch nichts (ε) ersetzt.
Bei der letzten Ableitung wurde das C durch nichts (ε) ersetzt.
==Beispiel für eine nicht-reguläre Grammatik==
Die folgende Grammatik für den KGB-Automaten ist <u>nicht</u> regulär:
* G= (N, T, S, P)
* '''Nichtterminalsymbole''' N = {S, A}
* '''Terminalsymbole''' T = {0,...,9}
* '''Startsymbol''' S = S
* '''Produktionsregeln P = {'''
** S &rarr; <u>007A</u> | 0S | 1S | 2S | ... | 9S
** A &rarr; &epsilon; | 0A | ... | 9A
* '''}'''
Die unterstrichene Regel verstößt gegen die Anforderungen, denn vor dem Nicht-Terminalsymbol sind drei Terminalsymbole!
''Hinweis:''
''Diese nicht-reguläre Grammatik lässt sich in eine reguläre Grammatik überführen.''
''Das gilt aber nicht für jede nicht-reguläre Grammatik!''


=Beziehung zu deterministischen endlichen Automaten=
=Beziehung zu deterministischen endlichen Automaten=

Version vom 19. August 2015, 20:43 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. Terminalsymbol wird ersetzt durch ein Terminalsymbol gefolgt von einem Nichtterminalsymbol'
  • A → a      d.h. Terminalsymbol wird ersetzt durch ein Terminalsymbol.
  • A → ε      d.h. Terminalsymbol wird ersetzt durch nichts. (ε steht für nichts.)

Beispiele

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.

Beispiel für eine nicht-reguläre Grammatik

Die folgende Grammatik für den KGB-Automaten ist nicht regulär:

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

Die unterstrichene Regel verstößt gegen die Anforderungen, denn vor dem Nicht-Terminalsymbol sind drei Terminalsymbole!

Hinweis:

Diese nicht-reguläre Grammatik lässt sich in eine reguläre Grammatik überführen.

Das gilt aber nicht für jede nicht-reguläre Grammatik!

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).

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.