Reguläre Grammatik: Unterschied zwischen den Versionen

Aus SibiWiki
Zur Navigation springen Zur Suche springen
 
(9 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 6: Zeile 6:
=Fachbegriffe=
=Fachbegriffe=
Nicht-terminal-symbole, Terminal-Symbole, Startsymbol, Produktionsregeln, Ableitung (eines Wortes), Sprache
Nicht-terminal-symbole, Terminal-Symbole, Startsymbol, Produktionsregeln, Ableitung (eines Wortes), Sprache
=Definition=
 
=Erklärvideos=
* [https://youtu.be/BcMXVx6VeSk Deterministischen endlichen Automaten in reguläre Grammatik umwandeln]
 
=Definition Grammatik=


Eine '''Grammatik''' G wird durch ein 4-Tupel (N, T, S, P) definiert:
Eine '''Grammatik''' G wird durch ein 4-Tupel (N, T, S, P) definiert:
Zeile 13: Zeile 17:
* S ∈ N ist das '''Startsymbol'''.
* S ∈ N ist das '''Startsymbol'''.
* P ist die Menge der '''Produktionsregeln'''.
* P ist die Menge der '''Produktionsregeln'''.
=Reguläre Grammatik=
Reguläre Grammatiken sind entweder '''rechtslinear''' oder '''linkslinear'''.


Eine '''reguläre''' Grammatik ist eine Grammatik, bei denen <u>alle</u> Produktionen eine der folgenden Formen haben:
"Üblich" sind rechtslineare Grammatiken, weil sie sich aus DEAs und NEAs direkt herstellen lassen.
* A &rarr; aB &nbsp;&nbsp;&nbsp;&nbsp;  ''d.h. Nichtterminalsymbol wird ersetzt durch ein Terminalsymbol gefolgt von einem Nichtterminalsymbol'''
 
Linkslineare Grammatiken sind '''äquivalent''' zu rechtslinearen Grammatiken, d.h.:
* für jede linkslineare Grammatik gibt es eine rechtslineare Grammatik, die die gleiche Sprache erzeugt.
* für jede rechtslineare Grammatik gibt es eine linkslineare Grammatik, die die gleiche Sprache erzeugt.
 
==rechtslineare Grammatik==
 
Eine '''rechtslineare''' Grammatik ist eine Grammatik, bei der <u>alle</u> Produktionen eine der folgenden Formen haben:
* '''A &rarr; aB''' &nbsp;&nbsp;&nbsp;&nbsp;  ''d.h. Nichtterminalsymbol wird ersetzt durch ein Terminalsymbol gefolgt von einem Nichtterminalsymbol''. '''Das Nicht-Terminal steht <u>rechts</u>.'''
* A &rarr; a &nbsp;&nbsp;&nbsp;&nbsp;  ''d.h. Nichtterminalsymbol wird ersetzt durch ein Terminalsymbol.''
* A &rarr; a &nbsp;&nbsp;&nbsp;&nbsp;  ''d.h. Nichtterminalsymbol wird ersetzt durch ein Terminalsymbol.''
* A &rarr; &epsilon; &nbsp;&nbsp;&nbsp;&nbsp;  ''d.h. Nichtterminalsymbol wird ersetzt durch nichts. (&epsilon; steht für nichts.)''
* A &rarr; &epsilon; &nbsp;&nbsp;&nbsp;&nbsp;  ''d.h. Nichtterminalsymbol wird ersetzt durch nichts. (&epsilon; steht für nichts.)''
=linkslineare Grammatiken=
in '''linkslinearen''' Grammatiken haben alle Regeln die Form:
* '''A &rarr; Ba''' &nbsp;&nbsp;&nbsp;&nbsp;  ''d.h. Nichtterminalsymbol wird ersetzt durch ein Nichtterminalsymbol gefolgt von einem Terminalsymbol''. '''Das Nicht-Terminal steht <u>links</u>.'''
* A &rarr; a &nbsp;&nbsp;&nbsp;&nbsp;  ''d.h. Nichtterminalsymbol wird ersetzt durch ein Terminalsymbol.''
* A &rarr; &epsilon; &nbsp;&nbsp;&nbsp;&nbsp;  ''d.h. Nichtterminalsymbol wird ersetzt durch nichts. (&epsilon; steht für nichts.)''
Das heißt: Der Unterschied zwischen regulären und linkslinearen Grammatiken besteht darin, dass bei den linkslinearen Grammatiken immer erst das Nichtterminalsymbol und dann das Terminalsymbol kommt.


=Beispiele=
=Beispiele=
Zeile 25: Zeile 47:
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.  


Die Grammatik G der KGB-Sprache kann wie folgt definiert werden:
Eine rechtslineare Grammatik G der KGB-Sprache kann wie folgt definiert werden:


* G= (N, T, S, P)
* G= (N, T, S, P)
Zeile 42: Zeile 64:
* S &rarr; 0S &rarr; 06S &rarr; 060A &rarr; 0600B &rarr; 06007C &rarr; 060074C &rarr; 060074
* S &rarr; 0S &rarr; 06S &rarr; 060A &rarr; 0600B &rarr; 06007C &rarr; 060074C &rarr; 060074
Bei der letzten Ableitung wurde das C durch nichts (&epsilon;) ersetzt.
Bei der letzten Ableitung wurde das C durch nichts (&epsilon;) ersetzt.
===... und der Nachweis, dass sich ein Wort NICHT ableiten lässt===
Das kann viel schwieriger sein!
Man muss nämlich <u>alle</u> Möglichkeiten durchprobieren und zeigen, dass <u>keine</u> zum Ziel führt!
'''Nachweis, dass das Wort "0003" nicht zur KGB-Sprache gehört:'''
* S &rarr; 0S &rarr; 00S &rarr; 000S &rarr; 0003S : Das Wort ist verbraucht, aber das Nicht-Terminal S ist nicht ersetzt.
* S &rarr; 0S &rarr; 00S &rarr; 000A : Hier kann man mit dem Terminal 3 keine Ersetzungsregel anwenden.
* S &rarr; 0S &rarr; 00A &rarr; 000B : Hier kann man mit dem Terminal 3 keine Ersetzungsregel anwenden.
* S &rarr; 0A &rarr; 00B : Hier kann man mit dem Terminal 0 keine Ersetzungsregel anwenden.


==Beispiel für eine nicht-reguläre Grammatik==
==Beispiel für eine nicht-reguläre Grammatik==
Zeile 64: Zeile 102:


=Beziehung zu deterministischen endlichen Automaten=
=Beziehung zu deterministischen endlichen Automaten=
[[Datei:DEA-RG-NEA-reg-Sprache.png|400px|thumb|right|Beziehungen: Reguläre Grammatik - DEA - NEA - reguläre Sprache]]
* '''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 69: Zeile 108:
* '''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).
** Erklärvideo dazu: [https://youtu.be/BcMXVx6VeSk Deterministischen endlichen Automaten in reguläre Grammatik umwandeln]


=Beziehung zu regulären Sprachen=
=Beziehung zu regulären Sprachen=
Zeile 76: Zeile 116:
* '''Zu jeder regulären Sprache gibt es eine reguläre Grammatik.'''
* '''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.''
** ''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.''
=Beziehung zu linkslinearen Grammatiken=
in '''linkslinearen''' Grammatiken haben alle Regeln die Form:
* '''A &rarr; Ba''' &nbsp;&nbsp;&nbsp;&nbsp;  ''d.h. Nichtterminalsymbol wird ersetzt durch ein Nichtterminalsymbol gefolgt von einem Terminalsymbol''
* A &rarr; a &nbsp;&nbsp;&nbsp;&nbsp;  ''d.h. Nichtterminalsymbol wird ersetzt durch ein Terminalsymbol.''
* A &rarr; &epsilon; &nbsp;&nbsp;&nbsp;&nbsp;  ''d.h. Nichtterminalsymbol wird ersetzt durch nichts. (&epsilon; steht für nichts.)''
Das heißt: Der Unterschied zwischen regulären und linkslinearen Grammatiken besteht darin, dass bei den linkslinearen Grammatiken immer erst das Nichtterminalsymbol und dann das Terminalsymbol kommt.
Linkslineare Grammatiken sind '''äquivalent''' zu regulären Grammatiken, d.h.:
* für jede linkslineare Grammatik gibt es eine reguläre Grammatik, die die gleiche Sprache erzeugt.
* für jede reguläre Grammatik gibt es eine linkslineare Grammatik, die die gleiche Sprache erzeugt.


=Grenzen der regulären Grammatik=
=Grenzen der regulären Grammatik=

Aktuelle Version vom 30. August 2023, 13:44 Uhr


Fachbegriffe

Nicht-terminal-symbole, Terminal-Symbole, Startsymbol, Produktionsregeln, Ableitung (eines Wortes), Sprache

Erklärvideos

Definition Grammatik

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

Reguläre Grammatiken sind entweder rechtslinear oder linkslinear.

"Üblich" sind rechtslineare Grammatiken, weil sie sich aus DEAs und NEAs direkt herstellen lassen.

Linkslineare Grammatiken sind äquivalent zu rechtslinearen Grammatiken, d.h.:

  • für jede linkslineare Grammatik gibt es eine rechtslineare Grammatik, die die gleiche Sprache erzeugt.
  • für jede rechtslineare Grammatik gibt es eine linkslineare Grammatik, die die gleiche Sprache erzeugt.

rechtslineare Grammatik

Eine rechtslineare Grammatik ist eine Grammatik, bei der alle Produktionen eine der folgenden Formen haben:

  • A → aB      d.h. Nichtterminalsymbol wird ersetzt durch ein Terminalsymbol gefolgt von einem Nichtterminalsymbol. Das Nicht-Terminal steht rechts.
  • A → a      d.h. Nichtterminalsymbol wird ersetzt durch ein Terminalsymbol.
  • A → ε      d.h. Nichtterminalsymbol wird ersetzt durch nichts. (ε steht für nichts.)

linkslineare Grammatiken

in linkslinearen Grammatiken haben alle Regeln die Form:

  • A → Ba      d.h. Nichtterminalsymbol wird ersetzt durch ein Nichtterminalsymbol gefolgt von einem Terminalsymbol. Das Nicht-Terminal steht links.
  • A → a      d.h. Nichtterminalsymbol wird ersetzt durch ein Terminalsymbol.
  • A → ε      d.h. Nichtterminalsymbol wird ersetzt durch nichts. (ε steht für nichts.)

Das heißt: Der Unterschied zwischen regulären und linkslinearen Grammatiken besteht darin, dass bei den linkslinearen Grammatiken immer erst das Nichtterminalsymbol und dann das Terminalsymbol kommt.

Beispiele

KGB-Sprache

Die KGB-Sprache besteht aus allen Ziffernfolgen, die irgendwo die Zahlenkette "007" enhalten.

Eine rechtslineare 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 → 060074C → 060074

Bei der letzten Ableitung wurde das C durch nichts (ε) ersetzt.

... und der Nachweis, dass sich ein Wort NICHT ableiten lässt

Das kann viel schwieriger sein!

Man muss nämlich alle Möglichkeiten durchprobieren und zeigen, dass keine zum Ziel führt!

Nachweis, dass das Wort "0003" nicht zur KGB-Sprache gehört:

  • S → 0S → 00S → 000S → 0003S : Das Wort ist verbraucht, aber das Nicht-Terminal S ist nicht ersetzt.
  • S → 0S → 00S → 000A : Hier kann man mit dem Terminal 3 keine Ersetzungsregel anwenden.
  • S → 0S → 00A → 000B : Hier kann man mit dem Terminal 3 keine Ersetzungsregel anwenden.
  • S → 0A → 00B : Hier kann man mit dem Terminal 0 keine Ersetzungsregel anwenden.

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!
Z.B. die Grammatik mit der Produktionsregel
S → aSb | ε
lässt sich nicht in einen reguläre Grammatik überführen.
Siehe Beispiel für eine kontextfreie Grammatik

Beziehung zu deterministischen endlichen Automaten

Beziehungen: Reguläre Grammatik - DEA - NEA - reguläre Sprache

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.

Grenzen der regulären Grammatik

Für alle Sprachen, für die es keinen deterministischen endlichen Automaten gibt, gibt es auch keine reguläre Grammatik!

Begründung:

Wenn es für eine Sprache eine reguläre Grammatik gibt, dann kann man sie in einen deterministischen endlichen Automaten überführen.

D.h. umgekehrt:
Wenn es zu einer Sprache keinen deterministischen endlichen Automaten gibt, dann kann es zu der Sprache auch keine reguläre Grammatik geben. (Denn die ließe sich in einen deterministischen endlichen Automaten überführen.)

Beispiel

Für die Sprache L = {anbn} gibt es keinen deterministischen endlichen Automaten:
Siehe Beispiel für Grenzen des deterministischen endlichen Automaten.

Deswegen gibt es für diese Sprache auch keine reguläre Grammatik.