[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/wiki16\/2021\/01\/04\/chomsky-hierarchie-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/wiki16\/2021\/01\/04\/chomsky-hierarchie-wikipedia\/","headline":"Chomsky-Hierarchie – Wikipedia","name":"Chomsky-Hierarchie – Wikipedia","description":"before-content-x4 Hierarchie der Klassen formaler Grammatiken after-content-x4 In der formalen Sprachtheorie, Informatik und Linguistik ist die Chomsky-Hierarchie (gelegentlich als bezeichnet","datePublished":"2021-01-04","dateModified":"2021-01-04","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/wiki16\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/wiki16\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/43b23197890d3c8fae398ea64a0be1800a89b045","url":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/43b23197890d3c8fae398ea64a0be1800a89b045","height":"","width":""},"url":"https:\/\/wiki.edu.vn\/wiki16\/2021\/01\/04\/chomsky-hierarchie-wikipedia\/","wordCount":4732,"articleBody":"     (adsbygoogle = window.adsbygoogle || []).push({});before-content-x4Hierarchie der Klassen formaler Grammatiken       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4In der formalen Sprachtheorie, Informatik und Linguistik ist die Chomsky-Hierarchie (gelegentlich als bezeichnet Chomsky-Sch\u00fctzenberger-Hierarchie)[1]  ist eine Containment-Hierarchie von Klassen formaler Grammatiken.Diese Hierarchie der Grammatiken wurde 1956 von Noam Chomsky beschrieben.[2]  Es ist auch nach Marcel-Paul Sch\u00fctzenberger benannt, der eine entscheidende Rolle bei der Entwicklung der Theorie der formalen Sprachen spielte.Table of Contents       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Formale Grammatiken[edit]Die Hierarchie[edit]Typ-0-Grammatiken[edit]Typ-1-Grammatiken[edit]Typ-2-Grammatiken[edit]Typ-3-Grammatiken[edit]Verweise[edit]Formale Grammatiken[edit]Eine formale Grammatik dieses Typs besteht aus einer endlichen Menge von Produktionsregeln (links \u2192 rechte Seite), wobei jede Seite aus einer endlichen Folge der folgenden Symbole besteht:eine endliche Menge von Nichtterminale Symbole (zeigt an, dass einige Produktionsregeln noch angewendet werden k\u00f6nnen)eine endliche Menge von Terminalsymbole (zeigt an, dass keine Produktionsregel angewendet werden kann)ein Startsymbol (ein ausgezeichnetes nichtterminales Symbol)Eine formale Grammatik liefert ein Axiomschema f\u00fcr (oder erzeugt) ein formelle SpracheDies ist eine (normalerweise unendliche) Menge von Symbolfolgen endlicher L\u00e4nge, die durch Anwenden von Produktionsregeln auf eine andere Folge von Symbolen (die anf\u00e4nglich nur das Startsymbol enth\u00e4lt) erstellt werden k\u00f6nnen.  Eine Regel kann angewendet werden, indem das Auftreten der Symbole auf der linken Seite durch diejenigen ersetzt wird, die auf der rechten Seite angezeigt werden.  Eine Folge von Regelanwendungen wird als a bezeichnet Ableitung.  Eine solche Grammatik definiert die formale Sprache: Alle W\u00f6rter bestehen ausschlie\u00dflich aus Endsymbolen, die durch Ableitung vom Startsymbol erreicht werden k\u00f6nnen.Nichtterminale werden h\u00e4ufig durch Gro\u00dfbuchstaben, Terminals durch Kleinbuchstaben und das Startsymbol durch dargestellt S..  Zum Beispiel die Grammatik mit Terminals {a, b}}, nicht terminale {S, A, B.}}ProduktionsregelnS. \u2192 ABS. \u2192 \u03b5  (wo \u03b5 ist die leere Zeichenfolge)EIN \u2192 wieB. \u2192 bund Startsymbol S., definiert die Sprache aller W\u00f6rter der Form        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4einnbn{ displaystyle a ^ {n} b ^ {n}}  (dh n Kopien von ein gefolgt von n Kopien von b).Das Folgende ist eine einfachere Grammatik, die dieselbe Sprache definiert:Terminals {a, b}}, Nichtterminale {S.}}, Startsymbol S., ProduktionsregelnS. \u2192 aSbS. \u2192 \u03b5Als weiteres Beispiel wird eine Grammatik f\u00fcr eine Spielzeuguntermenge der englischen Sprache gegeben durch:Terminals{generieren, hassen, gro\u00dfartig, gr\u00fcn, Ideen, Linguisten}Nichtterminale{SENTENCE, NOUNPHRASE, VERBPHRASE, NOUN, VERB, ADJ}}ProduktionsregelnSATZ \u2192 NOUNPHRASE VERBALPHRASENOUNPHRASE \u2192 ADJ NOUNPHRASENOUNPHRASE \u2192 SUBSTANTIVVERBALPHRASE \u2192 VERB NOUNPHRASEVERBALPHRASE \u2192 VERBSUBSTANTIV \u2192 IdeenSUBSTANTIV \u2192 LinguistenVERB \u2192 generierenVERB \u2192 HassADJ \u2192 gro\u00dfartigADJ \u2192 Gr\u00fcnund Startsymbol SATZ.  Eine beispielhafte Ableitung istSATZ \u2192 NOUNPHRASE VERBPHRASE \u2192 ADJ NOUNPHRASE VERBPHRASE \u2192 ADJ NOUN VERBPHRASE \u2192 ADJ NOUN VERB NOUNPHRASE \u2192 ADJ NOUN VERB ADJ NOUNPHRASE \u2192 ADJ NOUN VERB ADJ ADJ NOUNPHRASE \u2192 ADJ NOUN VERB ADJ ADJ NOUN \u2192 gro\u00dfartig NOUN VERB ADJ ADJ NOUN \u2192 gro\u00dfe Linguisten VERB ADJ ADJ NOUN \u2192 gro\u00dfe Linguisten erzeugen ADJ ADJ NOUN \u2192 gro\u00dfe Linguisten erzeugen gro\u00dfe  ADJ NOUN \u2192 Gro\u00dfe Linguisten erzeugen gro\u00dfes Gr\u00fcn SUBSTANTIV \u2192 Gro\u00dfartige Linguisten bringen gro\u00dfartige gr\u00fcne Ideen hervor.Andere Sequenzen, die aus dieser Grammatik abgeleitet werden k\u00f6nnen, sind: “Ideen hassen gro\u00dfe Linguisten“, und “Ideen erzeugen“. W\u00e4hrend diese S\u00e4tze unsinnig sind, sind sie syntaktisch korrekt. Ein syntaktisch falscher Satz (z.”Ideen Ideen gro\u00dfer Hass“) kann nicht aus dieser Grammatik abgeleitet werden. Siehe” Farblose gr\u00fcne Ideen schlafen w\u00fctend “f\u00fcr ein \u00e4hnliches Beispiel, das Chomsky 1957 gegeben hat; siehe Phrasenstrukturgrammatik und Phrasenstrukturregeln f\u00fcr nat\u00fcrlichere Sprachbeispiele und die Probleme der formalen Grammatik in diesem Bereich.Die Hierarchie[edit]  Stellen Sie Einschl\u00fcsse ein, die durch die Chomsky-Hierarchie beschrieben werdenIn der folgenden Tabelle sind die vier Grammatiktypen von Chomsky, die von ihm erzeugte Sprachklasse, der Typ des Automaten, der sie erkennt, und die Form der Regeln zusammengefasst.Beachten Sie, dass der Grammatiksatz, der rekursiven Sprachen entspricht, kein Mitglied dieser Hierarchie ist.  Diese liegen ordnungsgem\u00e4\u00df zwischen Typ 0 und Typ 1.Jede regul\u00e4re Sprache ist kontextfrei, jede kontextfreie Sprache ist kontextsensitiv, jede kontextsensitive Sprache ist rekursiv und jede rekursive Sprache ist rekursiv aufz\u00e4hlbar.  Dies sind alles richtige Einschl\u00fcsse, was bedeutet, dass es rekursiv aufz\u00e4hlbare Sprachen gibt, die nicht kontextsensitiv sind, kontextsensitive Sprachen, die nicht kontextfrei sind, und kontextfreie Sprachen, die nicht regul\u00e4r sind.[4]Typ-0-Grammatiken[edit]Typ-0-Grammatiken umfassen alle formalen Grammatiken.  Sie erzeugen genau alle Sprachen, die von einer Turing-Maschine erkannt werden k\u00f6nnen.  Diese Sprachen werden auch als bezeichnet rekursiv aufz\u00e4hlbar oder Turing-erkennbar Sprachen.[5]  Beachten Sie, dass sich dies von den rekursiven Sprachen unterscheidet, die es sein k\u00f6nnen beschlossen von einer immer stoppenden Turingmaschine.Typ-1-Grammatiken[edit]Typ-1-Grammatiken erzeugen kontextsensitive Sprachen.  Diese Grammatiken haben Regeln der Form \u03b1EIN\u03b2\u2192\u03b1\u03b3\u03b2{ displaystyle  alpha A  beta  rightarrow  alpha  gamma  beta}  mit EIN{ displaystyle A}  ein Nichtterminal und \u03b1{ displaystyle  alpha}, \u03b2{ displaystyle  beta}  und \u03b3{ displaystyle  gamma}  Zeichenfolgen von Terminals und \/ oder Nicht-Terminals.  Die Saiten \u03b1{ displaystyle  alpha}  und \u03b2{ displaystyle  beta}  kann leer sein, aber \u03b3{ displaystyle  gamma}  muss nicht leer sein.  Die Regel S.\u2192\u03f5{ displaystyle S  rightarrow  epsilon}  ist erlaubt wenn S.{ displaystyle S}  erscheint nicht auf der rechten Seite einer Regel.  Die von diesen Grammatiken beschriebenen Sprachen sind genau alle Sprachen, die von einem linear begrenzten Automaten erkannt werden k\u00f6nnen (einer nichtdeterministischen Turing-Maschine, deren Band durch ein konstantes mal die L\u00e4nge der Eingabe begrenzt ist).Typ-2-Grammatiken[edit]Typ-2-Grammatiken erzeugen die kontextfreien Sprachen.  Diese werden durch Regeln des Formulars definiert EIN\u2192\u03b1{ displaystyle A  rightarrow  alpha}  mit EIN{ displaystyle A}  ein Nichtterminal sein und \u03b1{ displaystyle  alpha}  eine Folge von Terminals und \/ oder Nicht-Terminals sein.  Diese Sprachen sind genau alle Sprachen, die von einem nicht deterministischen Pushdown-Automaten erkannt werden k\u00f6nnen.  Kontextfreie Sprachen – oder vielmehr ihre Teilmenge der deterministischen kontextfreien Sprache – sind die theoretische Grundlage f\u00fcr die Phrasenstruktur der meisten Programmiersprachen, obwohl ihre Syntax aufgrund von Deklarationen und Umfang auch eine kontextsensitive Namensaufl\u00f6sung umfasst.  Oft wird eine Teilmenge von Grammatiken verwendet, um das Parsen zu vereinfachen, beispielsweise durch einen LL-Parser.Typ-3-Grammatiken[edit]Typ-3-Grammatiken erzeugen die regul\u00e4ren Sprachen.  Eine solche Grammatik beschr\u00e4nkt ihre Regeln auf ein einzelnes Nichtterminal auf der linken Seite und eine rechte Seite, die aus einem einzelnen Terminal besteht, m\u00f6glicherweise gefolgt von einem einzelnen Nichtterminal (rechts regul\u00e4r).  Alternativ kann die rechte Seite der Grammatik aus einem einzelnen Terminal bestehen, dem m\u00f6glicherweise ein einzelnes Nichtterminal (links regul\u00e4r) vorangestellt ist.  Diese erzeugen die gleichen Sprachen.  Wenn jedoch links-regul\u00e4re Regeln und rechts-regul\u00e4re Regeln kombiniert werden, muss die Sprache nicht mehr regul\u00e4r sein.  Die Regel S.\u2192\u03f5{ displaystyle S  rightarrow  epsilon}  ist auch hier erlaubt wenn S.{ displaystyle S}  erscheint nicht auf der rechten Seite einer Regel.  Diese Sprachen sind genau alle Sprachen, die von einem endlichen Automaten bestimmt werden k\u00f6nnen.  Zus\u00e4tzlich kann diese Familie formaler Sprachen durch regul\u00e4re Ausdr\u00fccke erhalten werden.  Normale Sprachen werden h\u00e4ufig verwendet, um Suchmuster und die lexikalische Struktur von Programmiersprachen zu definieren.Verweise[edit]^ Silberztein, Max (2013).  “NooJ Computational Devices”. Formalisierung nat\u00fcrlicher Sprachen mit NooJ.  S. 1\u201313.  ISBN 978-1-4438-4733-9.^ Chomsky, Noam (1956). “Drei Modelle zur Beschreibung der Sprache” (PDF). IRE-Transaktionen zur Informationstheorie (2): 113\u2013124.  doi:10.1109 \/ TIT.1956.1056813.^ Geuvers, H.;  Rot, J. (2016). “Anwendungen, Chomsky-Hierarchie und Zusammenfassung” (PDF). Regul\u00e4re Sprachen.^ Chomsky, Noam (1963).  “Kapitel 12: Formale Eigenschaften von Grammatiken”.  In Luce, R. Duncan;  Bush, Robert R.;  Galanter, Eugene (Hrsg.). Handbuch der mathematischen Psychologie. II.  John Wiley and Sons, Inc., S. 323\u2013418.^ Sipser, Michael (1997). Einf\u00fchrung in die Theorie der Berechnung  (1. Aufl.).  Lernen einbinden.  p. 130.  ISBN 0-534-94728-X. Die kirchliche TheseChomsky, Noam (1959). “\u00dcber bestimmte formale Eigenschaften von Grammatiken” (PDF). Information und Kontrolle. 2 (2): 137\u2013167.  doi:10.1016 \/ S0019-9958 (59) 90362-6.Chomsky, Noam;  Sch\u00fctzenberger, Marcel P. (1963).  “Die algebraische Theorie kontextfreier Sprachen”.  In Braffort, P.;  Hirschberg, D. (Hrsg.). Computerprogrammierung und formale Sprachen (PDF).  Amsterdam: Nordholland.  S. 118\u2013161.Davis, Martin D.;  Sigal, Ron;  Weyuker, Elaine J. (1994). Berechenbarkeit, Komplexit\u00e4t und Sprachen: Grundlagen der theoretischen Informatik  (2. Aufl.).  Boston: Akademische Presse, Harcourt, Brace.  p. 327.  ISBN 0-12-206382-1.     (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki16\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki16\/2021\/01\/04\/chomsky-hierarchie-wikipedia\/#breadcrumbitem","name":"Chomsky-Hierarchie – Wikipedia"}}]}]