www.wikidata.de-de.nina.az

Formale Grammatik en sind mathematische Modelle von Grammatiken die zur eindeutigen Erzeugung und Beschreibung formaler

Formale Grammatik

Formale Grammatiken sind mathematische Modelle von Grammatiken, die zur eindeutigen Erzeugung und Beschreibung formaler Sprachen dienen. Sie werden in der theoretischen Informatik, insbesondere in der Berechenbarkeitstheorie, und im Compilerbau zum einen angewendet, um eindeutig festzulegen, ob ein Wort Element einer Sprache ist und zum anderen, um Eigenschaften dieser formalen Sprachen zu untersuchen bzw. zu beweisen. Formale Grammatiken werden mithilfe von Semi-Thue-Systemen angegeben in der Chomsky-Hierarchie klassifiziert.

Beschreibung Bearbeiten

Mit einer formalen Grammatik lassen sich ausgehend von einem Startsymbol (auch Startvariable genannt) Produktionsregeln aus einer Regelmenge anwenden, die aus dem Startsymbol neue Zeichenfolgen (Wörter) erzeugen, welche wiederum weiter ersetzt werden können. Diesen Vorgang nennt man auch Ableitung.

Das Vokabular einer Grammatik, bestehend aus der disjunkten Vereinigung eines Alphabets von Terminalsymbolen mit einer Menge von Nichtterminalsymbolen , gibt dabei vor, welche Symbole dafür verwendet werden können. Die Menge der Terminalsymbole definiert, aus welchen Zeichen Wörter bestehen, die nicht weiter abgeleitet werden können. Diese Wörter ergeben zusammengenommen die von der Grammatik beschriebene formale Sprache. Das Startsymbol muss dagegen ein Nichtterminalsymbol sein. Zusätzliche Nichtterminalsymbole erlauben differenziertere Regeln.

Produktionsregeln sind definitionsgemäß geordnete Paare , die auch geschrieben werden. Man wendet sie auf eine Zeichenfolge an, indem ein Vorkommen der Zeichenfolge in durch ersetzt wird. Auf der linken Seite der Regel muss immer mindestens ein Nichtterminalsymbol stehen. Eine Menge von Regeln mit gleicher linker Seite, also , wird abkürzend auch als geschrieben.

Zum Beispiel kann man mit der Regelmenge die Zeichenfolge entweder zu oder zu ableiten.

Ebenso wie auf eine gegebene Zeichenfolge mehrere Regeln gleichzeitig anwendbar sein können, muss es nicht immer nur eine Stelle in der Zeichenfolge geben, auf die eine Regel passt. Formale Grammatiken schreiben keine Reihenfolge vor. Alle nur aus Terminalsymbolen bestehenden Wörter, die sich aus dem Startsymbol ableiten lassen, zählen zur von der Grammatik beschriebenen Sprache.

Definition Bearbeiten

Eine formale Grammatik wird dargestellt durch das 4-Tupel , worin:

  • , einer endlichen Menge von Symbolen, welche als Symbolmenge oder Vokabular bezeichnet wird,
  • , einer Teilmenge von , auch Alphabet genannt und deren Elemente Terminalsymbole heißen,
  • , einer endlichen Menge von Produktionsregeln, sowie
  • , dem Startsymbol.

Das 4-Tupel wird je nach Konvention auch so definiert, dass der Menge der Nichtterminalsymbolen entspricht, sodass ist.

Hierbei bezeichnet die Kleenesche Hülle einer Menge von Zeichen (oder auch Wörtern).

Die Menge ist die Menge von Nichtterminalsymbolen (auch Nonterminale oder Metasymbole genannt), insbesondere gehört das Startzeichen zu ihr. Das Wort auf der linken Seite der Regelpaare darf nicht ausschließlich aus Terminalzeichen bestehen, was man auch durch eine Konkatenation ausdrücken kann:

Es ergibt wenig Sinn, wenn das Wort auf der rechten Seite das Startsymbol enthält. Manche Autoren berücksichtigen das, indem sie die zugehörige Menge entsprechend beschränken, d. h. durch ersetzen.

Manche Autoren bezeichnen alternativ das Quadrupel als Grammatik . Es finden sich darüber hinaus folgende abweichenden Bezeichnungen:

  • für die Terminalzeichen, hier ,
  • für das gesamte Vokabular (Symbolmenge) aller Symbole, hier ,
  • für die Nichtterminalzeichen (Variablen), hier ,
  • für das leere Wort, hier .

Die von einer Grammatik beschriebene Sprache Bearbeiten

Eine Regel einer gegebenen Grammatik besagt, dass in einem Wort mit R als Infix, R durch Q ersetzt werden kann, so dass ein neues Wort mit als Infix entsteht. Man spricht hierbei auch davon, dass in mit der Grammatik bzw. durch die Regel übergeht, oder auch, dass aus abgeleitet wurde. Dies kann durch notiert werden (häufig auch anstatt ). Soll nur ausgedrückt werden, dass in der Grammatik das Wort aus entstehen kann, ohne eine Regel zu benennen, schreibt man stattdessen (ist die Grammatik aus dem Kontext offensichtlich, auch einfach ). Demnach ist ein solcher Übergang von in eine Transitionsrelation, die eine natürliche Erweiterung von auf alle möglichen -Kontexte darstellt, nämlich:

wobei hier die Konkatenation von Wörtern bezeichnet.

Gibt es nun eine Folge von Wörtern , bei der gilt, dass für jede natürliche Zahl mit das Wort in übergeht (), so ist in Schritten aus ableitbar, was durch dargestellt wird. Eine solche Wortfolge wird Ableitung oder Rechnung von in der Länge genannt. Weiterhin heißt in ableitbar, wenn es mindestens ein gibt, so dass in Schritten aus ableitbar ist. Wenn in ableitbar ist, so wird dies durch die Schreibweise dargestellt. Dabei wird zusätzlich definiert, dass für jedes Wort gilt, dass ist, so dass die Relation die reflexiv-transitive Hülle der Relation ist.

Nun ist die von der Grammatik erzeugte formale Sprache diejenige Sprache, die aus allen Wörtern besteht, die zum einen nur aus Terminalsymbolen bestehen und die zum anderen vom Startsymbol mit einer endlichen Anzahl von Schritten abgeleitet werden können:

Dabei ist es egal, in welcher Reihenfolge die Produktionsregeln auf die abgeleiteten Wörter angewandt werden, oder ob es mehrere Möglichkeiten gibt, um ein Wort aus abzuleiten. Zwei Grammatiken und sind genau dann äquivalent, wenn die durch und erzeugten Sprachen gleich sind:

Wenn alle Terminalzeichen in den Wörten der formalen Sprachen vorkommen, dann müssen die Terminalzeichen übereinstimmen. Die Nichtterminalzeichen sind dagegen völlig frei.

Beispiele Bearbeiten

sei eine Grammatik mit den Terminalsymbolen , den Nichtterminalsymbolen , dem Startsymbol und mit den Regeln

Dabei ist das leere Wort, welches ein Wort der Länge 0 ist. Diese Grammatik definiert die Sprache aller Wörter der Form mit . So sind auf Grund der folgenden Ableitungen die Wörter , und Elemente der durch beschriebenen Sprache:

  • , mittels Regel (2),
  • , mittels der Regeln (1), (4) und (6),
  • , mittels der Regeln (1),(1),(4),(3), (5), (6) und (7).

Es gibt aber noch andere Möglichkeiten, um das Wort aus abzuleiten.

Eine weitere Grammatik, die dieselbe Sprache beschreibt, ist die kontextfreie Grammatik mit den Regeln:

Jede rekursiv aufzählbare Sprache wird von mehreren (und zwar abzählbar unendlich vielen) Grammatiken erzeugt. Allerdings gibt es auch Sprachen, die sich von keiner Grammatik erzeugen lassen.

Klassen von Grammatiken Bearbeiten

Grammatiken werden Klassen zugeordnet, die sich durch Gemeinsamkeiten auszeichnen. Die bekannteste Klassifikation beschrieben Noam Chomsky und Marcel Schützenberger mit der Chomsky-Hierarchie.

Chomsky-Hierarchie Bearbeiten

Die Chomsky-Hierarchie teilt die Grammatiken nach der Art der Produktionsregeln in Klassen vom Typ 0 bis Typ 3 ein:

  • Typ-0-Grammatiken: Phrasenstrukturgrammatiken sind uneingeschränkte formale Grammatiken.
  • Typ-1-Grammatiken: Kontextsensitive Grammatiken dürfen nur aus Regeln bestehen, in denen genau ein Nichtterminalsymbol durch eine Zeichenfolge ersetzt wird. Dieses Symbol darf auf der linken Seite der Regel auch von weiteren Symbolen umgeben sein, die einen Kontext angeben, innerhalb dessen die Ersetzung stattfinden muss.
  • Typ-2-Grammatiken: In kontextfreien Grammatiken darf dagegen auf den linken Seiten der Regeln jeweils nur genau ein Nichtterminalsymbol stehen. Das Symbol kann dann unabhängig vom Kontext ersetzt werden.
  • Typ-3-Grammatiken: Bei regulären Grammatiken enthalten die linken Seiten der Regeln ebenfalls nur genau ein Nichtterminalsymbol. Bei linksregulären Grammatiken darf die rechte Seite der Regel aus höchstens einem Nichtterminalsymbol bestehen, dem höchstens ein Terminalsymbol folgt (Bsp.: ). Bei rechtsregulären Grammatiken darf hingegen die rechte Seite aus höchstens einem Terminalsymbol bestehen, dem höchstens ein Nichtterminal folgt (Bsp.: ).

Die zugehörigen Sprachklassen sind abnehmend umfangreich. Es besteht folgende echte Inklusionsbeziehung:

Für die Sprachklassen von Typ mit gilt: .

Weitere Sprachklassen Bearbeiten

Von der Chomsky-Hierarchie abgesehen haben sich weitere Klassen an Grammatiken etabliert:

Siehe auch Bearbeiten

Literatur Bearbeiten

  • Katrin Erk, Lutz Priese: Theoretische Informatik. Eine umfassende Einführung. 2. erweiterte Auflage. Springer-Verlag, Berlin u. a. 2002, ISBN 3-540-42624-8, S. 53–61.

Weblinks Bearbeiten

Einzelnachweise Bearbeiten

  1. Peter Bachmann: Grundlagen der Theoretischen Informatik. Cottbus 2001, S. 47 (tu-cottbus.de [PDF; abgerufen am 12. Februar 2011] Vorlesungsskript).
  2. Christian Wagenknecht, Michael Hielscher: Formale Sprachen, Abstrakte Automaten und Compiler. Springer Vieweg, Wiesbaden 2014, S. 28, doi:10.1007/978-3-658-02692-9.
  3. Während die Bedeutung von und bzw. im gegebenen Fall jeweils klar ist, muss man sich bei (ebenso wie dem häufig benutzten ) durch Überprüfung des Kontexts klarmachen, was gemeint ist; wobei man sich auf das Grammatik-Quadrupels nicht verlassen kann.
  4. ↑ Klaus Reinhardt: (Memento des Originals vom 17. Januar 2018 im Internet Archive)  Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.@1@2Vorlage:Webachiv/IABot/users.informatik.uni-halle.de, Fakultät Informatik der Universität Stuttgart; Doktorarbeit 1994. Das Grammatik-Quadrupel ist hier wörtlich mit angegeben, damit ist in der hier gewählten Bezeichnungsweise gemeint.
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:
Formale Grammatiken sind mathematische Modelle von Grammatiken die zur eindeutigen Erzeugung und Beschreibung formaler Sprachen dienen Sie werden in der theoretischen Informatik insbesondere in der Berechenbarkeitstheorie und im Compilerbau zum einen angewendet um eindeutig festzulegen ob ein Wort Element einer Sprache ist und zum anderen um Eigenschaften dieser formalen Sprachen zu untersuchen bzw zu beweisen Formale Grammatiken werden mithilfe von Semi Thue Systemen angegeben in der Chomsky Hierarchie klassifiziert Inhaltsverzeichnis 1 Beschreibung 2 Definition 3 Die von einer Grammatik beschriebene Sprache 4 Beispiele 5 Klassen von Grammatiken 5 1 Chomsky Hierarchie 5 2 Weitere Sprachklassen 6 Siehe auch 7 Literatur 8 Weblinks 9 EinzelnachweiseBeschreibung BearbeitenMit einer formalen Grammatik lassen sich ausgehend von einem Startsymbol S displaystyle S nbsp auch Startvariable genannt Produktionsregeln aus einer Regelmenge P displaystyle P nbsp anwenden die aus dem Startsymbol neue Zeichenfolgen Worter erzeugen welche wiederum weiter ersetzt werden konnen Diesen Vorgang nennt man auch Ableitung Das Vokabular V displaystyle V nbsp einer Grammatik bestehend aus der disjunkten Vereinigung eines Alphabets T displaystyle T nbsp von Terminalsymbolen mit einer Menge von Nichtterminalsymbolen N displaystyle N nbsp gibt dabei vor welche Symbole dafur verwendet werden konnen Die Menge der Terminalsymbole definiert aus welchen Zeichen Worter bestehen die nicht weiter abgeleitet werden konnen Diese Worter ergeben zusammengenommen die von der Grammatik beschriebene formale Sprache Das Startsymbol muss dagegen ein Nichtterminalsymbol sein Zusatzliche Nichtterminalsymbole erlauben differenziertere Regeln Produktionsregeln sind definitionsgemass geordnete Paare a b displaystyle alpha beta nbsp die auch a b displaystyle alpha rightarrow beta nbsp geschrieben werden Man wendet sie auf eine Zeichenfolge w displaystyle w nbsp an indem ein Vorkommen der Zeichenfolge a displaystyle alpha nbsp in w displaystyle w nbsp durch b displaystyle beta nbsp ersetzt wird Auf der linken Seite der Regel muss immer mindestens ein Nichtterminalsymbol stehen Eine Menge von Regeln mit gleicher linker Seite also a b 1 a b n displaystyle alpha rightarrow beta 1 ldots alpha rightarrow beta n nbsp wird abkurzend auch als a b 1 b n displaystyle alpha rightarrow beta 1 ldots beta n nbsp geschrieben Zum Beispiel kann man mit der Regelmenge X displaystyle X rightarrow nbsp die Zeichenfolge 1 X 2 displaystyle 1X2 nbsp entweder zu 1 2 displaystyle 1 2 nbsp oder zu 1 2 displaystyle 1 2 nbsp ableiten Ebenso wie auf eine gegebene Zeichenfolge mehrere Regeln gleichzeitig anwendbar sein konnen muss es nicht immer nur eine Stelle in der Zeichenfolge geben auf die eine Regel passt Formale Grammatiken schreiben keine Reihenfolge vor Alle nur aus Terminalsymbolen bestehenden Worter die sich aus dem Startsymbol ableiten lassen zahlen zur von der Grammatik beschriebenen Sprache Definition BearbeitenEine formale Grammatik wird dargestellt durch das 4 Tupel G V T P S displaystyle G V T P S nbsp worin 1 V displaystyle V nbsp einer endlichen Menge von Symbolen welche als Symbolmenge oder Vokabular bezeichnet wird T V displaystyle T subset V nbsp einer Teilmenge von V displaystyle V nbsp auch Alphabet genannt und deren Elemente Terminalsymbole heissen P V T V displaystyle P subset left V setminus T right times V nbsp einer endlichen Menge von Produktionsregeln sowie S V T displaystyle S in V setminus T nbsp dem Startsymbol Das 4 Tupel wird je nach Konvention auch so definiert dass V displaystyle V nbsp der Menge der Nichtterminalsymbolen entspricht sodass V T displaystyle V cap T emptyset nbsp ist 2 Hierbei bezeichnet X displaystyle X nbsp die Kleenesche Hulle einer Menge X displaystyle X nbsp von Zeichen oder auch Wortern Die Menge N V T displaystyle N V setminus T nbsp ist die Menge von Nichtterminalsymbolen auch Nonterminale oder Metasymbole genannt insbesondere gehort das Startzeichen zu ihr Das Wort auf der linken Seite der Regelpaare darf nicht ausschliesslich aus Terminalzeichen bestehen was man auch durch eine Konkatenation ausdrucken kann V T V N V displaystyle left V setminus T right V NV nbsp Es ergibt wenig Sinn wenn das Wort auf der rechten Seite das Startsymbol enthalt Manche Autoren berucksichtigen das indem sie die zugehorige Menge entsprechend beschranken d h V displaystyle V nbsp durch V S displaystyle V setminus S nbsp ersetzen Manche Autoren bezeichnen alternativ das Quadrupel N T P S displaystyle N T P S nbsp als Grammatik G displaystyle G nbsp Es finden sich daruber hinaus folgende abweichenden Bezeichnungen 3 S displaystyle Sigma nbsp fur die Terminalzeichen hier T displaystyle T nbsp S displaystyle Sigma nbsp fur das gesamte Vokabular Symbolmenge aller Symbole hier V displaystyle V nbsp V displaystyle V nbsp fur die Nichtterminalzeichen Variablen hier N displaystyle N nbsp 4 l displaystyle lambda nbsp fur das leere Wort hier ϵ displaystyle epsilon nbsp 4 Die von einer Grammatik beschriebene Sprache BearbeitenEine Regel R Q P displaystyle R rightarrow Q in P nbsp einer gegebenen Grammatik G displaystyle G nbsp besagt dass in einem Wort w V displaystyle w in V ast nbsp mit R als Infix R durch Q ersetzt werden kann so dass ein neues Wort w displaystyle w prime nbsp mit Q displaystyle Q nbsp als Infix entsteht Man spricht hierbei auch davon dass w displaystyle w nbsp in w displaystyle w prime nbsp mit der Grammatik G displaystyle G nbsp bzw durch die Regel R Q displaystyle R rightarrow Q nbsp ubergeht oder auch dass w displaystyle w prime nbsp aus w displaystyle w nbsp abgeleitet wurde Dies kann durch w R Q w displaystyle w rightsquigarrow R rightarrow Q w prime nbsp notiert werden haufig auch displaystyle Rightarrow nbsp anstatt displaystyle rightsquigarrow nbsp Soll nur ausgedruckt werden dass in der Grammatik G displaystyle G nbsp das Wort w displaystyle w prime nbsp aus w displaystyle w nbsp entstehen kann ohne eine Regel zu benennen schreibt man stattdessen w G w displaystyle w rightsquigarrow G w prime nbsp ist die Grammatik aus dem Kontext offensichtlich auch einfach w w displaystyle w rightsquigarrow w prime nbsp Demnach ist ein solcher Ubergang von w displaystyle w nbsp in w displaystyle w prime nbsp eine Transitionsrelation die eine naturliche Erweiterung von P displaystyle P nbsp auf alle moglichen V displaystyle V nbsp Kontexte darstellt namlich u R v u Q v R Q P u v V displaystyle rightsquigarrow u circ R circ v u circ Q circ v R Q in P u v in V nbsp wobei hier displaystyle circ nbsp die Konkatenation von Wortern bezeichnet Gibt es nun eine Folge von Wortern w 0 w 1 w n V displaystyle w 0 w 1 ldots w n in V ast nbsp bei der gilt dass fur jede naturliche Zahl i displaystyle i nbsp mit 0 i lt n displaystyle 0 leq i lt n nbsp das Wort w i displaystyle w i nbsp in w i 1 displaystyle w i 1 nbsp ubergeht w i G w i 1 displaystyle w i rightsquigarrow G w i 1 nbsp so ist w n displaystyle w n nbsp in n displaystyle n nbsp Schritten aus w 0 displaystyle w 0 nbsp ableitbar was durch w 0 G n w n displaystyle w 0 rightsquigarrow G n w n nbsp dargestellt wird Eine solche Wortfolge w 0 w 1 w n displaystyle w 0 w 1 ldots w n nbsp wird Ableitung oder Rechnung von w 0 displaystyle w 0 nbsp in w n displaystyle w n nbsp der Lange n displaystyle n nbsp genannt Weiterhin heisst w displaystyle w nbsp in w displaystyle w prime nbsp ableitbar wenn es mindestens ein n N 0 displaystyle n in mathbb N 0 nbsp gibt so dass w displaystyle w prime nbsp in n displaystyle n nbsp Schritten aus w displaystyle w nbsp ableitbar ist Wenn w displaystyle w nbsp in w displaystyle w prime nbsp ableitbar ist so wird dies durch die Schreibweise w G w displaystyle w rightsquigarrow G ast w prime nbsp dargestellt Dabei wird zusatzlich definiert dass fur jedes Wort w V displaystyle w in V ast nbsp gilt dass w G w displaystyle w rightsquigarrow G ast w nbsp ist so dass die Relation G displaystyle rightsquigarrow G ast nbsp die reflexiv transitive Hulle der Relation G displaystyle rightsquigarrow G nbsp ist Nun ist die von der Grammatik G displaystyle G nbsp erzeugte formale Sprache L G displaystyle L G nbsp diejenige Sprache die aus allen Wortern besteht die zum einen nur aus Terminalsymbolen bestehen und die zum anderen vom Startsymbol mit einer endlichen Anzahl von Schritten abgeleitet werden konnen L G w T S G w displaystyle L left G right left w in T S rightsquigarrow G w right nbsp Dabei ist es egal in welcher Reihenfolge die Produktionsregeln auf die abgeleiteten Worter angewandt werden oder ob es mehrere Moglichkeiten gibt um ein Wort w displaystyle w nbsp aus S displaystyle S nbsp abzuleiten Zwei Grammatiken G 1 displaystyle G 1 nbsp und G 2 displaystyle G 2 nbsp sind genau dann aquivalent wenn die durch G 1 displaystyle G 1 nbsp und G 2 displaystyle G 2 nbsp erzeugten Sprachen gleich sind G 1 i s t a q u i v a l e n t z u G 2 L G 1 L G 2 displaystyle G 1 mathrm ist ddot a quivalent zu G 2 Longleftrightarrow L G 1 L G 2 nbsp Wenn alle Terminalzeichen in den Worten der formalen Sprachen vorkommen dann mussen die Terminalzeichen ubereinstimmen Die Nichtterminalzeichen sind dagegen vollig frei Beispiele BearbeitenG 1 displaystyle G 1 nbsp sei eine Grammatik mit den Terminalsymbolen a b displaystyle a b nbsp den Nichtterminalsymbolen S A B displaystyle S A B nbsp dem Startsymbol S displaystyle S nbsp und mit den Regeln S A B S 1 S e 2 B A A B 3 B S b 4 B b b b 5 A b a b 6 A a a a 7 displaystyle begin matrix S amp to amp ABS amp 1 S amp to amp varepsilon amp 2 BA amp to amp AB amp 3 BS amp to amp b amp 4 Bb amp to amp bb amp 5 Ab amp to amp ab amp 6 Aa amp to amp aa amp 7 end matrix nbsp Dabei ist e displaystyle varepsilon nbsp das leere Wort welches ein Wort der Lange 0 ist Diese Grammatik G 1 displaystyle G 1 nbsp definiert die Sprache aller Worter der Form a n b n displaystyle a n b n nbsp mit n N 0 displaystyle n in mathbb N 0 nbsp So sind auf Grund der folgenden Ableitungen die Worter e displaystyle varepsilon nbsp a b displaystyle ab nbsp und a a b b displaystyle aabb nbsp Elemente der durch G 1 displaystyle G 1 nbsp beschriebenen Sprache S e displaystyle S rightsquigarrow varepsilon nbsp mittels Regel 2 S A B S A b a b displaystyle S rightsquigarrow ABS rightsquigarrow Ab rightsquigarrow ab nbsp mittels der Regeln 1 4 und 6 S A B S A B A B S A B A b A A B b A A b b A a b b a a b b displaystyle S rightsquigarrow ABS rightsquigarrow ABABS rightsquigarrow ABAb rightsquigarrow AABb rightsquigarrow AAbb rightsquigarrow Aabb rightsquigarrow aabb nbsp mittels der Regeln 1 1 4 3 5 6 und 7 Es gibt aber noch andere Moglichkeiten um das Wort a a b b displaystyle aabb nbsp aus S displaystyle S nbsp abzuleiten Eine weitere Grammatik die dieselbe Sprache beschreibt ist die kontextfreie Grammatik G 2 displaystyle G 2 nbsp mit den Regeln S a S b e displaystyle begin matrix S amp to amp aSb varepsilon end matrix nbsp Jede rekursiv aufzahlbare Sprache wird von mehreren und zwar abzahlbar unendlich vielen Grammatiken erzeugt Allerdings gibt es auch Sprachen die sich von keiner Grammatik erzeugen lassen Klassen von Grammatiken BearbeitenGrammatiken werden Klassen zugeordnet die sich durch Gemeinsamkeiten auszeichnen Die bekannteste Klassifikation beschrieben Noam Chomsky und Marcel Schutzenberger mit der Chomsky Hierarchie Chomsky Hierarchie Bearbeiten Die Chomsky Hierarchie teilt die Grammatiken nach der Art der Produktionsregeln in Klassen vom Typ 0 bis Typ 3 ein Typ 0 Grammatiken Phrasenstrukturgrammatiken sind uneingeschrankte formale Grammatiken Typ 1 Grammatiken Kontextsensitive Grammatiken durfen nur aus Regeln bestehen in denen genau ein Nichtterminalsymbol durch eine Zeichenfolge ersetzt wird Dieses Symbol darf auf der linken Seite der Regel auch von weiteren Symbolen umgeben sein die einen Kontext angeben innerhalb dessen die Ersetzung stattfinden muss Typ 2 Grammatiken In kontextfreien Grammatiken darf dagegen auf den linken Seiten der Regeln jeweils nur genau ein Nichtterminalsymbol stehen Das Symbol kann dann unabhangig vom Kontext ersetzt werden Typ 3 Grammatiken Bei regularen Grammatiken enthalten die linken Seiten der Regeln ebenfalls nur genau ein Nichtterminalsymbol Bei linksregularen Grammatiken darf die rechte Seite der Regel aus hochstens einem Nichtterminalsymbol bestehen dem hochstens ein Terminalsymbol folgt Bsp X Y a displaystyle X to Ya nbsp Bei rechtsregularen Grammatiken darf hingegen die rechte Seite aus hochstens einem Terminalsymbol bestehen dem hochstens ein Nichtterminal folgt Bsp X a Y displaystyle X to aY nbsp Die zugehorigen Sprachklassen sind abnehmend umfangreich Es besteht folgende echte Inklusionsbeziehung Fur die Sprachklassen L n displaystyle L n nbsp von Typ n displaystyle n nbsp mit n 0 1 2 3 displaystyle n in 0 1 2 3 nbsp gilt L 3 L 2 L 1 L 0 displaystyle L 3 subset L 2 subset L 1 subset L 0 nbsp Weitere Sprachklassen Bearbeiten Von der Chomsky Hierarchie abgesehen haben sich weitere Klassen an Grammatiken etabliert Monotone Grammatiken beschreiben die gleiche Sprachklasse wie die kontextsensitiven Grammatiken Etwas strenger sind die wachsend kontextsensitiven Grammatiken die eine Teilklasse der kontextsensitiven Sprachklasse beschreiben Deterministisch kontextfreie Grammatiken beschreiben die deterministisch kontextfreien Sprachen Sie werden auch durch die LR k Grammatiken beschrieben welche fur den Compilerbau von Bedeutung sind Andere im Compilerbau bekannte Grammatiken sind LL k Grammatiken und LF k Grammatiken Siehe auch BearbeitenGraphgrammatik Backus Naur Form und Erweiterte Backus Naur Form Syntaxtheorie zu formalen Grammatiken in der Linguistik Kommunizierendes Grammatik SystemLiteratur BearbeitenKatrin Erk Lutz Priese Theoretische Informatik Eine umfassende Einfuhrung 2 erweiterte Auflage Springer Verlag Berlin u a 2002 ISBN 3 540 42624 8 S 53 61 Weblinks BearbeitenWebsite zum Thema GrammatikEinzelnachweise Bearbeiten Peter Bachmann Grundlagen der Theoretischen Informatik Cottbus 2001 S 47 tu cottbus de PDF abgerufen am 12 Februar 2011 Vorlesungsskript Christian Wagenknecht Michael Hielscher Formale Sprachen Abstrakte Automaten und Compiler Springer Vieweg Wiesbaden 2014 S 28 doi 10 1007 978 3 658 02692 9 Wahrend die Bedeutung von T N displaystyle T N nbsp und ϵ displaystyle epsilon nbsp bzw l displaystyle lambda nbsp im gegebenen Fall jeweils klar ist muss man sich bei V displaystyle V nbsp ebenso wie dem haufig benutzten S displaystyle Sigma nbsp durch Uberprufung des Kontexts klarmachen was gemeint ist wobei man sich auf das Grammatik Quadrupels nicht verlassen kann a b Klaus Reinhardt Prioritatszahlerautomaten und die Synchronisation von Halbspursprachen Memento des Originals vom 17 Januar 2018 im Internet Archive nbsp Info Der Archivlink wurde automatisch eingesetzt und noch nicht gepruft Bitte prufe Original und Archivlink gemass Anleitung und entferne dann diesen Hinweis 1 2 Vorlage Webachiv IABot users informatik uni halle de Fakultat Informatik der Universitat Stuttgart Doktorarbeit 1994 Das Grammatik Quadrupel ist hier wortlich mit V S P S displaystyle V Sigma P S nbsp angegeben damit ist in der hier gewahlten Bezeichnungsweise N T P S displaystyle N T P S nbsp gemeint Normdaten Sachbegriff GND 4154991 0 lobid OGND AKS Abgerufen von https de wikipedia org w index php title Formale Grammatik amp oldid 226621183