Theoretische Informatik

Konstruktion einer rechtslinearen Grammatik

aus einem nichtdeterministischen endlichen Automaten

 aufwärts

Gegeben ist ein nicht­deterministischer endlicher Automat N. Es stellt sich die Frage, ob es eine Grammatik G gibt mit L(G) = L(N). Gesucht ist also eine Grammatik, die genau die Sprache erzeugt, die der Automat N erkennt. Wir formen dazu den gegebenen nicht­deterministischen Automaten N in geeigneter Weise in eine Grammatik um. Dabei zeigt es sich, dass sogar ein ganz bestimmter Typ von Grammatik hierfür ausreichend ist. Ferner zeigt sich, dass "Erkennen" und "Erzeugen" im Prinzip das gleiche ist, nur in entgegen­gesetzter Richtung.

Verfahren

Gegeben sei ein nicht­deterministischer endlicher Automat

N  =  (Z, A, d, q, F)

mit Zustands­menge Z, Eingabe­alphabet A, Übergangs­relation d, Startzustand q und Menge von Endzuständen F.

Aus dem Automaten N wird in folgender Weise eine Grammatik

G = (V, T, P, S)

mit Variablen­menge V, Terminal­zeichenmenge T, Produktionen­menge P und Startsymbol S konstruiert.

Konstruktion der Grammatik
  1. Die Menge der Variablen V der Grammatik ist gleich der Menge der Zustände Z des Automaten:

    V  =  Z

  2. Das Startsymbol S der Grammatik ist gleich dem Startzustand q des Automaten:

    S  =  q

  3. Die Menge der Terminal­zeichen T der Grammatik ist gleich dem Eingabe­alphabet A des Automaten:

    T  =  A

  4. Die Menge der Produktionen P der Grammatik entsteht aus der Übergangs­relation d des Automaten wie folgt:
    1. Für alle a Element A und r, s Element Z gilt

      (r, a, sElement d   genau dann wenn   r Pfeil nach rechts as  Element  P

    2. Für alle r Element Z gilt

      r Element F   genau dann wenn   r Pfeil nach rechts ε  Element  P

    Aus jedem Element (r, a, s) der Übergangs­relation wird also eine Produktion r Pfeil nach rechts as gemacht. Zusätzlich wird für jeden Endzustand r Element F noch eine Produktion r Pfeil nach rechts ε erzeugt.

Jedem Wort, das der Automat erkennt, entspricht ein Pfad durch den Zustands­graphen des Automaten vom Startzustand zu einem Endzustand. Diesem Pfad entspricht eine Ableitungs­folge vom Startsymbol der Grammatik zu diesem Wort. Umgekehrt entspricht jeder Ableitungs­folge vom Startsymbol der Grammatik zu einem Terminalwort ein Pfad durch den Zustands­graphen des Automaten vom Startzustand zu einem Endzustand.

Beispiel:  Der in folgendem Bild 1 dargestellte nicht­deterministische endliche Automat N erkennt die Sprache

L  =  { alle Wörter über A = {a, b}, die mit a anfangen und mit a aufhören }

Die aus dem Automaten N konstruierte Grammatik G = (V, T, P, S) hat die Variablen V = {S, X, Y}, die Terminal­zeichen T = {a, b}, die Produktionen

Sgeht über nachaX  |  aY
Xgeht über nachaX  |  bX  |  aY
Ygeht über nachε

und das Startsymbol S. Die Grammatik erzeugt die Sprache L.

 

Dem Wort abba entspricht der Pfad von S über X nach Y im Automaten. Diesem Pfad entspricht die Ableitungs­folge

Pfeil nach rechts aX Pfeil nach rechts abX Pfeil nach rechts abbX Pfeil nach rechts abbaY Pfeil nach rechts abba

in der Grammatik.

Bild 1: Nichtdeterministischer endlicher Automat, der die Sprache L erkennt
Bild 1: Nichtdeterministischer endlicher Automat, der die Sprache L erkennt

Rechtslineare Grammatik

Die Grammatik, die durch die angegebene Konstruktion entsteht, ist eine rechts­lineare Grammatik.

Definition:  Eine Grammatik G = (V, T, P, S) heißt rechtslinear, wenn jede Produktion von der Form

Xgeht über nachaY    oder
Xgeht über nacha    oder
Xgeht über nachε

mit X, Y Element V und a Element T ist.

 

Eine rechts­lineare Grammatik ist nichts anderes als eine Typ-3-Grammatik der Chomsky-Hierarchie.

Satz:  Jede reguläre Sprache ist eine Typ-3-Sprache.

Beweis:  Wenn eine Sprache L regulär ist, dann gibt es einen nicht­deterministischen endlichen Automaten N, der sie erkennt, d.h. L(N) = L. Aus diesem Automaten kann nach dem oben angegebenen Verfahren eine Typ-3-Grammatik G konstruiert werden mit L(G) = L(N) = L.

Aufgaben

Aufgabe 1:  Gegeben sei folgender nicht­deterministische Automat N (Bild 2). Konstruieren Sie nach dem angegebenen Verfahren eine rechts­lineare Grammatik G mit L(G) = L(N).

Bild 2: Nichtdeterministischer endlicher Automat N
Bild 2: Nichtdeterministischer endlicher Automat N

Aufgabe 2:  Beweisen Sie das Pumping Lemma mithilfe des Begriffs der rechts­linearen Grammatik.

Aufgabe 3:  Geben Sie das umgekehrte Verfahren an, das zu einer rechts­linearen Grammatik G einen nicht­deterministischen endlichen Automaten N, ggf. mit Epsilon-Übergängen, konstruiert, derart dass L(G) = L(N) gilt.

 

Weiter mit:  [Kontextfreie Grammatik]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 26.01.2003   Updated: 13.05.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik