www.wikidata.de-de.nina.az

Greibach Normalform Die ist ein Begriff der theoretischen Informatik der im Zusammenhang mit kontextfreien Sprachen von

Greibach-Normalform

Die Greibach-Normalform ist ein Begriff der theoretischen Informatik, der im Zusammenhang mit kontextfreien Sprachen von Interesse ist. Sie ist nach der US-Informatikerin Sheila A. Greibach benannt und beschreibt eine Normalform der kontextfreien Grammatiken. Jede kontextfreie Grammatik, nach der nicht das leere Wort abgeleitet werden kann, kann in eine Greibach-Normalform transformiert werden. Die herausragende Eigenschaft der Greibach-Normalform ist, dass bei jedem Ableitungsschritt jeweils genau ein Terminalzeichen entsteht. Damit ist sie der natürliche Zwischenschritt bei der Umformung einer kontextfreien Grammatik in einen äquivalenten nichtdeterministischen Kellerautomaten ohne -Übergänge.

Eine weitere Normalform für kontextfreie Grammatiken ist die Chomsky-Normalform.

Formale Definition Bearbeiten

Sei eine kontextfreie Grammatik (vgl. Chomsky-Hierarchie), also , mit . Dabei sei die Menge der Nichtterminalsymbole, die Menge der Terminalsymbole, die Menge von Produktionsregeln und das Startsymbol. Sei das leere Element .

ist in Greibach-Normalform (kurz GNF), wenn alle Produktionen aus die Form mit haben, wobei ein Terminalsymbol ist und und für Nichtterminale sind. Das Besondere an dieser Form ist also, dass auf der rechten Seite jeder Produktion genau ein Terminalsymbol gefolgt von beliebig vielen Nichtterminalen steht. Es ist aber insbesondere möglich, dass auf der rechten Seite der Produktion nur ein Terminalsymbol steht.

Mit erhält man eine reguläre Grammatik als Spezialfall einer kontextfreien Grammatik in Greibach-Normalform.

Für alle mit gibt es ein , mit , in Greibach-Normalform.

Ist allerdings , dann darf nie auf der rechten Seite einer Produktion vorkommen. Somit ist gewährleistet, dass auch Sprachen, die das leere Wort enthalten, von einer Grammatik in Greibach-Normalform erzeugt werden können.

Konstruktion der GNF Bearbeiten

Der folgende Algorithmus überführt eine Grammatik von der Chomsky-Normalform in die Greibach-Normalform. Der Algorithmus ist von theoretischer Bedeutung, da er zeigt, dass jede kontextfreie Grammatik, nach der nicht das leere Wort abgeleitet werden kann, in eine Greibach-Normalform transformiert werden kann. Die erzeugte Greibach-Normalform ist aber nicht minimal und es existieren Algorithmen mit besserer Laufzeit, die kleine Greibach-Normalformen berechnen.

Notation Bearbeiten

Hierbei sind im Folgenden:

  • Nichtterminale (hier repräsentiert bereits vorhandene und im Schema neu eingeführte Nichtterminalsymbole)
  • Terminale und
  • das Vokabular der Grammatik
  • Folgen von Nichtterminalen (z. B. )
  • Folgen von Terminalen und Nichtterminalen (z. B. )

Vorbereitung Bearbeiten

Zunächst bringt man die Grammatik in Chomsky-Normalform. Für das unten angegebene Schema braucht man eine beliebige totale Ordnung auf den Nichtterminalen. Dazu kann man die vorkommenden Nichtterminale in mit umbenennen. Hierzu geht man wie folgt vor:

  • Das erste vorkommende Nichtterminal wird in umbenannt.
  • Das zweite vorkommende Nichtterminal wird in umbenannt.
  • Dieses Schema wird fortgesetzt, bis man alle vorkommenden Nichtterminale ersetzt hat.

Beispiel:

  • Die erste vorkommende Variable ist , und wird deswegen in umbenannt.
  • Die zweite vorkommende Variable ist , und wird deswegen in umbenannt.
  • führt man diese Schema weiter, kommt man zu

Phase 1 Bearbeiten

In dieser Phase verwendet der Algorithmus die folgenden zwei Formen von Ersetzungen von Regeln. Nach diesem Schritt gilt für alle Regeln der Grammatik, dass .

Einsetzen der Produktionen Bearbeiten

Mit dieser Ersetzungsregel entfernt der Algorithmus alle Regeln der . Die Voraussetzung ist, dass es keine rekursiven Regeln für das Nichtterminal gibt. Die Regeln der Form werden dann ersetzt, indem das Nichtterminal durch seine Produktionen ersetzt werden. 

Regel1() für alle  für alle  Füge  hinzu ende Entferne  ende

Beispiel: mit wird zu .

Ersetzen von linksrekursiven Regeln Bearbeiten

Linksrekursive Regeln haben die Form , d. h. eine Variable kann wieder auf sich selbst ableiten. Durch wiederholtes Einsetzen sieht man leicht, dass durch linksrekursive Regeln genau der reguläre Ausdruck

erzeugt werden kann. Dies kann leicht anders erreicht werden:

Man ersetzt die Regeln für linksrekursive durch:

und fügt neue Regeln für ein: 

Regel2() für alle  Füge  hinzu ende für alle  Füge  hinzu Füge  hinzu Entferne  ende

Algorithmus Bearbeiten

Der Algorithmus wendet die obigen zwei Ersetzungsregeln für bis an, sodass zunächst immer Regeln der Form ersetzt werden und dann linksrekursive Regeln mit eliminiert werden. 

 für i:=1 bis m für j:=1 bis i-1 Regel1() ende Regel2() ende

Ab jetzt gibt es nur noch Regeln der Form oder der Form . Insbesondere gilt, dass alle Regeln auf der rechten Seite mit einem Terminalsymbol beginnen.

Phase 2 Bearbeiten

In diese Phase werden alle Regeln über die Nichtterminale in die Form transformiert. Der Algorithmus beginnt bei den Regeln und ersetzt Regeln, die mit einem Nichtterminal beginnen werden, indem die Produktionen des Nichtterminals eingesetzt werden. Hier wird ausgenutzt, dass wenn Regeln betrachtet werden, die Regeln für schon in der gewünschten Form sind. 

 für i:=m-1 bis 1 für j:=i+1 bis m Regel1() ende ende

Phase 3 Bearbeiten

Im letzten Schritt werden alle Regeln über die neuen Nichtterminale in die Greibach-Normalform transformiert. Regeln, die mit einem Nichtterminal beginnen, werden ersetzt, indem die Produktionen dieses Nichtterminals eingesetzt werden. 

 für alle  für alle  Füge  hinzu ende Entferne  ende

Hier wird ausgenutzt, dass die Regeln alle schon in Greibach-Normalform sind und die nie als erstes Symbol der rechten Seite einer Regel auftreten.

Eine strengere Variante der Greibach-Normalform Bearbeiten

Es ist auch möglich, die Produktionen einer kontextfreien Grammatik so in Greibach-Normalform umzuformen, dass auf jeder rechten Seite maximal 2 Variablen vorkommen. Die resultierenden Produktionen haben dann also die Form , oder .

Konstruktion eines Kellerautomaten aus der GNF Bearbeiten

Um aus einer Grammatik in GNF einen Kellerautomaten zu konstruieren, wähle die Zustandsmenge von als , das Kelleralphabet , das Bandalphabet , das Kellerstartsymbol und die Menge der Endzustände . Als Übergangsrelation wähle . akzeptiert über leeren Keller. Beweis per Induktion.

Literatur Bearbeiten

  • Uwe Schöning: Theoretische Informatik – kurz gefasst. 5. Auflage. Spektrum Akademischer Verlag, Heidelberg, ISBN 978-3-8274-1824-1, 1.3 Kontextfreie Sprachen.
  • Ingo Wegener: Theoretische Informatik. Eine algorithmenorientierte Einführung. B.G. Teubner, Stuttgart, ISBN 3-519-02123-4, 7.1 Die Greibach-Normalform für kontextfreie Grammatiken.

Einzelnachweise Bearbeiten

  1. Norbert Blum, Robert Koch: Greibach Normal Form Transformation Revisited. In: Information and Computation. 150. Jahrgang, Nr. 1, 1999, S. 112–118, doi:10.1006/inco.1998.2772.
  2. Beweis der Konstruktion des Kellerautomaten aus der GNF
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Die Greibach Normalform ist ein Begriff der theoretischen Informatik der im Zusammenhang mit kontextfreien Sprachen von Interesse ist Sie ist nach der US Informatikerin Sheila A Greibach benannt und beschreibt eine Normalform der kontextfreien Grammatiken Jede kontextfreie Grammatik nach der nicht das leere Wort abgeleitet werden kann kann in eine Greibach Normalform transformiert werden Die herausragende Eigenschaft der Greibach Normalform ist dass bei jedem Ableitungsschritt jeweils genau ein Terminalzeichen entsteht Damit ist sie der naturliche Zwischenschritt bei der Umformung einer kontextfreien Grammatik in einen aquivalenten nichtdeterministischen Kellerautomaten ohne e displaystyle varepsilon Ubergange Eine weitere Normalform fur kontextfreie Grammatiken ist die Chomsky Normalform Inhaltsverzeichnis 1 Formale Definition 2 Konstruktion der GNF 2 1 Notation 2 2 Vorbereitung 2 3 Phase 1 2 3 1 Einsetzen der Produktionen 2 3 2 Ersetzen von linksrekursiven Regeln 2 3 3 Algorithmus 2 4 Phase 2 2 5 Phase 3 3 Eine strengere Variante der Greibach Normalform 4 Konstruktion eines Kellerautomaten aus der GNF 5 Literatur 6 EinzelnachweiseFormale Definition BearbeitenSei G displaystyle G nbsp eine kontextfreie Grammatik vgl Chomsky Hierarchie also G Typ 2 displaystyle G in mbox Typ 2 nbsp mit G N S P S displaystyle G left N Sigma P S right nbsp Dabei sei N displaystyle N nbsp die Menge der Nichtterminalsymbole S displaystyle Sigma nbsp die Menge der Terminalsymbole P displaystyle P nbsp die Menge von Produktionsregeln und S displaystyle S nbsp das Startsymbol Sei das leere Element e L G displaystyle varepsilon notin L left G right nbsp G displaystyle G nbsp ist in Greibach Normalform kurz GNF wenn alle Produktionen aus P displaystyle P nbsp die Form A b B 1 B k displaystyle A rightarrow bB 1 ldots B k nbsp mit k 0 displaystyle k geq 0 nbsp haben wobei b displaystyle b nbsp ein Terminalsymbol ist und A displaystyle A nbsp und B i displaystyle B i nbsp fur i 1 k displaystyle i in 1 ldots k nbsp Nichtterminale sind Das Besondere an dieser Form ist also dass auf der rechten Seite jeder Produktion genau ein Terminalsymbol gefolgt von beliebig vielen Nichtterminalen steht Es ist aber insbesondere moglich dass auf der rechten Seite der Produktion nur ein Terminalsymbol steht Mit k 0 1 displaystyle k in 0 1 nbsp erhalt man eine regulare Grammatik als Spezialfall einer kontextfreien Grammatik in Greibach Normalform Fur alle G Typ 2 displaystyle G in mbox Typ 2 nbsp mit e L G displaystyle varepsilon notin L left G right nbsp gibt es ein G Typ 2 displaystyle G in mbox Typ 2 nbsp mit L G L G displaystyle L left G right L left G right nbsp in Greibach Normalform Ist allerdings S e P displaystyle left S varepsilon right in P nbsp dann darf S displaystyle S nbsp nie auf der rechten Seite einer Produktion vorkommen Somit ist gewahrleistet dass auch Sprachen die das leere Wort enthalten von einer Grammatik in Greibach Normalform erzeugt werden konnen Konstruktion der GNF BearbeitenDer folgende Algorithmus uberfuhrt eine Grammatik G N S P S displaystyle G left N Sigma P S right nbsp von der Chomsky Normalform in die Greibach Normalform Der Algorithmus ist von theoretischer Bedeutung da er zeigt dass jede kontextfreie Grammatik nach der nicht das leere Wort abgeleitet werden kann in eine Greibach Normalform transformiert werden kann Die erzeugte Greibach Normalform ist aber nicht minimal und es existieren Algorithmen mit besserer Laufzeit die kleine Greibach Normalformen berechnen 1 Notation Bearbeiten Hierbei sind im Folgenden A i B i N i N displaystyle A i B i in N i in mathbb N nbsp Nichtterminale hier reprasentiert A i displaystyle A i nbsp bereits vorhandene und B i displaystyle B i nbsp im Schema neu eingefuhrte Nichtterminalsymbole a S displaystyle a in Sigma nbsp Terminale und V S N displaystyle V Sigma cup N nbsp das Vokabular der Grammatik x y N displaystyle x y in N nbsp Folgen von Nichtterminalen z B x A 1 A 2 A 3 displaystyle x A 1 A 2 A 3 nbsp a b V displaystyle alpha beta in V nbsp Folgen von Terminalen und Nichtterminalen z B x a A 1 A 2 displaystyle x aA 1 A 2 nbsp Vorbereitung Bearbeiten Zunachst bringt man die Grammatik in Chomsky Normalform Fur das unten angegebene Schema braucht man eine beliebige totale Ordnung auf den Nichtterminalen Dazu kann man die vorkommenden Nichtterminale in A 1 A n displaystyle A 1 ldots A n nbsp mit n N displaystyle n N nbsp umbenennen Hierzu geht man wie folgt vor Das erste vorkommende Nichtterminal wird in A 1 displaystyle A 1 nbsp umbenannt Das zweite vorkommende Nichtterminal wird in A 2 displaystyle A 2 nbsp umbenannt Dieses Schema wird fortgesetzt bis man alle vorkommenden Nichtterminale ersetzt hat Beispiel P S A D E A a D G G b displaystyle P S rightarrow ADE A rightarrow aDG G rightarrow b nbsp Die erste vorkommende Variable ist S displaystyle S nbsp und wird deswegen in A 1 displaystyle A 1 nbsp umbenannt Die zweite vorkommende Variable ist A displaystyle A nbsp und wird deswegen in A 2 displaystyle A 2 nbsp umbenannt fuhrt man diese Schema weiter kommt man zu P A 1 A 2 A 3 A 4 A 2 a A 3 A 5 A 5 b displaystyle P A 1 rightarrow A 2 A 3 A 4 A 2 rightarrow aA 3 A 5 A 5 rightarrow b nbsp Phase 1 Bearbeiten In dieser Phase verwendet der Algorithmus die folgenden zwei Formen von Ersetzungen von Regeln Nach diesem Schritt gilt fur alle Regeln A i A j x displaystyle A i rightarrow A j x nbsp der Grammatik dass i lt j displaystyle i lt j nbsp Einsetzen der Produktionen Bearbeiten Mit dieser Ersetzungsregel entfernt der Algorithmus alle Regeln der A i A j x displaystyle A i rightarrow A j x nbsp Die Voraussetzung ist dass es keine rekursiven Regeln fur das Nichtterminal A j displaystyle A j nbsp gibt Die Regeln der Form A i A j x displaystyle A i rightarrow A j x nbsp werden dann ersetzt indem das Nichtterminal A j displaystyle A j nbsp durch seine Produktionen ersetzt werden Regel1 A i A j displaystyle A i A j nbsp fur alle A i A j x displaystyle A i rightarrow A j x nbsp fur alle A j b displaystyle A j rightarrow beta nbsp Fuge A i b x displaystyle A i rightarrow beta x nbsp hinzu ende Entferne A i A j x displaystyle A i rightarrow A j x nbsp ende Beispiel A 2 A 1 x displaystyle A 2 rightarrow A 1 x nbsp mit A 1 A 3 A 4 displaystyle A 1 rightarrow A 3 A 4 nbsp wird zu A 2 A 3 x A 4 x displaystyle A 2 rightarrow A 3 x A 4 x nbsp Ersetzen von linksrekursiven Regeln Bearbeiten Linksrekursive Regeln haben die Form A i A i x 1 A i x 2 A i x n b 1 b 2 b n displaystyle A i rightarrow A i x 1 A i x 2 ldots A i x n beta 1 beta 2 ldots beta n nbsp d h eine Variable kann wieder auf sich selbst ableiten Durch wiederholtes Einsetzen sieht man leicht dass durch linksrekursive Regeln genau der regulare Ausdruck b 1 b 2 b n x 1 x 2 x n displaystyle beta 1 beta 2 ldots beta n x 1 x 2 ldots x n nbsp erzeugt werden kann Dies kann leicht anders erreicht werden Man ersetzt die Regeln fur linksrekursive A i displaystyle A i nbsp durch A i b 1 b 2 b n b 1 B i b 2 B i b n B i displaystyle A i rightarrow beta 1 beta 2 ldots beta n beta 1 B i beta 2 B i ldots beta n B i nbsp und fugt neue Regeln fur B i displaystyle B i nbsp ein B i x 1 x 2 x n x 1 B i x 2 B i x n B i displaystyle B i rightarrow x 1 x 2 ldots x n x 1 B i x 2 B i ldots x n B i nbsp Regel2 A i displaystyle A i nbsp fur alle A i b displaystyle A i rightarrow beta nbsp Fuge A i b B i displaystyle A i rightarrow beta B i nbsp hinzu ende fur alle A i A i x displaystyle A i rightarrow A i x nbsp Fuge B i x displaystyle B i rightarrow x nbsp hinzu Fuge B i x B i displaystyle B i rightarrow x B i nbsp hinzu Entferne A i A i x displaystyle A i rightarrow A i x nbsp ende Algorithmus Bearbeiten Der Algorithmus wendet die obigen zwei Ersetzungsregeln fur A 1 displaystyle A 1 nbsp bis A m displaystyle A m nbsp an sodass zunachst immer Regeln der Form A i A j x i gt j displaystyle A i rightarrow A j x i gt j nbsp ersetzt werden und dann linksrekursive Regeln mit A i displaystyle A i nbsp eliminiert werden fur i 1 bis m fur j 1 bis i 1 Regel1 A i A j displaystyle A i A j nbsp ende Regel2 A i displaystyle A i nbsp ende Ab jetzt gibt es nur noch Regeln der Form A i A j x i lt j displaystyle A i rightarrow A j x i lt j nbsp oder der Form A i x displaystyle A i rightarrow x nbsp Insbesondere gilt dass alle A m displaystyle A m nbsp Regeln auf der rechten Seite mit einem Terminalsymbol beginnen Phase 2 Bearbeiten In diese Phase werden alle Regeln uber die Nichtterminale A i displaystyle A i nbsp in die Form A i a N displaystyle A i rightarrow a N nbsp transformiert Der Algorithmus beginnt bei den A m 1 displaystyle A m 1 nbsp Regeln und ersetzt Regeln die mit einem Nichtterminal beginnen werden indem die Produktionen des Nichtterminals eingesetzt werden Hier wird ausgenutzt dass wenn A i displaystyle A i nbsp Regeln betrachtet werden die A j displaystyle A j nbsp Regeln fur j gt i displaystyle j gt i nbsp schon in der gewunschten Form sind fur i m 1 bis 1 fur j i 1 bis m Regel1 A i A j displaystyle A i A j nbsp ende ende Phase 3 Bearbeiten Im letzten Schritt werden alle Regeln uber die neuen Nichtterminale B i displaystyle B i nbsp in die Greibach Normalform transformiert Regeln die mit einem Nichtterminal beginnen werden ersetzt indem die Produktionen dieses Nichtterminals eingesetzt werden fur alle B i A j x displaystyle B i rightarrow A j x nbsp fur alle A j b displaystyle A j rightarrow beta nbsp Fuge B i b x displaystyle B i rightarrow beta x nbsp hinzu ende Entferne B i A j x displaystyle B i rightarrow A j x nbsp ende Hier wird ausgenutzt dass die A j displaystyle A j nbsp Regeln alle schon in Greibach Normalform sind und die B i displaystyle B i nbsp nie als erstes Symbol der rechten Seite einer Regel auftreten Eine strengere Variante der Greibach Normalform BearbeitenEs ist auch moglich die Produktionen einer kontextfreien Grammatik so in Greibach Normalform umzuformen dass auf jeder rechten Seite maximal 2 Variablen vorkommen Die resultierenden Produktionen haben dann also die Form A i a displaystyle A i rightarrow a nbsp A i a V displaystyle A i rightarrow aV nbsp oder A i a V 1 V 2 displaystyle A i rightarrow aV 1 V 2 nbsp Konstruktion eines Kellerautomaten aus der GNF BearbeitenUm aus einer Grammatik G N T P S displaystyle G N T P S nbsp in GNF einen Kellerautomaten M Z S G d q 0 Z 0 F displaystyle M Z Sigma Gamma delta q 0 Z 0 F nbsp zu konstruieren wahle die Zustandsmenge von M displaystyle M nbsp als Z q 0 displaystyle Z q 0 nbsp das Kelleralphabet G N displaystyle Gamma N nbsp das Bandalphabet S T displaystyle Sigma T nbsp das Kellerstartsymbol Z 0 S displaystyle Z 0 S nbsp und die Menge der Endzustande F displaystyle F emptyset nbsp Als Ubergangsrelation wahle d q 0 a A q 0 x A a x P displaystyle delta q 0 a A q 0 x A rightarrow ax in P nbsp M displaystyle M nbsp akzeptiert uber leeren Keller Beweis per Induktion 2 Literatur BearbeitenUwe Schoning Theoretische Informatik kurz gefasst 5 Auflage Spektrum Akademischer Verlag Heidelberg ISBN 978 3 8274 1824 1 1 3 Kontextfreie Sprachen Ingo Wegener Theoretische Informatik Eine algorithmenorientierte Einfuhrung B G Teubner Stuttgart ISBN 3 519 02123 4 7 1 Die Greibach Normalform fur kontextfreie Grammatiken Einzelnachweise Bearbeiten Norbert Blum Robert Koch Greibach Normal Form Transformation Revisited In Information and Computation 150 Jahrgang Nr 1 1999 S 112 118 doi 10 1006 inco 1998 2772 Beweis der Konstruktion des Kellerautomaten aus der GNF Abgerufen von https de wikipedia org w index php title Greibach Normalform amp oldid 232068295