Diskussion:Chomsky-Hierarchie

Überarbeitung geplant

Ich plane diesen Artikel komplett zu überarbeiten. Den passenden Baustein setzte ich gleich noch. Und gebe dann iher mal eine kurze Übersicht zu meinen Vorstellungen. Laßt mir aber noch paar Stunden Zeit ;)

Falls einer weiß wie man für die bisherigen Diskussionen ordnungsgemäß ein Archiv anlegt, möge das bitte machen und hier verlinken. Danke.

--Kleinvieh macht auch Mist 17:00, 28. Nov 2005 (CET)

Ich hab nun eine Extraseite für erste Entwürfe und die passenden Diskussionsseite angelegt, und möchte euch bitten dort nachzusehen. Die hier bereits genannten Vorschläge werde ich mit der Zeit auch mal durchgehen und dort miteinarbeiten, falls dies nicht schon in der aktuellen Version soweit getan wurde. --Kleinvieh macht auch Mist 19:30, 28. Nov 2005 (CET)

---

Älteres

Ich schlage vor, den Abschnitt "formale Sprachen" auf eine Extraseite auszulagern (bzw. nur dort zu behandeln), damit es hier gleich mit der "Hierarchie" losgeht --HaJo Gurt 12:23, 29. Mai 2003 (CEST)

Wo ist denn ein Abschnitt "formale Sprachen"? Falls Du "formale Grammatiken" meinst, warum willst Du den Auslagern? Der normale unwissende Leser wird sicher diese Information brauchen. Warum willst Du Ihn also erst zu den "formalen Grammatiken" schicken?. Ich glaube da findet man übrigens jetzt schon genau diesen Teil. --Coma 18:19, 29. Mai 2003 (CEST)

Sorry, ich meinte auch "Formale Grammatiken". Der Text hier von Anfang bis "Beispiele" ist fast genau der gleiche wie der Text im Artikel "Formale Grammatiken" im Abschnitt Defininition ... Beispiel. Insofern kann man den Text hier streichen und nur den Link dortin lassen. Man muss ja nicht überall die Grundlagen nochmal reinkopieren. --HaJo Gurt 19:16, 29. Mai 2003 (CEST)

Naja, wenn es das Verständnis erleichtert bin ich schon dafür. So lang ist der Abschnitt ja auch nicht. Und es wird und wurde schon oft gesagt, das wir ruhig redundant sein dürfen. Die engl. WP, aus der ich übersetzt habe hat den Teil glaub auch drin (hatte sie zumindest). Ist nat. auch nicht unbedingt ein Kriterium, aber ich bin für drin lassen. Wir können ja auch Abstimmen. :-) --Coma 19:22, 29. Mai 2003 (CEST)

Kompromiss: Kurze Definition hier, ausführliche bei Formale Grammatik --HaJo Gurt 15:10, 1. Jun 2003 (CEST)

Können wir machen, aber ich finde die Definition zu kurz, insbesondere, da unten Bezug auf (die Alte Definition) genommen wird. --Coma 22:03, 1. Jun 2003 (CEST)

Wieso kann man news/79066 Der Sitz von Chomskys "Universal- Grammatik" im Gehirn nicht drinnen lassen? nerd

Scheinbar landet man da nicht auf der richtigen Seite?! Abgesehen davon finde ich den Link auch nicht so passend und bezweifle dass er besonders wertvoll ist. --Coma 14:12, 24. Jun 2003 (CEST)

Bei der Universal-Grammatik handelt es sich um eine hypothetische Funktion (?) im menschlichen Gehirn, die Basis des Spracherwerbs in den ersten Lebensjahren ist. Bei der Chomsky-Hierarchie handelt es sich um eine Klassifizierung formaler Sprachen. Was ist da die Gemeinsamkeit?

Obendrein geht es in dem Artikel nur um eine spezielles Experiment zur Gehirntaetigkeit beim Erlernen einer fremden Grammatik.

--zeno 14:25, 24. Jun 2003 (CEST)

Danke, ist ja nicht so einfach, das Gebiet (für mich) .--nerd

Zwei Fragen: So wie ich es gelernt habe, können reguläre Grammatiken auch Regeln der Form $A\rightarrow T^{*}N$ bzw. $A\rightarrow NT^{*}$ enthalten - die Einschränkung ist, dass Nonterminale entweder nur ganz links oder ganz rechts angehängt werden. Die Definition der regulären Grammatiken in diesem Artikel entspricht dem, was ich als elementar linkslineare bzw. elementar rechtslineare Grammatiken kenne. Gibts da verschiedene Definitionen? Außerdem stellt die Formel bei den regulären Grammatiken lediglich die Regeln für eine rechtslineare Grammatik dar - ist das Absicht, dass das linkslineare Pendant nicht auftaucht? -- Wiedenfroegen 21:10, 27. Jun 2005 (CEST)

---

Wäre menschliche Sprache vom Typ 2 oder 3, so wäre diese Aufgabe trivial.

Dieser Satz ist falsch. Nur weil eine Sprache kontextfrei ist, ist ihre Verarbeitung noch lange nicht trivial. Das gesamte Problem der Semantik und Pragmatik ist dann noch nicht gelöst, es wird immer noch Mehrdeutigkeiten geben, die nicht aufgelöst werden. Und vielleicht haben wir es mit 30.000 Produktionsregeln zu tun, die alle herausgefunden werden müssen. --zeno 18:49, 29. Feb 2004 (CET)

Ringverweise

Sehe gerade, daß die kontextfreie / -sensitive Grammatik über einen Redirect einen Ringverweis zur Chomsky-Hierarchie bringt. Die Themen werden aber auch im Beitrag verlinkt. Absicht mit dem Ziel eigene Beiträge daraus zu machen - oder Zufall? --15:44, 15. Sep 2004 (CEST)

Das stört mich auch ein wenig. Deshalb meine Frage: Sollen für kontextfreie Grammatik und ähnliche Dinge eigene Artikel angelegt werden? (Bitte schaut euch auch mal den 1. Abschnitt der Diskusion an. Ich plane diesen Artikel komplett zu überarbeiten und bitte um eure Unterstützung.)

Schreibweise der Produktionen

edit: hatte sich grad erledigt. Hatte mich über die Schreibweise der Produktionen gewundert. Ich finde die eigentlich ziemlich wichtig - leider stechen die nicht wirklich als eine Art Übersicht heraus. Wie wärs mit sowas an prominenter stelle - z.B. bei jedem Typ auf der Rechten Seite? Die Mengen N Nichtterminale und T Terminale bräuchte man auch nur einmal definieren. -cljk 00:39, 3. Nov 2004 (CET)

Reguläre Sprachen?

Was mir an dem ganzen Artikel noch fehlt ist eine Begründung, warum man bei "regulären Sprachen" hierher kommt. Ist ja nicht jeder Leser Informatiker oder Sprachwissenschaftler. P.S.: Studium ist irgendwie zu lange her um den Zuastz selbst zu schreiben. --ThSpeck 21:19, 11. Nov 2004 (CET)

Definition kontextsensitive Sprache

In der Definition von kontextsensitiven Sprachen steht "alle Regeln haben die Gestalt $\alpha A\gamma \rightarrow \alpha \beta \gamma$ (modulo Wahl der Buchstaben), oben wird aber nur angegeben, dass für alle Regeln $w_{1}\rightarrow w_{2}$ gilt, dass $|w_{1}|\leq |w_{2}|$ ist. Mir ist aus meinen Theorievorlesungen auch die zweite Definition geläufig - ist die erste eine Normalform?

-- Johannes

wie wärs mit einer erklärung aller verwendeten symbole?

---

$|w_{1}|\leq |w_{2}|$ sagt aus, dass alle Produktionen ein schon erzeugtes Wort nie verkürzen, es lediglich gleich lang bleibt oder länger wird (mit $|w|$ sind die Anzahl der Buchstaben im Wort $w$ gemeint). $\alpha A\gamma \rightarrow \alpha \beta \gamma$ ist eine entsprechend allgemeine Produktionsregel.

---

Historisch verhält es sich so: Zuerst wurde kontextabhängig ersetzt: $\alpha A\gamma \rightarrow \alpha \beta \gamma$ Dann hat Kuroda bewiesen, dass das äquivalent ist zu $|w_{1}|\leq |w_{2}|$.

Ich werde das demnächst, sobald ich mal dazu komme, hier so darstellen. --Gerhard Buntrock 03:14, 11. Aug 2005 (CEST)

Fehler in der Beschreibung kontext- sensitiver Funktionen?

Im Unterschied zu kontextfreien Grammatiken ist die Anzahl der Variablen (egal ob Terminal oder Nicht-Terminal) auf der linken Seite bei einer kontextsensitiven Grammatik > 1. Einzige Ausnahme: $S\rightarrow \varepsilon$

---

dieser letzte absatz der kontext-sensitiven Grammatiken dürfte so nicht stimmen.

Denn laut folgender definition

---

Typ-1-Grammatiken besitzen nur Regeln der Form $\alpha A\beta \rightarrow \alpha \gamma \beta$, wobei $A$ ein Nichtterminal und $\alpha \gamma \beta$ Wörter bestehend aus Terminalen ($\Sigma$) und Nichtterminalen ($N$) sind. Die Wörter $\alpha$ und $\beta$ können leer sein, aber $\gamma$ muss mindestens ein Symbol (also ein Terminal oder ein Nichtterminal) enthalten.

---

können $\alpha$ und $\beta$ leer sein, und damit muss die linke Seite nicht immer > 1 sein.

---

Wie wird dann das leere Wort $\varepsilon$ erzeugt?

So wie es da steht, mit der Sonderregel $S\rightarrow \varepsilon$ --80.141.153.160 18:56, 23. Jul 2005 (CEST)

Das leer Wort

Bei der Kontextsensitive Gramtik, steht das es ist erlaubt S \rightarrow \varepsilon (mit der bestimmten vorrausetzung). Aber darf nur der Startsymbol ein \varepsilon regel haben oder auch andere Nonterminale?

Baagil

Kein Nonterminal, das auf der rechten Seite einer Regel vorkommt, darf auf $\varepsilon$ abgebildet werden. Wenn man solches erlaubt, kann man bereits alle rekursiv aufzählbaren Sprachen erzeugen!

--Gerhard Buntrock 03:19, 11. Aug 2005 (CEST) Die Konklusion einer regulaeren Grammatik kann laut gleichnamigem Abschnitt das leere Wort sein. Widerspricht das aber nicht der Aussage, dass die Konklusion einer kontextfreien Grammatik mindestens ein Symbol enthalten muss (-> Laengenbeschraenktheit)?

--Benutzer:Valodim 22:13, 5. Maerz 2005 (CEST)

Natürliche Sprachen

Von den formalen Sprachen werden die natürlichen Sprachen unterschieden. Der ursprüngliche Weg zur maschinellen Übersetzung bestand darin, jede menschliche Sprache als formale Sprache darzustellen. Um zu einer semantisch korrekten Übersetzung zu gelangen, benötigt man dann ein vollständiges semantisches Modell für jede natürliche Sprache. Wenn jetzt die Semantik eines Satzes in dem Modell abgebildet ist, kann man zurück in eine beliebige Sprache wechseln, in der diese Semantik ausdrückbar ist. Heute ist bekannt, dass es kein vollständiges Modell der Sematik geben kann, da in der natürlichen Sprache zum Beispiel auch Paradoxien gebildet werden können, die eine besondere Intensionalität ausdrücken können. Mathematisch kann man dadurch zeigen, dass wir ins Uferlose abstrahieren können und ein Abschluss hier nicht möglich ist. Diese Folgerung können wir zum Beispiel aus dem Beweis des Satzes von Kurt Gödel ziehen: Gödelscher Unvollständigkeitssatz.

Das hab ich mal entfernt. Es gibt den Nachweis einer Grammatik für einige natürliche Sprachen, eine davon ist ungarisch. Außerdem lassen sich auch in formalen Systemen Widersprüche bilden, das ist sogar der Kerngedanke des Gödelschen Unvollständigkeitssatz: Ein formales System ist entweder unvollständig (es lassen sich nicht alle wahren Aussagen ableiten = es läßt sich nicht alles interessante sagen) oder es ist widersprüchlich (es lassen sich falsche Aussagen ableiten = es lassen sich Widersprüche und Paradoxien bilden). Von der mathematischen Seite sehe ich da keine Probleme. Eher von der jetzt im Artikel dargestellte... --LC KijiF? 21:46, 21. Sep 2005 (CEST)

Ups! Für die Bemerkung über das Ungarische würde mich eine Quellenangabe interessieren. Als Linguist bin ich mir ziemlich sicher, dass es noch niemandem gelungen ist, eine natürliche Sprache mit Hilfe einer formalen Grammatik gleich welchen Typs vollständig zu erfassen. --128.176.96.213 19:09, 25. Okt 2005 (CEST)

Und auch im Jahre 2010 gibt es noch einen (anderen) Linguisten, der sich der Aufforderung anschließt und dem Kollegen aus dem Jahre 2005 dazu gratuliert, daß er mit einer derart - sagen wir - gewagten Behauptung höflich umgeht, obwohl das auch ihm nicht leicht gefallen sein dürfte. Sie ist nämlich, mit Verlaub, ziemlicher Quatsch. --78.34.164.52 09:37, 15. Aug. 2010 (CEST)

Zustimmung im Jahre 2011 von einem Computerlinguisten. Zur Zeit steht im Artikel: ... ist bis heute der Nachweis einer (formalen) Grammatik nur für die wenigsten Sprachen gelungen, die meisten davon konstruierte Plansprachen. Für welche denn? Für Lojban glaube ich das unbesehen, aber schon für Esperanto nicht. Und selbst wenn es für diese Sprachen formale Grammatiken gibt: Wie in Natürliche Sprache (m.E. ganz richtig) steht, sind Plansprachen eben keine natürlichen Sprachen. (Weitere Diskussion s.u., wo der Stanford-Parser erwähnt wird.) -- UKoch 04:21, 9. Mär. 2011 (CET)

Noch ein Problem, das ich mit dem Artikel habe: Wenn in einem übersetzten Text nur die Vokabeln stimmen, hat der menschliche Leser in der Regel keine Schwierigkeiten bei der inhaltlichen Erfassung. Das stimmt so auch nicht, es sei denn, man legt "in der Regel" extrem großzügig aus. -- UKoch 04:21, 9. Mär. 2011 (CET)

Syntax vs. Semantik

Formale Grammatiken dienen dazu, die syntaktische Struktur von Sätzen zu beschreiben, die dann wiederum Grundlage für eine semantische Interpretation sein kann. Insofern ist das Beispiel

"Er macht einen Haufen Mist."

nicht besonders hilfreich, da er zwar semantisch uneindeutig ist, syntaktisch dagegen eindeutig. Wie wäre es mit dem Klassiker "Eine große Wildsau erlegte am Sonntag eine Jagdgesellschaft", bei dem zwei verschiedene syntaktische Interpretationen möglich sind? Das ist gleichzeitig ein Beispiel dafür, dass semantisches Kontextwissen dabei helfen kann, die Syntax von Sätzen korrekt zu erfassen (durch Elimination semantisch sinnloser Interpretationen). -- 84.63.54.217 16:19, 23. Okt. 2006 (CEST)

Ich hab das mal durch ein etwas besseres Beispiel ersetzt. --Hcy 09:24, 8. Dez. 2008 (CET)

„Das Problem besteht vor allem in der Mehrdeutigkeit menschlicher Kommunikation mit ihren verschiedenen Bedeutungsebenen.“

Naja, eine klene reguläre Sprache:

(ε | präpositionalausdruck | adverb) -nominal verb nominal> satz

(nomen | pronomen) (ε | präpositionalausdruck | attribut) -> nominal

Eingabe: ich sehen mann mit-fernrohr

Tokens: pronomen verb nomen präpositionalausdruck

Es gibt einen FIRST/FOLLOW-Konflikt, es ist uneindeutig, doch es ist und bleibt eine reguläre Sprache. Die Argumentation macht es also keinesfalls plausibel, dass z.B. das Deutsche nicht z.B. kontextsensitiv sein soll. --Chricho 15:19, 10. Jul. 2010 (CEST)

Der Abschnitt ist wirklich etwas verunglückt. Kann und will das jemand verbessern? Ich sehe das Hauptproblem darin, dass hier "Beschreibung einer natürlichen Sprache" mit Sprachverständnis/Spracherkennung verwechselt wird. Spracherkennung hat vermutlich bedeutend größere Hürden vor sich als Grammatiken zu verstehen. Das Problem der formalen Grammatik als vollständige Beschreibung der Grammatik einer Sprache vermute ich eher in den vielen Ausnahmeregeln und Sonderfällen, z.B. bei Redewendungen. Dennoch gibt es gerade fürs Englische umfangreiche formale Grammatiken, andernfalls würden Parser wie der Stanford Parser nicht funktionieren.--Zahnradzacken 17:41, 10. Jul. 2010 (CEST)

S.o.: Es gibt auch fürs Englische keine vollständige formale Grammatik. -- UKoch 04:21, 9. Mär. 2011 (CET)

Ja. Und darauf sollte sich der Abschnitt wieder zurückbesinnen und nicht Probleme behandeln, die nichts mit der Hierarchie zu tun haben. Wenn es in der Literatur eine kritische Auseinandersetzung mit Chomskys Hierarchie gibt oder mit seinen mit der Hierarchie verbundenen Modellen, dann kann das hier zitiert/referenziert werden. Alles andere ist hoffnungsloser Unsinn, der ab 2004 von verschiedenen IPs nach und nach getöpfert wurde. Gibt es dennoch Rettungsvorschläge, bevor der Absatz einfach gelöscht wird? --Zahnradzacken 15:52, 9. Mär. 2011 (CET)

Ich finde, wenn man ihn verkürzt und einige Formulierungen abschwächt, kann er bleiben. Ich mach' mich demnächst dran. -- UKoch 19:12, 10. Mär. 2011 (CET)

Hat gedauert, aber hier ist mein Vorschlag:

Obwohl Chomsky seine Forschungen mit dem Ziel verfolgte, eine mathematische Beschreibung der natürlichen Sprachen zu finden, ist bis heute der Nachweis einer korrekten und vollständigen formalen Grammatik für keine natürliche Sprache gelungen. Das Problem besteht u.a. im Zusammenspiel der verschiedenen Grammatikteile, die jeweils einzelne sprachliche Phänomene modellieren. Beim praktischen Einsatz formaler Grammatiken in der Computerlinguistik kommen Mehrdeutigkeiten auf verschiedenen Ebenen der Sprachbetrachtung hinzu; diese müssen (z.B. in der maschinellen Übersetzung) anhand des Kontextes aufgelöst werden.

-- UKoch 16:28, 21. Mär. 2011 (CET)

Ich baue obigen Vorschlag jetzt so ein. -- UKoch 14:44, 26. Mär. 2011 (CET)

Formelsprache

ich Frage mich ob die mathematische Formelsprache eindeutig zuordbar ist... wenn das jemand von euch weiß wäre das m.E. eine hilfreiche Verbesserung des Artikels

--schubi (Diskussion) 19:15, 28. Apr. 2012 (CEST)

Übersicht Typ 3

Es fehlen Regeln mit denen B etwas zugewiesen werden kann, oder? 195.145.172.242

Dient nur der Verdeutlichung, daß auf der anderen Seite ein weiteres Nichtterminal stehen kann. --LC KijiF? 10:54, 12. Okt 2005 (CEST)

Hierachie

Der Satz: "Eine Typ-1-Grammatik ist also ein Spezialfall (eine Echte Teilmenge) einer Typ-0-Grammatik, eine Typ-2-Grammatik ein Spezialfall einer Typ-1-Grammatik usw." ist imho falsch. Nur die erzeugten Sprachen bilden eine Hierarchie, nicht die Grammatiken.

Dies ist sicherlich richtig. So sind in Typ-2-Grammatiken Epsilonproduktionen aus allen Nichtterminalen erlaubt, während bei Typ-1-Grammatiken nur Epsilonproduktionen aus dem Axiom erlaubt sind. Es ist also offensichtlich, dass Typ-2-Grammatiken keine Untermenge der Typ-1-Grammatiken darstellen können. Bei den Typ-1-Grammatiken wird die Ausnahmeregel zur Längenbeschränktheit, die oben genannte Produktion aus dem Axiom auch nur erlaubt, damit die von der Typ-2-Grammatik erzeugten Sprachen wirklich eine Untermenge der Typ-1-Sprachen darstellen. Ich habe mir mal erlaubt, dass im Artikel selbst zu korrigieren, trotz der geplanten Überarbeitung, um hier eine weitere Verwirrung zu stoppen. Data2 00:34, 26. Feb 2006 (CET)

Allgemeine Kritik

• Der Artikel ist vielleicht korrekt, aber er ist ungenießbar. Das Verhältnis zwischen Fachsprache und Normalsprache müsste verbessert werden, damit er in diese Enzyklopädie passt.
• Dass kultureller Hintergrund nicht mathematisch darstellbar sei, ist eine Behauptung, die nicht haltbar ist. Wahr ist bestenfalls, dass das bis jetzt noch niemand versucht hat. Auch der Umgang mit semantischer und grammatischer Mehrdeutigkeit ist durchaus mathematisch fassbar, auch wenn hier und überhaupt im Bereich der maschinellen Übersetzung immer wieder das Gegenteil behauptet wird - aus beinah schon ideologischen Gründen, wie mir scheint, und zwar um die angeblich besondere Rolle des Menschen zu bekräftigen.

--Panda17 08:55, 1. Sep. 2007 (CEST)

Definition für Typ-1 korrekt?

Es steht im Artikel: $\forall (w_{1}\rightarrow w_{2})\in P:\left|w_{1}\right|\leq \left|w_{2}\right|$. (Kriterium 1).
Wieso wird kurz darauf dann eine bestimmte Form ($\alpha A\beta \rightarrow \alpha \gamma \beta \,$) der Ableitungsregeln vorgeschrieben? Erfüllt denn eine Regel wie diese

$\alpha A\beta \rightarrow \beta \gamma \alpha \,$, sofern $|A|\leq |\gamma |$

nicht auch jenes erste Kriterium? Oder wo liegt mein Denkfehler? --RokerHRO 23:45, 16. Jan. 2008 (CET)

Du machst keinen Denkfehler, du ueberlegst nur falsch herum. *g* Das Zweite ist kein Kriterium, das ist nur zu anschaulichen Erklaerung, mehr oder minder steht da: Es gilt <...>, die Regeln haben also die Form: <...>. Es ist also genau genommen keine weitere Regel sondern ein Korollar. Dient sicherlich auch der Darstellung der Herkunft "kontextsensitiv". --Schwarzer8Kater 18:36, 19. Feb. 2008 (CET)

CH3 entspricht DEA

Wollte nur mal kurz einwerfen, dass das geklammerte "deterministisch" in der Tabelle irrefuehrend sein kann.. ein nichtdeterministischter endlicher Automat kann die Grammatik genauso gut darstellen. --Schwarzer8Kater 20:12, 18. Feb. 2008 (CET)

Die Sprachklassen zum nichtdeterministischen und zum deterministischen endlichen Automaten sind gleich. Zu jedem nichtdeterministischen EA lässt sich ein äquivalenter deterministischer EA angeben. --Heinrich Seebauer 15:05, 7. Dez. 2008 (CET)

Abgeschlossenheit Kleene-Stern

Nur am Rande, jede Menge oder Sprache die unter Konkatenation abgeschlossen ist, muss ja zwangslaeufig auch unter der Kleeneschen Huelle abgeschlossen sein, da diese darauf beruht. Andernfalls muesste man auch noch die positive Huelle und andere Sonderformen mit aufnehmen. Daher.. eigentlich ueberfluessig oder? [Korrigieren wenn ich falsch bin ;-]--Schwarzer8Kater 18:41, 19. Feb. 2008 (CET)

Hier die Korrektur: Die Kleenesche Hülle jeder Sprache enthält auch das leere Wort. Wenn man kontextsensitive (oder monotone, oder beschränkte) Grammatiken so definiert, dass sie keine Epsilon-Regeln enthalten dürfen, dann können sie das leere Wort nicht erzeugen. Damit ist die so definierte Menge der kontextsensitiven Sprachen unter Konkatenation abgeschlossen, aber nicht unter der Kleeneschen Hülle. -- UKoch 16:35, 30. Mär. 2011 (CEST)

Phrasenstrukturgrammatik ist nicht Typ-0-Grammatik

Der Begriff Phrasenstrukturgrammatik scheint mir kein Synonym für Typ-0-Grammatik bzw. allgemeine Chomsky-Grammatik zu sein. An mehreren Stellen wird eine Phrasenstrukturgrammatik als kontextfrei beschrieben (z.B. hier), der Begriff sollte daher als Synonym aus der Überschrift entfernt werden. --Loopkid 09:11, 17. Jun. 2008 (CEST)

Unverständlich

Sorry, aber ohne irgendwo eine halbwegs allgemeinverständliche Erklärung zu haben, ist der Artikel überflüssig. Da kann ich auch gleich ein Kristallgitter auswenig lernen. Erläuterungen wie

"Typ-2-Grammatiken werden auch kontextfreie Grammatiken genannt. Es handelt sich dabei um Typ-1-Grammatiken mit $\forall (w_{1}\rightarrow w_{2})\in P:(w_{1}\in N)\land \left(w_{2}\in (N\cup \Sigma )^{\ast }\right).$

Man schreibt $G\in {\mbox{Typ}}_{2}.$"

bringen nur dem etwas, der ohnehin schon verstanden hat, worum es geht. Nix gegen Chomsky, aber für Normal-Dumme wie mich müßte da schon mehr Erklärung her. Viele Grüße --Thomas Roessing 23:41, 21. Jul. 2008 (CEST)

Hallo Thomas, hast du denn den Artikel von vorne gelesen? Hast du die verlinkten Artikel gelesen, falls dir der entsprechende Begriff nichts gesagt hast? Weißt du, was eine Formale Sprache und was eine Produktionsregel ist? Hast du hier in diesem Artikel gelesen, was die Symbole alle bedeuten? Was terminale und nichtterminale Symbole sind? Das, was du zitiert hast, ist keine Erläuterung, sondern die Definition(!) der kontextfreien Grammatik, d.h. sie kann gar nicht anders lauten. Hast du dir Kontextfreie Grammatik angeschaut? Da wird der prädikatenlogische Ausdruck ja noch mal im Fließtext formuliert. Die Einleitung des Artikels sollte möglichst allgemeinverständlich sein, für den Rest (gerade bei einem solch spezialisierten/abstrakten Thema) kannst du nicht erwarten, dass du es ohne Vorarbeit deinerseits verstehst. --Klara 21:17, 22. Jul. 2008 (CEST)

Ich glaube Du tust Benutzer Thomas Roessig unrecht. Ich habe mir den Artikel gestern Nacht zur brust genommen (nach seinem Disk-Beitrag hier) und die Einleitung mit den Beispielen und Erklärungen geschrieben (siehe Versionshistorie!). Vorher war der ARtikel wirklich nur nach Lektüre der genannten anderen Artikel lesbar. Ich denke aber eine solche allgemein-verständliche Einführung darf hier ruhig stehen. Der ARtikel verliert sicher nicht dadurch! Jkrieger 21:27, 22. Jul. 2008 (CEST)

Oh, dann vielen Dank für deine Überarbeitung! :) War eigentlich positiv überrascht, wie ausführlich das alles hier erklärt wird und daher war mir seine Kritik besonders unverständlich. Hab mich daran aufgehangen, dass er die Definition nicht versteht und die stand ja noch genauso da. Sorry, nächstes Mal schau ich in die History. --Klara 21:35, 22. Jul. 2008 (CEST)

(Nach BK) Moin, vielen herzlichen Dank für die Erläuterungen und die Beispiele. Das macht es mir doch nun wesentlich einfacher zu verstehen, was im Artikel behandelt wird. Meiner Meinung nach muß zumindest der Anfang eines Artikels auch für Nicht-Fachleute halbwegs verständlich sein, die nicht alle verlinkten Artikel gelesen haben und die nicht mit der Symbolik formaler Sprachen vertraut sind. Die Arbeit von Jkrieger ist ein großer Schritt in diese Richtung. Viele Grüße --Thomas Roessing 21:38, 22. Jul. 2008 (CEST)

Können wir den Baustein dann herausnehmen oder magst du noch weitere konkrete Kritikpunkte äußern, also welche Schritte deiner Meinung nach noch fehlen? Zur Information: Ich komme von dieser Seite hierher. --Klara 21:41, 22. Jul. 2008 (CEST)

Ich habe den Baustein entfernt. Vermutlich kann man die Verständlichkeit noch weiter verbessern, aber dafür braucht es wohl kein Bapperl. --Thomas Roessing 21:46, 22. Jul. 2008 (CEST)

Problem mit Typ 1

Hallo,

ich hab bezgl. Typ 1 widersprüchliche Definitionen gehört. Manche Leute bestehen auf die Einschränkung, dass alle Regeln die Form

$\alpha A\beta \rightarrow \alpha \gamma \beta ,$

haben sollen, manche nicht. Mein Problem: Ich denke, es ist nicht möglich, die Sprache

$L_{1}=\left\{a^{n}b^{n}c^{n}|n\geq 1\right\}$

die unten im Artikel als Typ 1 definiert wurde, mit einer Typ 1 Grammatik zu kreieren, so lange die o.g. Einschränkung gültig ist. Würde die o.g. Einschränkung nicht gelten, wäre es kein Problem, diese Sprache mit Typ 1 Regeln zu erstellen. Z.B. so:

P = {S --> ASBC, S --> ABC, CB --> BC, A --> a, aB --> ab, bB --> bb, bC --> bc, cC --> cc}

Aber laut der hier genannten Definition von Typ 1 ist die Regel CB --> BC nicht Typ 1 komform.

Grüße, Alex (Squall83)

Ich möchte hinzufügen, dass die aktuelle Definition von Typ 1 NICHT aquivalent zu einem linear beschränkten Automaten ist. Der LBA ist mächtiger als Typ 1, nämlich genau so mächtig wie Grammatiken, für die gilt:

$\forall (w_{1}\rightarrow w_{2})\in P:\left|w_{1}\right|\leq \left|w_{2}\right|$, wobei dies die Definition von Typ 1 ist, die ich kennen gelernt habe. Aber wenn hier in Wikipedia die eingeschränktere Version von Typ 1 stehen soll, müssen m.E. nach auch die Konsequenzen beachtet werden. --Squall83 13:36, 17. Jan. 2009 (CET)

Die genannte Sprache ist vom Typ 1. Gegenwärtig gibt es einige Ungereimtheiten in den obigen Defintionen, die korrigiert werden müssen. Es ist prinzipiell richtig das CB --> BC nicht Typ 1 komform ist, diese Schreibweise hat sich allerdings eingebürgert um sich so einige zusätzliche Regeln zu ersparen. Die Sprache lässt sich durchaus darstellen, ohne auf CB --> BC zurückzugreifen. --Stefan Schultz 02:51, 24. Jan. 2009 (CET)

Ich bin jetzt mehr oder weniger zufällig auf die Lösung gekommen: CB --> CD, CD --> BD, BD --> BC

Ich finde es des Verständnisses wegen sehr wichtig, dass mehr Beispiele in den Artikel aufgenommen werden, sowohl für Produktionsregeln als auch bzgl. der Frage, wie man nun genau ein Wort ableitet. D.h. der eine oder andere Ableitungsbaum wäre schön. Allein anhand der Formeln kann man es nur verstehen, wenn man die Thematik schon kennt. Außerdem helfen Beispiele, zu belegen, dass a^n b^n c^n von Typ 1 ist.

Bleibt nur noch die Frage offen, ob Typ 1 wirklich äquivalent zu einem linear beschränkten Automaten ist, denn dieser ist wie gesagt äquivalent zu einer beschränkten Grammatik (also wie Typ 1 nur ohne die Einschränkung, dass der Kontext nicht verändert werden darf).

Außerdem ist es wichtig, zu beachten, dass die Definition von Typ 1 auch in angesehenen Büchern variiert, d.h. die Einschränkung, dass der Kontext erhalten bleiben muss, gibt es nicht immer. Wenn gewünscht, kann ich die Quellen zitieren. Ich vermute, dass es daran liegt, dass Herr Chomsky kein Logiker, sondern Sprachwissenschaftler ist und dass er ursprünglich 6 Typen definiert hat (laut seinen ersten beiden Büchern, die er zu dem Thema geschrieben hat). In seinem ersten Buch hat er die Typen 0 bis 4 eingeführt, wobei aber das, was wir unter Typ 3 verstehen, dort noch nicht dabei war, sondern erst im zweiten Buch eingeführt wurde.

--Squall83 20:37, 28. Jan. 2009 (CET)

Warum sind nur Regeln 1-3 anwendbar?

Im Text heißt es: Die Grammatik gibt nur vor, welche Regeln in einer Situation anwendbar sind, nicht welche angewendet werden müssen oder sollen. In der ersten Zeile sind z. B. nur die Regeln 1-3 anwendbar, nicht aber Regel 4. Ab dem 4. Schritt ist nur noch Regel 4 anwendbar.. Leider wird nicht erklärt warum das so ist. Warum kann ich Regel 4 nicht ebenfalls als erste anwenden? --212.201.18.32 18:30, 22. Jan. 2009 (CET)

In der ersten Zeile wird ja das Startsymbol Summe (Nicht-Terminal) vorgegeben. Dieses Nicht-Terminal kann nur durch eine der ersten drei Regeln der Grammatik ersetzt werden, weil dort Summe auf der linken Seite vorkommt. Theoretisch könnte man auch Regel 4 als erstes anwenden. Allerdings würde sich dadurch nichts ändern, da die Variable Zeichen - die mit dieser Regel ersetzt wird - in der Ableitung noch gar nicht vorkommt. --89.247.67.208 19:13, 22. Jan. 2009 (CET)

Typ 3 Beispiel zur verdeutlichung?

Ich würde es für sinnvoll erachten wenn man bei Typ 3 noch ein Beispiel einfügt, da bei schnellem durchlesen das meiner Meinung nach nicht so deutlich wird, ich würde mich dafür bereit erklären. Irgendwelche Anregungen dazu? -- Ben der Honk 20:54, 18. Apr. 2009 (CEST)

Fehler bei Typ 2?

"... und auf der rechten Seite eine beliebige (auch leere) Folge von terminalen und nicht-terminalen Symbolen."

Da Typ2-Grammatiken insbesondere Typ1-Grammatiken sind, folgt aus der Definition von Typ1 dass die rechte Seite der Ableitungsregeln von Typ2-Grammatiken NICHT leer sein dürfen. Folglich muss es im Bild auch w2 aus (N vereinigt Epsilon)+ statt (~)* heißen... --87.184.191.23 09:39, 24. Apr. 2009 (CEST)

Bildest du die Chomsky-Normalform, so hast du eine Grammatik in genau der von dir verlangten Form. $S\rightarrow \varepsilon$ ist dann einzige Ausnahme, wie auch bei Typ-1. In meinen Unterlagen finde ich übrigens nur die Aussage:

Jede Kontextfreie Grammatik ist äquivalent zu einer Kontextsensitiven Grammatik.

Also keine tatsächliche Teilmengenbeziehung. Siehe auch Diskussionspunkt 11 zur Hierarchie. --Zahnradzacken 18:16, 23. Jan. 2010 (CET)

Überarbeiten?

Warum genau ist der Überarbeiten-Baustein bei Abschnitt 4?

Verbessern kann man immer etwas, aber wenn der Baustein nicht begründet wird, möchte ich ihn gerne demnächst entfernen. --Zahnradzacken 17:10, 23. Jan. 2010 (CET)

Der Überarbeiten-Baustein am 01.Dezember 2008 durch Benutzer:Squall83 in den Artikel eingefügt worden. Begründet hat er es auf der Diskussionsseite nicht.

Ich persönlich störe mich an dem Satz „Jede reguläre Sprache ist kontextfrei, jede kontextfreie Sprache ist kontextsensitiv und jede kontextsensitive Sprache ist rekursiv aufzählbar.“

Als Informatiker und Mathematiker weiß ich zwar, das mit diesem Satz die Teilmengen-Beziehung verdeutlicht werden soll. Wenn ich mich jedoch in die Perspektive eines natürlichsprachlich denkenden Laien hineinversetze, finde ich den Satz grob unverständlich. Spätestens beim Gedankengang „kontextfrei ist kontextsensitiv“ steigt dieser aus dem Artikel aus. -- La Corona • ?! 19:50, 23. Jan. 2010 (CET)

Ich finde, es gibt Sätze viel früher im Artikel, an denen man mehr zu knabbern hat. Dass die Teilmengen-Beziehung geschildert wird, wird ja anschließend sogar nochmal erwähnt. Man kann den Abschnitt gerne umformulieren, aber den Baustein rechtfertigt das noch nicht, oder?

Hast du einen Vorschlag, das Problem mit „kontextfrei ist kontextsensitiv“ zu lösen? Wäre es weniger holprig zu sagen: Jede Sprache aus L3 ist auch in L2, ... und jede Sprache in L1 ist auch in L0? Oder stört dich allgemein der Satzbau? (nicht signierter Beitrag von Zahnradzacken (Diskussion | Beiträge) 22:03, 23. Jan. 2010 (CET))

Fehler: kontextsensitive != monotone Grammatik

Aus der Überschrift "Typ-1-Grammatik (kontextsensitive bzw. monotone Grammatik)", und dadurch, dass nicht weiter darauf eingegangen wird, geht hervor, dass die beiden Grammatiken dasselbe sind. Das ist jedoch NICHT der fall!

Produktionen:   ,  ∈ (N ∪ T)+,  ∈ (N ∪ T)* monoton:   , || ≤ || (S   erlaubt wenn S nicht auf der rechten Seite einer Produktion) kontextsensitiv: uAv  uwv, A ∈ N, w ∈ (N ∪ T)+, u, v ∈ (N ∪ T)* (S   erlaubt wenn S nicht auf der rechten Seite einer Produktion) (nicht signierter Beitrag von 62.178.15.161 (Diskussion | Beiträge) 16:08, 20. Mär. 2010 (CET))

Im Prinzip stimme ich dir zu. Ich habe aber einige deutschsprachige Bücher gefunden, die das, was du als monoton bezeichnest, als Definition für kontextsensitiv hernehmen: [1], [2], [3]. Aber selbst Hopcroft und Ullman sagen in [4] und in "Introduction to Automata Theory, Languages and Computation", dass lediglich $\left|\alpha \right|\leq \left|\beta \right|$ gelten muss, $uAv\rightarrow u\alpha v$ sei lediglich eine Normalform, die den Namen motiviere, manche Autoren bevorzugten diese Form, beide Grammatiken seien aber sprachäquivalent.

Nunja, man sollte es einheitlich machen und auf den Namenskonflikt hinweisen. Werde ich demnächst in Angriff nehmen. --Zahnradzacken 20:23, 20. Mär. 2010 (CET)

Nachtrag: Ordnet man Monotone/Nicht-verkürzende Grammatiken der Typ-1-Ebene zu, hätte man eine durchgängige Inklusionsbeziehung zwischen den Grammatiken. Vermutlich bevorzugen deshalb einige Autoren diese Definition der CSGs. Leider habe ich noch kein Dokument von Chomsky oder Schützenberger gelesen, in dem die Hierarchie mit den Grammatiken definiert ist. --Zahnradzacken 20:26, 20. Mär. 2010 (CET)

Korrekt: Dei Grammatiken sind sprachäquivalent, erzeugen also genau dieselben sprachen. Most und Wein machenn aber auch beide einen kater und sind trotzdem nicht dasselbe... Die Grammatiken der Chomsky Hierarchie haben KEINE vollständige inklusion bzw strikte hierarchie! Das lässt sich mit einfachen Beispielen beweisen: Die Produktion AD->BC ist nicht kontextsensitiv, sehr wohl aber Monoton! Natürlich lässt sich mit zusätzlichen Produktionen daraus eine kontextsensitive Grammatik machen... Genauso wie sich aus Most Wein machen lässt. Zu behaupten Kontextsensitive Gramamtiken und Monotone Grammatiken wären dasselbe, ist schlichtweg falsch.

-- Joehopf 12:49, 21. Mär. 2010 (CET)

Nun, Hopcroft und Ullman taten aber genau dies 1969 und 1979 in den beiden genannten Veröffentlichungen. „Schlichtweg falsch“ ist es schon deshalb nicht, weil letztlich jeder für sich in seiner Veröffentlichung Begriffe definieren kann, wie er möchte. Wenn du einen Blick in die verlinkten Google-Bücher werfen würdest, könntest du das an Beispielen sehen. Bloß hier sollte nichts neu definiert werden. Da es aber genügend Literatur gibt, die das, was andere monotone Grammatik nennen, selbst kontextsensitive Grammatik nennt, kann auch hier nicht das eine oder das andere Weltbild zementiert werden.

Da aber der Begriff der monotonen Grammatik existiert, aber nur dann sinnvoll erscheint, wenn man unterscheidet, finde ich es schon gerechtfertigt, die "strengere" Definition anzugeben und lediglich darauf hinzuweisen, dass manche Autoren die Definition der monotonen Grammatik für die kontextsensitive Grammatik verwenden.

--Zahnradzacken 00:54, 22. Mär. 2010 (CET)

Abschnitt 'Erläuterungen zur Grundidee'

Ich wäre dafür den Abschnitt auf die Passagen zu reduzieren, die sich auch auf das Lemma beziehen. Wer den Artikel zur Chomsky-Hierarchie besucht, ohne etwas von formalen Sprachen zu wissen, will vermutlich auch weiterhin nicht zu viel auf einmal darüber erfahren oder dürfte bereit sein, sich zunächst den Artikel Formale Sprache anzusehen (zugegeben, derzeit keine Lösung). Überhaupt: In jedem Artikel aus dem Gebiet der formalen Sprachen erstmal zu erklären, was formale Sprachen sind, käme der Idee gleich, in jedem Artikel zur neueren Geschichte Deutschlands zu erzählen, was bisher so geschah (Beispiel Bundestagswahl 2005: Was ist der Bundestag, wie wird gewählt und warum überhaupt?).

Mein Vorschlag wäre, die meisten Absätze nach Formale Sprache zu verschieben – dort wird sowas dringend benötigt. --Zahnradzacken 18:45, 24. Jul. 2010 (CEST)

Überarbeiten, Lückenhaft

Der Abschnitt "Erläuterungen zur Grundidee" ist geschwätzig und ungenau. Verständnis schafft man nicht mit vagen Allgemeinheiten, die noch dazu sichtlich nicht belastbar sind. :Die hier angemerkten Entsprechungen sind keine absoluten Parallelen, geben aber eine ungefähre Idee des Konzepts. Besser kann man nicht ausdrücken, dass man nur Stroh drischt.

Es fehlt konkret z.B. die Beziehung zu Semi-Thue-Systemen, die auch im Artikel Formale Sprache nicht geboten wird. Eine CG hat nämlich zwei Alphabete, und als Ableitungen gelten nur solche Ableitungen im Semi-Thue-Sinne, die in einem Wort nur aus Terminalen enden. Deshalb auch der Begriff der Satzformengrammatik, bei der diese Einchränkung nicht gemacht wird. -- Silvicola Diskussion Silvicola 10:10, 8. Aug. 2010 (CEST)

Der vorangehende Abschnitt sollte dir nicht entgangen sein. Ich nehme daher an, du widersprichst dem Vorschlag, das Kapitel überwiegend zu verschieben? Ich stimme zu, dass der Abschnitt ungenau ist. Die entsprechenden Formulierungen könnte man verbessern. Die Ursache der Geschwätzigkeit sehe ich darin, dass sich der Text am falschen Ort befindet. Den Zweck, sowohl Laien als auch Geschulten Zugang zur Thematik zu ermöglichen, sehe ich aber durchaus mit Hilfe dieses Abschnitts ansatzweise erfüllt.

Den Lückenhaft-Baustein verstehe ich nicht ganz. Sicher könnte man etwas zu dem Thema sagen, aber eine Lücke sehe ich nicht klaffen. Dazu müsste irgendwo schon Bezug auf Semi-Thue-Systeme genommen worden sein, ohne dass die Beziehung erklärt würde. Die Bezugnahme fehlt aber gänzlich, der Artikel wirkt in diesem Sinne auf mich kohärent und lückenlos. Die Frage ist, inwiefern das Thema speziell für dieses Lemma relevant wäre. Der Begriff Satzformengrammatik kommt mir auch etwas zusammenhanglos vor. Gibt es dazu Literatur? Ich finde nämlich gar nichts. --Zahnradzacken 12:03, 8. Aug. 2010 (CEST)

Es ist mir auch klar, das die Abgrenzungen zwischen den einzelnen Artikeln auf dem Feld der FS ausgefranst sind. Vielleicht ist Dein Vorschlag in dieser Hinsicht gut, ich habe noch nicht das Gefühl, ihm unbedingt zustimmen zu sollen, bin da also noch unsicher und am Erwägen.

Problem ist wie so oft: der einzelne Artikel sollte dem Laien genügend Zusammenhang bieten, ohne ihn auf eine nur verwirrende Link-Rundreise zu schicken.

Die Satzformengrammatik ist die Grammatik, die alle Satzformen einer C-Grammatik erzeugt. In ihr ist also jede aus dem Startsymbole erzeugbare Zeichenkette aus der Symbolmenge $N\cup T$ zulässiges Erzeugnis, im gegensatz zur zugrubndeliegenden C-Grammatik, in der als – im Sinne der Semi-Thue-Systeme: zusätzliche –Bedingung hinzukommt, dass Worte exklusiv in T* liegen dürfen.

Ich behaupte nicht, dass man den Begriff unbedingt bringen müsste. Wesentlich ist mir aber der Zshg. mit den Semi-Thue-Systemen (STS), aus denen ja der ganze Begriff der Ableiterei kommt. C-Grammatiken sind nämlich im strengen Sinne keine STS, weil eben die Zusatzbedingung Schluss immer nur in einer Zeichenkette aus T*) nicht dabei ist.

Auf diesen Zusammenhang mit den STS einzugehen finde ich deshalb nötig,

• weil die Leser hier ja herumstreifen, und wenn sie dann zweimal ableitbar in verschiedenem, aber für sie begrifflich nicht klärbarem Gebrauch finden, nur verwirrt werden. Security by obscurity funktioniert hier eben auch nicht.
• weil ein sowohl wissenschaftsgeschichtlicher wie sachlicher Zusammenhang eben besteht.

Kritik der derzeitigen Form des Abschnitts "Erläuterungen zur Grundidee" in separatem Diskussionabschnitt.

Gruß -- Silvicola Diskussion Silvicola 17:09, 8. Aug. 2010 (CEST)

Ich hoffe, ich war nicht zu voreilig im Entfernen des Bausteins. Zum wissenschaftsgeschichtlichen und tiefergreifend sachlichen Zusammenhang zwischen der Hierarchie und STS kann ich nichts beitragen. --Zahnradzacken 00:18, 24. Sep. 2010 (CEST)

Ein erster Zusammenhang ist seit einiger Zeit vorhanden, ich entferne auch den Lückenhaft-Baustein. Was noch fehlt, kann ja ergänzt werden. --Zahnradzacken 22:43, 23. Okt. 2010 (CEST)

Kritik der derzeitigen Form des Abschnitts "Erläuterungen zur Grundidee"

In der Informatik spielen formale Sprachen eine wichtige Rolle.

Sie erlauben Informationen in einer computerverständlichen Form darzustellen und verarbeiten zu lassen.

Es gäbe viele Formen, Informationen in einer computerverständlichen Form darzustellen und dann zu verarbeiten, die viel schlichter sind als CFGs. Nehmen wir beispielsweise ein Programm. Für Eingabe und Verarbeitung durch die Maschine wäre Maschinencode oder – wenn man denn unabhängiger von einer Architektur bleiben wollte – Dreiadresscode noch einfacher zu verstehen und zu verarbeiten als jede CFG-Sprache. Solche Dreiadresscode-Anweisungen kann man darstellen als Quadrupel aus Opcode und den drei (symbolischen) Adressen, dafür braucht es das ausgefeilte Konzept der CFG gar nicht, das kann man schon mit einem solchen kruden Tabellenformat "pro Zeile ein Statement mit bis zu vier Zellen" darstellen. Der spezifische Vorzug von FS scheint mir eher für den eingebenden (hier: programmierenden) Menschen zu bestehen.

Eine formale Sprache weist gewisse Parallelen zu natürlichen Sprachen auf.

Viel zu vage. Was sind denn hier "Parallelen"? Ein Fremdwort, das Präzision insinuiert, aber nicht liefert. Sind Ähnlichkeiten gemeint? Dann auch so nennen.

Sie besteht aus einer Menge von sogenannten terminalen Zeichen (in natürlichen Sprachen Silben), die zu Wörtern zusammengefügt werden können.

Wenn man die Analogie Formale Sprachen (FS) <-> Natürliche Sprachen (NS) schon bemühen will: In FS sind Terminale die nicht weiter analysierbaren Einheiten, bei Sprachen sind das aber nicht die Silben, sondern die Phoneme, bei europäischen Schriften wären es nicht (Schreib-)Silben, sondern Buchstaben.

In NS kann man verschiedene Hierarchiestufen der Lautfolgenorganisation feststellen: (terminale) Phoneme, darüber Silben, darüber Worte, darüber Sytagmen, darüber Sätze Hauptverständnisproblem für einen Laien als Leser scheint mir zu sein, dass er auf keinen Fall die umgangssprachlichen Worte mit den FS-Worten verwechseln darf. Die Entsprechung ist nämlich besser zwischen ugs. Sätzen und fs. Worten. Wegen der Gefahr, dass man nur Konfusion auslöst, scheint mir deshalb die Analogsetzung zu NS, zumindest so früh im Artikel, verkehrt. Man sollte lieber möglichst früh das gedankliche Konzept und den Begriffsapparat der FS/CFG einführen und befestigen, ehe man auch Teufel komm raus – und er wird leider oft genug herauskommen, der Teufel des Missverständnisses – analogisiert.

Außerdem gibt es einen Satz von Regeln (Grammatik genannt), der beschreibt, wie aus Wörtern sogenannte gültige Ausdrücke (entsprechend natürlichen Sätzen) aufgebaut werden können.

Geht so.

Die hier angemerkten Entsprechungen sind keine absoluten Parallelen, geben aber eine ungefähre Idee des Konzepts.

Das ist ein Satz, der im Grunde sagt: Stimmt schon irgendwie, aber nicht so ganz. Vor solchen hüte man sich! Schließlich, dass der Leser eine leidliche Vorstellung der Konzepte bekommen soll, das ist zu leisten, und nicht zu behaupten.

Beispiele für den Einsatz von formalen Sprachen sind etwa Programmiersprachen oder Auszeichnungssprachen wie XML oder HTML.

Einsatz ist das falsche Wort, man setzt eine konkrete Sache ein, d.h. man verwendet sie, aber kein Konzept.

Sie lassen sich alle als formale Sprache ausdrücken.

OK.

Es sei angemerkt, dass die formale Sprache nur das Konzept der Datendarstellung beschreibt (zum Beispiel die Idee, dass eine XML-Datei aus verschachtelten Tags aufgebaut ist), nicht die tatsächlichen Daten.

die formale Sprache, welche denn?

Was soll der Satz eigentlich sagen? Dass eine Grammatik eine ganze Sprache definiert und nicht ein einzelnes Wort? Aber das ist ja bei allen mehr als einelementigen Sprachen immer so. Doch ich rate hier nur.

Die Parenthese setzt voraus, dass der Leser schon leidlich XML verstanden hat, sonst versteht er anhand des Beispiels gar nichts. Also macht man damit eine schädliche Voraussetzung.

Die Idee hinter formalen Sprachen ist es, eine mathematisch exakte Beschreibung für eine solche Sprache zu finden.

Besser: FS haben den Vorzug, eine mathematisch präzise Beschreibung des dadurch definierten Umfangs einer Sprache zu liefern.

Darauf aufbauend können dann Verfahren konstruiert werden, die diese Sprachen verarbeiten (sogenannte Parser).

Nicht nur, es gibt ja umgekehrt auch Ausgabe in einer Sprache.

Im letzten Absatz wurden schon die Grundelemente einer formalen Sprache genannt.

Zu geschwätzig.

Zum einen muss es eine Menge von Grundzeichen geben. Sie wird als Alphabet $\Sigma$ bezeichnet und kann zum Beispiel die Menge aller Buchstaben und aller Ziffern sein.

muss geben, kann sein stören mich.

$\Sigma$ ist Variable, jeder kann natürlich das Terminalalphabet mit dem Variablennamen bezeichnen, der ihm gerade gefällt, etwa auch mit T, oder $T_{1}$, $T^{12345abc}$ usw.

Vorschlag für den Nachsatz, um ihn verständlicher zu machen: : Will man eine FS der Dezimalzahlen entwerfen, würde man als Alphabet etwa die Menge aller Dezimalziffern zusammen mit dem Komma und den beiden Vorzeichen wählen.

Das zweite Grundelement ist die Grammatik mit ihren Regeln. Grammatiken werden hier durch Ersetzungsregeln $\alpha \rightarrow \beta$ dargestellt. Damit kann man in einem gültigen Wort der Sprache die Zeichen $\alpha$ durch die Zeichen $\beta$ ersetzen und erhält wieder ein gültiges Wort.

Stimmt nicht, weil man im Zuge einer Ableitung, vom letzten Schritt abgesehen, nur Satzformen erzeugt und keine Worte. Man kann aus einem gültigen Wort bei CGs in Wahrheit gar kein weiteres Wort erzeugen, weil dazu noch ein NTS enthalten sin müsste, und dann wär's kein WOrt der erzeugten Sprache gewesen.

Es sollte explizit gesagt werden, dass $\alpha$ und $\beta$ Zeichenketten sein lönnen.

Zusätzlich benötigt man noch ein Startzeichen, oft auch als Axiom bezeichnet. Das ist ein Zeichen, das per Definition ein Wort der Sprache ist.

Nein, es ist eine Satzform.

Man muss hier noch zwischen terminalen und nicht-terminalen Symbolen unterscheiden. Streng genommen dürfen Sätze oder Wörter einer formalen Sprache nur aus Terminalsymbolen (zum Beispiel den Buchstaben des Alphabets) bestehen. Es werden aber noch sogenannte Nicht-Terminale (oder Variablen) eingeführt. Das sind Platzhaltersymbole, die in gewisser Weise ein Konzept repräsentieren.

Die Trennung in TS und NTS ist, neben der restriktiveren Ende-Muss-Terminalzeichenkett-Sein-Regel, der wesentliche Unterschied zu STS. Es sollte unbedingt gesagt werden:

• CG sind durch die zusätzlichen NTS erzeugungsmächtiger
• Die Definition des erzeugtens Wortes eines CG ist mathematisch streng und schließt Zeichenketten, die NTS enthalten, definitiv aus. Man muss auf diesem Feld die Begriffe streng nehmen, dieses streng genommen ja nicht, aber dann halt doch, das hier anklingt, ist ein Graus in jeder mathematisch definierenden Disziplin. Man kann doch nicht Definitionen, die man gerade genannt hat, danach unbeachtet lassen, dann sind sie ja für die Katz!

Das folgende Beispiel verdeutlicht das.

Wieder gesagt, was man sagen will, statt es treffend zu sagen.

Hier höre ich mal auf. Notabene, ich bin durchaus für eine Motivierung der relevanten Begriffe, das ist wichtig. Aber man muss sie auch definieren, und nicht im X-ist-irgendwie-so-was-Ähnliches-wie-Y-Stil

Gruß -- Silvicola Diskussion Silvicola 17:09, 8. Aug. 2010 (CEST)

Niemand hat den Edit-Link deaktiviert. Erhebliche Zustimmung meinerseits. Das Mergen mit anderen Artikeln (Siehe Diskussion weiter oben) kann ggf. später erfolgen. --Daniel5Ko 01:31, 11. Aug. 2010 (CEST)

Pünktchennotation

$\forall (w_{1}\rightarrow w_{2})\in P:(w_{1}\in N)\land$ $(w_{2}\in \Sigma \cup (\Sigma \cdot N\ {\dot {\lor }}\ N\cdot \Sigma )\cup \{\varepsilon \})$

Was bedeuten die Pünktchen zwischen den Mengen (Konkatenation zweier Mengen?) und was bedeutet das Pünktchen auf dem Oder (Kontravalenz für Mengen?)? Stellt das Pünktchen auf dem Oder sicher, dass die Regeln in P entweder alle linksregulär sind oder alle rechtsregulär (sodass es nicht zur Vermischung beider Regeltypen in einer Grammatik kommt)? Gibt es einen Wiki-Artikel zu dieser Notation? --Abdull 00:29, 31. Aug. 2010 (CEST)

Diese Notationsweise, falls es denn nicht ein bloßer Redaktionsfehler wäre, was ich für wahrscheinlicher halte, kenne ich ebenfalls nicht. Ich hielte sie auch, selbst wenn sie denn richtig gemeint wäre, für verwirrend und gefährlich; schließlich könnte man jede lineare Grammatik durch Einführung neuer Nichtterminalsymbole und Regeln recht trivial und erzeugungsäquivalent umformen in eine mit nur links- und rechtsregulären Regeln, jedoch ist die Klasse der regulären SPrachen mächtiger als die der regulären. Es wäre wohl besser, die Definition auf nur einen Fall zu beschränken und am Ende mit einem Textzusatz salopp gesprochen zu erläutern: Es geht genauso auch andersrum. -- Silvicola Diskussion Silvicola 10:15, 31. Aug. 2010 (CEST)

Schon geändert, aber ausführlicher. -- Silvicola Diskussion Silvicola 11:35, 31. Aug. 2010 (CEST)

Überarbeiten, 2010-12-17

1. Auch die 0 ist eine Ziffer, wieso wurde die weggelassen? Weil das Beispiel mit einem Verbot de führenden Null in Zahlen schon wieder zu kompliziert würde? Dann muss man eben ein wirklich einfaches Beispiel nehmen und nicht eines so hindrehen.

2. Man sollte sich gerade beim einführenden Beispiel nicht (mit den zwei Punkten) schon wieder Freiheiten vom exakten Formalismus gönnen, nur weil man nicht 10 ganz analoge Produktionen untereinander hinschreiben will. Lieber ein einfacheres Beispiel nehmen.

-- Silvicola Diskussion Silvicola 15:43, 17. Dez. 2010 (CET)

3. Jeweils gleich mächtig wie uneingeschränkte formale Grammatiken sind Turingmaschinen. — Das ist so unerläutert den Lesern unverständlich. Vorher ist von einem "Formalismus zur Beschreibung von Sprachen" die Rede, nun von einem zur Erzeugung oder Entscheidung, und selbst das noch wird offengelassen.

Ja, den Satz muss man unbedingt ausbauen. Den Wechsel von "Beschreibung" zu "Erzeugung/Entscheidung" sehe ich aber bisher nicht. --Zahnradzacken

Eine generative Grammatik ist ein i.a. nichtdeterministisches Verfahren, dass genau alle Worte ihrer Sprache erzeugen kann und das ein bestimmtes WOrt erzeugt, wenn man es in geeigneter Weise steuert.

Eine (deterministische) TM dagegen operiert auf zwei Arten: Entweder als Erkennungsautomat mit Ausgabe 0/1(/nicht haltend); oder durch rekursives Aufzählen; oder in einer noch anderen, von mir hier unerahnten Betriebsmethode, die dann vermutlich auch dem Leser nicht evident ist.

Betrachten wir den Fall des Erkennungsautomaten. Würdest Du sagen wollen, ein Rehgatter ist genauso mächtig wie ein Jägerfernglas? Mit dem einen kann man Rehe erzeugen, mit dem anderen sie erkennen.

Oder zum rekursiven Aufzählen: Das geht eben deterministisch, eins nach dem anderen, keins wird ausgelassen, während man bei der generativen Grammatik sozusagen ein einziges, aber beliebiges Wort erzeugt. Das ist schon etwas anderes.

Zudem ist dann selbst für den leidlich Kundigen unklar, in welcher Verwendungsweise, nämlich als Erkennungs- oder als Aufzählautomat man die TM hier versteht, eine Laie dagegen versteht nur Bahnhof. Nämlich den mit dem Schild Hat-wohl-irgendwas-zu-tun-mit-dem-Tu-Dingsda-aber-frag-mich-nicht.

TMs, PDAs und EAs sind zunächst keine greifbaren Maschinen, sondern mathematische Modelle. Ihre Semantik/Aufgabe ist in der Theorie die Beschreibung von Sprachen. Nur das Prinzip ist anders (akzeptieren&verwerfen statt erzeugen). Das Problem ist natürlich, dass ohne Erklärung einem Laien diese unterstellten Zusammenhänge nicht in den Sinn kommen. Allerdings sollten wir uns für das Thema Laienverständlichkeit vielleicht einen Einstiegsartikel (z.B. Formale Grammatik) vornehmen, denn warum sollte man die Zusammenhänge ausgerechnet hier erklären (oder hier und an hundert anderen Stellen)? --Zahnradzacken

4. Für "leistungsfähige(n) Automatenmodelle(n)" hat der Laien-Leser eine Alltagsinterpretation, die ihn hier auf Abwege führt.

Spricht etwas gegen ausdrucksstark? Das ist ohne Erklärung natürlich auch vage, aber wenn man sich etwas darunter vorstellen kann, dann tendenziell etwas weniger Falsches. --Zahnradzacken

Ein Automat ist sicher nicht ausdrucksstark, weil er ja nichts ausdrückt, sondern erkennt oder aufzählt. Bei Klassen von Automaten, also eine Abstraktionsstufe höher, wird das noch unverständlicher. Es gilt das schon irgendwo von mir genannte doppelte Mächtigkeitsargument: Jede Automatenklasse hat genausoviele Mitklieder wie irgend eine andere, jede Klasse hat irgendeine zu jeder anderen gleichmächtige erkannte Sprache.

Vermutlich ist es besser, so etwas ähnliches zu schreiben, wie ich es jetzt grob und ins Unreine tue: Zu jeder Klasse von GG gibt es eine korrespondierende Klasse von A, so dass jede von einem aus GG erzeugte Sprache von einem a aus A erkannt/aufgezählt wird und umgekehrt, weshalb diese G-Sprachklassen auch als A-Sprachklassen aufgefasst werden können. Insofern gibt es acuh eine Hierarchie von A.

Meiner Meinung nach drückt ein Automat schon etwas aus. Durch ihn lassen sich Sprachen modellieren. Allerdings beziehe ich mich hier auch vielmehr auf das Wort Automatenmodell, also wie "mächtig/fähig/ausdrucksstark" sind bestimmte Klassen von Automaten? Dein Mächtigkeitsargument kann ich weiterhin nicht nachvollziehen. Wenn die zu den Automatenklassen gehörigen Sprachklassen eine strikte Teilmengenbeziehung bilden, wie kann man von Gleichheit reden? Es geht ja nicht darum, dass alle unendlich viel können, sondern trotz der Unendlichkeit einige immer noch mehr als die anderen. (Warum sollte übrigens das Wort fähig nur für Menschen zulässig sein? Schon die Frage „Sind Maschinen fähig zu denken?“ könnte man sonst nicht stellen, oder siehe hier).

Kannst du mit der Formulierung leistungsfähig oder aber ausdrucksstark leben oder nicht? Der Überarbeiten-Baustein für diese Formulierung kann nicht ewig stehen bleiben. --Zahnradzacken 21:01, 6. Jun. 2011 (CEST)

Deinen Vorschlag finde ich insgesamt gut, aber ungenau (weil auch Automaten ohne Zuhilfenahme von Grammatiken Sprachen beschreiben können). Ich glaube aber, er deutet auch eine Tendenz an, die der Abschnitt generell annehmen sollte: Eine viel deutlicher lemma-orientierte Zusammenfassung auf verständliche und doch korrekte Art und Weise, anstatt den ganzen Themenkomplex grob zu erläutern. --Zahnradzacken

5. "lassen sich auch verschieden mächtige Grammatiken feststellen." — Die Grammatikklassen fielen nicht vom Himmel, sondern wurden definiert.

Das halte ich für ein philosophisches Argument. Wären nur die Typ-0-Grammatiken definiert worden, hätte es die anderen Klassen auch gegeben, nur ohne Namen. So wie man später auch noch mehr Klassen gefunden/definiert hat, ohne den einmal definierten Formalismus zu verlassen. --Zahnradzacken

6. "Zugleich lässt sich jeder Grammatikebene eine Klasse formaler Sprachen zuordnen, die je nach Tiefe in der Hierarchie verschieden umfangreich sind." — Zu jedem Sprachtyp gibt es eine unendliche Sprache, die darin liegt. Zu jedem Grammatiktyp gibt es genau gleich viele Grammatiken, nämlich abzählbar unendlich viele. und, dies jetzt ohne Grimmen desselben aus dem Bauch heraus gesagt, auch jeweils abzählbar unendlich viele Sprachen des korrespondierenden Sprachtyps. Was soll das also aussagen?

Das Wort umfangreich ist unmathematisch und ist nicht gleichbedeutend mit mächtig gemeint. Möglicherweise sind alle Sprachklassen gleichmächtig, aber es besteht dennoch eine strikte Teilklassenbeziehung. Intuitiv finde ich den Begriff also passend und nützlich, weil man sich Begriffe wie Teilmenge/Teilklasse spart. --Zahnradzacken

Es wäre besser, die gegenüber Chomsky "dazwischengeschobenen" Klassen erst nach der Behandlung der konventionellen Hierarchie zu erwähnen. Die Analogisierung zu den Automatenmodellklassen wäre überhaupt nur dann hilfreich, wenn die dem Leser schon mit Sicherheit bejkannt wären. Nun glaube ich aber, letztere sind in Wirklichkeit schwieriger zu verstehen als unser Thema GG hier. Man denke nur an die linear bandbeschränkten TM. Also bezöge man sich, um Einfacheres zu definieren, auf Schwierigeres, ein fatales Rezept für einne Enzyklopädie!

Das sprachliche (nicht: philosophische) Argument halte ich im übrigen aufrecht. Die Grammatikklassen werden ja nicht gerade in der Natur festgestellt, sondern man muss doch die Begriffe - GG verschiedener Stufen -- doch erst entwickeln, das ist keine platonische Wiedererkennung einer präexistenten Idee.

Ich hatte eigentlich gar nicht vor, die dazwischen geschobenen Klassen explizit zu erwähnen. Es ist nunmal so, dass man zu einem allgemeinen Modell auch Einschränkungen definieren kann. Drei davon wurden auch prompt in eine Hierarchie eingeordnet. Aber sowie man das Konzept GG hat, hat man auch die Möglichkeit, eingeschränktere Klassen zu finden. Dass, ohne eine Änderung vom GG-Modell, erst später weitere Klassen definiert wurden, zeigt doch, dass man danach suchen musste.

Die Analogie zu Automatenmodellen finde ich nun nicht so problematisch. Man muss erstens nicht von jedem Leser, der lieber Worte statt Formeln liest, annehmen, dass er ein Laie ist. Zweitens ist für Laien eine ungenaue Vorstellung verschieden mächtiger Automaten doch ausreichend für eine Verständnis, dass Grammatiken verschieden viel ausdrücken können (ja, alles unendlich, aber den Punkt hatten wir ja schon). --Zahnradzacken

7. "Die Regel $S\rightarrow \varepsilon$ darf aber nur dann verwendet werden, wenn das Startsymbol $S$ auf keiner rechten Seite der Produktionsregeln auftritt." — Schlecht formuliert. Es ist kein Verwendungsverbot, vielmehr darf diese triviale Produktion in dem Fall schlichtweg nicht in der Produktionsmenge enthalten sein. Geändert und motiviert.

8. Noch Missverständliches danach geklärt.

9. "Das Halteproblem ist vom Typ 0, aber nicht vom Typ 1" — Das Halteproblem ist zunächst einmal gar keine Sprache. Kann also nicht so stehen bleiben und führte wohl zu weit, wenn man's erklärt. -- Silvicola Diskussion Silvicola 17:21, 17. Dez. 2010 (CET)

Danke soweit schonmal für die Anmerkungen und Verbesserungen. Was hielt dich davon ab, die besonders kleinen Mankos zu entfernen? (Satz über Halteproblem rauswerfen, Beispiel auf drei Ziffern reduzieren?) Wenn du irgendeinen sinnvollen Zusammenhang zum Halteproblem in Worte fassen kannst, kannst du es ja mal hier skizzieren. --Zahnradzacken 21:02, 17. Dez. 2010 (CET)

@Nicht-Verbesserung: Bei manchem war ich mir nicht sicher, ob ich recht verstanden hatte, was gesagt werden sollte.

Ich meine, das wäre, wie glücklich eine zu findende Erklärung auch wäre, in jedem Falle ein Bezug auf Komplizierteres und also bei der Definition des Begriffes nicht hilfreich. Gruß-- Silvicola Diskussion Silvicola 02:05, 18. Dez. 2010 (CET)

Wäre im Artikel wohl auch unangebracht, aber ich wäre an einem Erklärungsversuch interessiert gewesen. --Zahnradzacken 13:19, 18. Dez. 2010 (CET)

Formulierungsvorschlag für monierten Abschnitt, 2011-06-09

Derzeit so:

„Ebenso wie es unterschiedlich leistungsfähige Automatenmodelle gibt (zum Beispiel endliche Automaten, Kellerautomaten oder linear beschränkte Turingmaschinen), lassen sich auch verschieden mächtige Grammatiken feststellen. Die Einteilung in vier Klassen einer Hierarchie ist durch Chomskys Arbeit historisch begründet und basiert auf Einschränkungen der Ableitungsregeln, die für die Ebenen charakteristisch sind. Zugleich lässt sich jeder Grammatikebene eine Klasse formaler Sprachen zuordnen, die je nach Tiefe in der Hierarchie verschieden umfangreich sind.“

„Die einfacheren Sprachen sind auf der einen Seite auch einfacher (und schneller) zu verarbeiten, andererseits auch nicht so mächtig. Reguläre Ausdrücke zum Suchen von Mustern in Texten entsprechen den regulären Grammatiken vom Typ 3 in Chomskys Hierarchie, welche aber nicht mächtig genug sind, um Programmiersprachen zu beschreiben. Diese werden typischerweise durch Typ-2-Grammatiken beschrieben.“

Vorschlag:

Chomsky definierte in seiner epochemachenden Arbeit vier heute gängige Unterklassen von formalen Grammatiken mit fortschreitend schärferen Bedingungen an die darin zulässigen Ersetzungsregeln. Diese vier Grammatikklassen bilden also eine Hierarchie, in der die weniger restringierten Klassen die stärker restringierten jeweils echt umfassen. Das gleiche gilt für die von den jeweiligen Grammatikklassen beschriebenen Sprachklassen, auch sie bilden eine Hierarchie. Allen vier Sprachklassen korrespondiert bei den Automatenmodellen jeweils ein Untertyp von Turingmaschinen, der genau sie akzeptiert.

Sprachen restringierteren Grammatiktyps sind im allgemeinen einfacher algorithmisch zu verarbeiten – um den Preis, weniger ausdrucksmächtig zu sein. Reguläre Ausdrücke, mit denen man etwa Muster für die Suche in Texten definiert, entsprechen zum Beispiel den sehr eingeschränkten Chomsky-Grammatiken regulären Typs (Typ 3) und solche Textsuchen sind effektiv und schnell. Dagegen taugen Grammatiken des Typs 3 wegen ihrer Einfachheit nicht zur Beschreibung von Programmiersprachen, für die man meist weniger eingeschränkte Typ-2-Grammatiken benutzt.

Erläuterung:

1. Ggf. vor dem ersten vier noch unter anderem einfügen, falls er denn dort noch andere Stufen definiert haben sollte (linear? endlich?), was ich leider nicht mehr im Kopf hatte.
2. Endliche Automaten, Kellerautomaten oder linear beschränkte Turingmaschinen sind hier noch konkret nicht zu nennen, das wäre ein Vorgriff auf Details, die ihren natürlichen Platz erst in den folgenden Klassenbeschreibungen haben, wo man sie jeweils neben den Grammatiktyp stelle.
3. "Meist" bitte stehen lassen, wegen der Van-Wijngaarden-Grammatiken (außerhalb der Hierarchie), die sehr wohl zur Beschreibung, m.W. aber nie zur Verarbeitung von Sprachen benutzt wurden.
4. In der letzten Formulierung sollte man beim Ausdruck Beschreibung von Programmiersprachen bleiben und nicht von Verarbeitung sprechen; denn bei der sind CFGs unzureichend ohne die Verwendung von Symboltabellen, mit deren meist formlos formulierter Zusatzsemantik („Keine Verwendung eines Bezeichners ohne vorige Deklaration“ o.ä.) man den Grad an Kontextabhängigkeit dazugibt, der ganz essentiell ist. Denn vom CFG-Standpunkt aus gesehen ist ja jedes Vorkommen eines generischen Tokens (Bezeichner, Litteral) immer ein und dasselbe terminale Symbol.

-- Silvicola Diskussion Silvicola 02:57, 9. Jun. 2011 (CEST)

Hallo Silvicola. Danke für deinen Verbesserungsvorschlag. Isoliert betrachtet gefällt mir dein Vorschlag besser als die bisherige Formulierung. Da das Ziel des Abschnitts eine möglichst allgemeinverständliche Einleitung ist, würde ich nur gerne auf Wörter wie restringiert verzichten. Ich fände aber wegen des Übergangs vom Absatz davor einen kurzen (metaphorischen) Vergleich mit Automaten schön.

1. In [5] wurden nur die vier Typen definiert. "Vier" trifft es aber nicht ganz, weil es keine Oberklasse von Typ-0 gibt (außer Typ-0 selbst).
2. Hast mich überzeugt.
3. Van-Wijngaarden-Grammatiken sind doch einfach spezielle Typ-2-Grammatiken oder nicht? Aber mich stört das Wort meist nicht.
4. Ja, Grammatiken dienen eher dem Beschreiben. Kein Einwand.

Zusätzliche Anmerkung:

• Du hast Recht, auch die Grammatiken als strikt hierarchisch zu beschreiben, ein Detail, das ich bisher eher aus dem Artikel entfernt habe, aus folgendem Grund: Chomsky erlaubt bei Typ-2-Grammatiken keine Epsilon-Regeln (was ich vorhin in [1] zum ersten mal gelesen habe), somit sind die Typ-2-Grammatiken eine echte Teilklasse der Typ-1-Grammatiken. In heutiger Literatur und hier in der WP sind bei CFGs Epsilon-Regeln erlaubt. Es gibt also CFGs, die keine CSGs sind. Bevor man in der Einleitung die Intuition prägt, sollte vielleicht erst das Formale an Chomskys Arbeit angepasst werden.
  • Nachtrag: Habe den Artikel ein bisschen angepasst. Diese Anmerkung sollte also keine Einschränkung mehr sein. --Zahnradzacken 16:57, 9. Jun. 2011 (CEST)

Mein Vorschlag:

Vorstehende Sätze:

„Nicht alle unendlichen Sprachen lassen sich durch solche Modelle beschreiben, es ist aber kein tauglicheres Konzept bekannt. Ein anderer Formalismus zur Beschreibung von Sprachen sind Automatenmodelle.

Uneingeschränkte formale Grammatiken und Turingmaschinen sind bei der Beschreibung von formalen Sprachen gleichmächtig, d.h. zu jeder von einer Grammatik erzeugten Sprache gibt es eine Turingmaschine, die diese akzeptiert, und umgekehrt.“

Und dann:

Ebenso wie es unterschiedlich mächtige Automatenmodelle gibt, definierte Chomsky in seiner Arbeit unterschiedliche Grammatiktypen. Er stellte eine Hierarchie aus vier Klassen auf, die, beginnend mit den uneingeschränkten formalen Grammatiken, fortschreitend schärfere Bedingungen an die darin zulässigen Ersetzungsregeln stellen, wodurch die weniger eingeschränkten Klassen die stärker regulierten Klassen jeweils echt umfassen. Das gleiche gilt für die von den jeweiligen Grammatikklassen beschriebenen Sprachklassen: auch sie bilden eine Hierarchie.

Sprachen eingeschränkteren Grammatiktyps sind üblicherweise einfacher algorithmisch zu verarbeiten – um den Preis, weniger ausdrucksmächtig zu sein. Reguläre Ausdrücke, mit denen man etwa Muster für die Suche in Texten definiert, entsprechen zum Beispiel den sehr eingeschränkten Chomsky-Grammatiken regulären Typs (Typ 3) und solche Textsuchen sind effektiv und schnell. Dagegen taugen Grammatiken des Typs 3 wegen ihrer Einfachheit nicht zur Beschreibung von Programmiersprachen, für die man meist weniger eingeschränkte Typ-2-Grammatiken benutzt.

Kommentar: Den Satz zu korrespondierenden Automaten, die Untertypen von TMs sind, habe ich gestrichen, da eine Automatenhierarchie wohl nur über Sprachäquivalenz definiert wäre (strukturell sind die Modelle sich nur ähnlich), der Satz also nicht viel Sinn ergibt. Chomsky selbst identifizierte Typ-0 mit TMs und Typ-3 mit EAs, für die beiden anderen Klassen waren noch keine Parallelen gezogen. --Zahnradzacken 16:11, 9. Jun. 2011 (CEST)

Einwände sprachlicher Natur gegenüber dem vorgeschlagenen Absatz Ebenso wie es unterschiedlich mächtige Automatenmodelle gibt, … auch sie bilden eine Hierarchie.:

1. Die Grammatiktypen gibt es (im platonischen Sinne) genauso wie die Automatenmodelle, oder andersherum gesagt: auch die Automatenmodelle sind definiert. Und selbst wenn die anderen irgendwie reale Dinge wären, könnte man nicht Konzepte ebenso wie sie definieren, da sie dann kategoriell etwas Verschiedenes wären, sondern allenfalls nach ihrem Vorbild o.ä.
2. Nicht die Klassen selbst stellen Bedingungen an die in ihnen erlaubten Regeln, vielmehr stellte der definierende Chomsky diese Bedingungen und definiert damit die Klassen. Der Satz ist ohnehin zu verschachtelt ("die" von Kommas umgeben!), da passiert so etwas.
3. Die Sprachklassen sind nicht von den Grammatikklassen beschrieben, sondern definiert. Beschrieben unterstellte nämlich, dass diese schon vorher in irgend einem Sinne existierten.

Gruß -- Silvicola Diskussion Silvicola 17:00, 9. Jun. 2011 (CEST)

Danke fürs Feedback. Zum Teil nachvollziehbare Einwände, aber es macht nur Sinn, daran rumzubasteln, wenn du nur die sprachlichen Einwände hast. Hast du noch Einwände auf anderer Ebene oder wollen wir hiermit weitermachen? --Zahnradzacken 22:08, 9. Jun. 2011 (CEST)

Ich habe das mal eingebaut und dabei noch, neben sprachlichen Details, das folgende verändert:

• Neue wesentliche Begriffe bei Ersterwähnung kursiviert
• Ein Fehler am Anfang raus: Typ-3-Sprachen sind natürlich auch Typ-2-Sprachen usw., so wie das da stand, hätte man meinen mögen, nur die Komplemente zu den nächstkleineren Sprachklassen bildeten die nächsthöhere; dies gilt aber nur für die Sprachen echt höheren Typs. Eine weitere Definition-in-der-Definition dessen, was hier echt heißt, erschien dem Verständnis hinderlich.
• Erzeugungsverfahren als wesentliches Konzept der FS genannt.
• Semi-Thue in eigenem Absatz; denn sie sind das einfachere Konzept von Erzeugungsverfahren, das dann aber doch nicht verwendet wird, denn rein formal sind CGs eben keine STS, sondern nur ähnlich.
• Danach in eigenem Absatz CGs vor dem Hintergrund von STS
• Den technischen ε-Regel-Sonderkram etwas motiviert.

Mich stören noch die Unterstreichungen im ersten Beispiel. Vor allem wenn diese unter mehreren Buchstaben durchgehen, sieht das potthässlich aus. Wäre es da nicht noch besser, die TS in Normalschrift zu belassen und die NTS fett zu setzen? Oder NTS normal und TS mit \mathtt? Mir ist schon klar, wieso man bei einem Einführungsbeispiel NTS und TS auch satztechnisch unterschieden will; aber so jedenfalls ist das zu aufdringlich.

Vgl. auch Hilfe:Textgestaltung#Formatierungen, die nicht in Wikipedia-Artikeln verwendet werden sollten mit dem <u>-Verbot. Gilt wohl für Teχ-Formeln dann genauso. Bin aber kein Regel-Pedant, es gibt immer Situationen, wo man eine WP-Regel sogar besser bricht als befolgt – aber hier nicht, oder doch nicht so.

Gruß -- Silvicola Diskussion Silvicola 02:38, 10. Jun. 2011 (CEST)

Vielen Dank für die Mühe, finde die Änderungen sehr gut. Habe nur zwei winzige Änderungen vorgenommen. Ich finde die \underline-Darstellung auch hässlich, das Problem ist aber das +-Symbol, das sich gegen \mathbf und gegen \mathtt wehrt. Wenn man die Symbole unterschiedlich darstellen will, ist es unpraktisch, wenn ein Symbol ganz anders gesetzt ist. Eine Möglichkeit wären <> um die NTs herum, finde ich aber auch nicht schön. Gruß --Zahnradzacken 13:24, 10. Jun. 2011 (CEST)

Scheint mir jetzt rund zu sein. Wegen des Beispiels nochmals: Was spricht gegen fett/nicht fett? -- Silvicola Diskussion Silvicola

Die Idee ist gut, aber TS normal und NTS anders darzustellen, sieht nicht gut aus, weil man zwischen $+$, $\mathbf {+}$ und ${\mathtt {+}}$ nicht unterscheiden kann und ${\boldsymbol {+}}$ sticht auch nicht als fett ins Auge. Andersrum die NTS fett und die TS normal darzustellen habe ich eben ausprobiert und finde das Ergebnis auch nicht gut unterscheidbar. Ich glaube, die Lösung wird sein, TS normal darzustellen und für NTS eine Hervorhebung zu finden, die annehmbar ist. Vorschläge: $\ulcorner \!Summe\!\lrcorner ,\langle Summe\rangle ,Summe_{NT}$ oder meinetwegen fett. --Zahnradzacken 23:42, 10. Jun. 2011 (CEST)

CH-1 unter Komplementbildung abgeschlossen aber CH-2 nicht?

In der Tabelle steht, CH-1-Sprachen seien unter der Komplementbildung abgeschlossen. Ich sehe nicht, wie das sein kann.

Ich weiß, dass CH-2 nicht unter der Komplementbildung abgeschlossen ist. Ist es nicht so, dass jede CH-2-Sprache auch durch eine CH-1-Grammatik ausgedrückt werden kann (die verschiedenen Chomsky-Typen liegen doch alle ineinander verschachtelt)?

Habe ich nun eine CH2-Sprache die ein Gegenbeispiel zur abgeschlossenen Komplementbildung in CH-2 darstellt (die gibt es) und fasse sie als CH-1-Sprache auf (müsste auch gehen) kann das Komplement doch nicht auf einmal wieder abgeschlossen sein -- ich habe die Sprache ja nicht verändert. (nicht signierter Beitrag von 84.57.207.185 (Diskussion) 20:49, 27. Feb. 2014 (CET))

Male Dir ein Venn-Diagramm der zwei Sprachklassen ${\mathcal {C}}_{2}\subset {\mathcal {C}}_{1}$ in Gestalt zweier konzentrischer Kreise. Nun betrachten wir eine Sprache in ${\mathcal {C}}_{2}$ mit dem Alphabet $\Sigma$, also im inneren Kreis und damit natürlich auch im äußeren. Abgeschlossenheit von ${\mathcal {C}}_{1}$ besagt, dass wir, ausgehend von einem L in ${\mathcal {C}}_{1}$, durch Komplementbildung nicht aus ${\mathcal {C}}_{1}$ hinauskommen, d.h. $\Sigma ^{*}\setminus L$ liegt dann auch in ${\mathcal {C}}_{1}$. Damit ist durchaus verträglich, dass $\Sigma ^{*}\setminus L$ für manche L aus ${\mathcal {C}}_{2}$ nicht in ${\mathcal {C}}_{2}$ liegt, es kann dieses Komplement zuweilen etwa im Ring zwischen innerem und äußerem Kreis liegen.

Beachte, dass hier gar keine Rolle spielt, um welche konkrete Art von Abgeschlossenheit es überhaupt geht. Wesentlich ist allein, dass Abgeschlossenheit eine Eigenschaft nicht von Sprachen, sondern von Sprachklassen ist. Wenn wir sie auf die enthaltenen Sprachen herunterbrechen, bedeutet Abgeschlossenheit einer Sprachklasse ${\mathcal {C}}$ bzgl. einer Operation O , dass gilt:

Wenn L in ${\mathcal {C}}$ liegt und Alphabet $\Sigma$ hat und

wenn ${\mathcal {C}}$ abgeschlossen gegenüber O ist

dann liegt $O(L)$ auch in ${\mathcal {C}}$

Diese Aussage für die enthaltenen Einzelsprachen ist relativ, d.h. sie hat noch einen weiteren Parameter in Gestalt der Sprachklasse ${\mathcal {C}}$. Nicht verwunderlich dann, dass sie ungültig werden kann, wenn man die Sprachklasse einfach austauscht, oder?

Nimm folgendes Beispiel.

Sei ${\mathcal {C}}_{1}$ = die Menge aller Verheirateten auf der Erde

Sei ${\mathcal {C}}_{2}$ = die Menge aller Verheirateten in Deutschland

Die Operation O, gegenüber der wir Abgeschlossenheit prüfen wollen, ordnet jedem seinen Ehepartner zu.

Dann ist ${\mathcal {C}}_{1}$ abgeschlossen gegenüber O – kein Mensch ist mit einem Marsmenschen verheiratet – aber ${\mathcal {C}}_{2}$ ist nicht abgeschlossen gegenüber O – manche Deutschen sind mit Franzosen verheiratet.

Abgeschlossenheit ist ein Eigenschaft der Schachtel, nicht der Dinge, die darin sind.

--Silvicola ^Disk 23:04, 27. Feb. 2014 (CET)

Danke für den Beitrag. Mir ist es später auch noch aufgefallen. (nicht signierter Beitrag von 84.57.201.192 (Diskussion) 10:26, 28. Feb. 2014 (CET))

Fehler in Übersicht bei TYP 0 ?

Im Abschnitt zu Typ 0 wird festgelegt, dass die linke Seite mindestens 1 Nichtterminal enthalten muss.
${\displaystyle }$

Unten in der Übersicht wird $\alpha$ (= linke Seite) von Typ 0 definiert als Element von:
${(\Sigma \cup N)}^{+}$ (was nach Definition im Absatz zu Typ 0 $V^{+}$ entspräche.)

Die Positive Hülle von ${(\Sigma \cup N)}$ kann ja gesehen werden als: ${(\Sigma \cup N)}^{1}\cup {(\Sigma \cup N)}^{2}\cup {(\Sigma \cup N)}^{3}\cup etc.$
mit ${(\Sigma \cup N)}^{i}:={(\Sigma \cup N)}^{i-1}o{(\Sigma \cup N)}$
wobei ${(\Sigma \cup N)}^{0}=\epsilon$

Daraus folgt, dass ${(\Sigma \cup N)}^{1}={(\Sigma \cup N)}^{0}o{(\Sigma \cup N)}=\epsilon o{(\Sigma \cup N)}={(\Sigma \cup N)}\subset {(\Sigma \cup N)}^{+}$
$\alpha$ kann also ein Element aus ${(\Sigma \cup N)}$ sein.

Damit kann alpha aber ein beliebiges einzelnes Terminal sein.
Über ${(\Sigma \cup N)}^{2}$ und ${(\Sigma \cup N)}^{3}$ etc. kann alpha dann eine beliebige Konkatenation aus Terminalen sein, die kein einziges Nichtterminal enthält, was der Definition im Abschnitt zu Typ 0 widerspricht. Die bisherige Definition von Alpha in der Übersicht sagt nur, dass die linke Seite nicht leer sein darf, nicht aber, dass sie mindestens ein Nichtterminal enthalten muss.

Oder sehe ich das falsch? (nicht signierter Beitrag von 93.215.46.132 (Diskussion) 15:51, 26. Apr. 2015 (CEST))

---

Van-Wijngaarden-Grammatiken

Kann man diese hier einordnen? -- Wegner8 (Diskussion) 08:36, 1. Dez. 2020 (CET)

Beispiele fehlen

Es fehlen Beispiele für Sprachen der jeweiligen Hierarchiestufen. (nicht signierter Beitrag von Diderot1770 (Diskussion | Beiträge) 08:17, 10. Mär. 2021 (CET))