Diskussion:Formale Grammatik

Wozu???

wozu dienen die definitionen von "formale Sprachen" und "Formale Grammatik"? meiner meinung nach ist das nur ne schöne mathematische spielerrei. aber sie hilft keinem ne gute sprache zu entwickeln. wenn ich mir die sprachentwicklung in der informatik anschaue, dann ist das ne stetige weiterentwichlung. da hat sich keiner mit solchen theorien beschäftigt. besonders wenn ich mir anschau das sie variablenbezeichnungen in gigantische längen mit berücksichtigt. mit bedienfreundlichkeit und übersicht hat das nix mehr zu tun. naja, soweit die worte eines nicht informatikstudentens, welcher sich schon seit 10 jahren mit dem programmieren beschäftigt, sich seit etlichen jahren nach einer vernünftigen sprache umschaut und sich dabei seine eigenen gedanken zum programmiersprache macht und dann ganz verdutzt solche artikel sieht. (der text sollte als kritische frage eines interesierten verstanden werden.)

-- SK-Genius 23:34, 25. Jun 2004 (CEST)

---

Ohne die Theorien über formale Grammatiken und Sprachen wären Compilerbau und viele verwandte Dinge, die sich mit dem inlesen und Parsen von Daten beschäftigen heute kaum noch vorstellbar. Beispielsweise hat ziemlich jede Compiler-Programmiersprache seit C davon profitiert. Abgeesehen davon ist die Beschreibung der Syntax einer Programmierspache heutzutage fast immer in Backus-Naur-Form gegeben und damit eine formale Grammatik. Natürlich kann man auch ohne davon Ahnung zu haben programmieren. Aber davon Ahnung zu haben kann beim Programmieren sehr helfen. --Coma 13:34, 26. Jun 2004 (CEST)

---

formale Grammatiken sind in der Theoretischen Informatik von entscheidender Bedeutung. Mit ihnen lassen sich zahlreiche theoretische Probleme lösen und beweisen. Welche Programmiersprachen praxistauglich sind könnte man ohne Theorie gar nicht prüfen. Natürlich sollte man mit formalen Grammatiken kein Betriebssystem programmieren wollen :-) Man stelle sich die Berechenbarkeitstheorie ohne Grammatiken vor! Stern 23:42, 25. Jun 2004 (CEST)

---

das ne programmiersprache ne eindeitige grammitik haben sollte ist mir auch klar. ich versteh nur nicht wozu die mengenformulierungen auf den zwei besagten seiten gut sein soll. bisher hab ich auch noch nicht den sinn von theoretischer informatik verstanden. die meisten eintwicklungen sind aus dem hobbybereich entstanden. das schliest die betriebssysteme mit ein. die einzigen ausnahmen die mir dazu einfallen sind die grossen simulationsrechnernetzwerke.

was sich sehr interesant anhört ist, dass man damit die praxistauglichkeit einer sprache überprüfen kann. wo kann ich mich zu dem thema näher informieren?

ps: bei der überprüfung von c++ müsste doch eindeitig rauskommen das sie nicht praxistauglich ist? ;-)

-- SK-Genius 14:05, 26. Jun 2004 (CEST)

---

hab mir jetzt den artilel Ackermannfunktion (zum teil) durchgelesen, und hab jetzt zumindest den sinn von der theoretischen informatik (genauer: den sinn von der berechenbarkeits theorie) verstanden. aber der nutzen der mengenbeschreib der zwei genannten seiten bleibt mir immernoch verborgen.

-- SK-Genius 14:34, 26. Jun 2004 (CEST)

---

Das bleibt beim besten Anfangs auch einem Studenten verborgen ^^ Aber jetzt ernsthaft: Hier wird eine theoretische Grundlage für all die Programmierei geschaffen. Programmieren ist aus der Informatik heraus entstanden. Das Prinzip der Informatik ist die thematische, systematische Grundlage für all die Prozeduren da draußen zu schaffen. Dahinter verbirgt sich, wie das auch schon meine Vorredner gesagt haben, formale Probleme zu lösen und rien theoretische Problemstellungen zu beweisen. Solche Beweise sind oft die Grundlage für ganz große Neuerungen in der Praxis. Zudem lassen sich die meisten Dinge in der Programmierung durch theoretische Herangehensweise optimieren. Formale Sprachen sind eine solche Herangehensweise. Man versucht dabei das Thema möglichst abstrakt und genau zu identifizieren um damit mathematisch umgehen zu können. Was wir davon haben sind die Grundlagen komplexe Systeme, die am Ende für jedermann handhabbar und zuverlässig sind, weil sie bewiesen wurden ; ) Thilo --78.48.226.141 13:27, 22. Nov. 2007 (CET)

Ersetzungsregeln

Hab mir gerade mal den Artikel durchgelesen. Dabei bin ich der Meinung, dass gleich das erste Beispiel falsch ist, müßten die Regeln nicht wie folgt angewendet werden? C -> Bcc -> Abcc -> abcc Wie zu dieser Auffassung komme? Ich glaube mich aus meinem Studium zu entsinnen, dass die erste zutreffende Regel benutzt werden muß. Also nicht von Abcc mittels der 2. Regel nach Aabcc, sondern halt mittels der 1. Regel nach abcc. Wenn ich's mir Recht überlege, kann die 2. Regel jedoch auch gestrichen werden. :? Ich werd mal meine Unterlagen rauskramen ... Wie kommt das Beispiel eigentl. auf das Ergebniss aaaaabcc? Dies würde für mich bedeuten, das ich mir die entsprechende Ersetzungsregel aussuchen kann. *kopfschüttel* --Kleinvieh macht auch Mist 15:26, 28. Nov 2005 (CET)

Was man auch, wie bei der gewöhnlichen Grammatik, kann. Ein Zwang zur ersten Regel gibt es nicht. Siehe später auch die Definition: Eine(r) endlichen Menge P von Produktionsregeln. Mengen sind per definitionem ungeordnet. --Hubi 18:51, 28. Nov 2005 (CET)

Ableitbarkeit

Es fehlt noch ein Abschnitt über Ableitbarkeit, einschließlich der Symbolik für "A ist aus B ableitbar" und "A ist aus B direkt ableitbar" und "A ist aus B in n Schritten ableitbar" Richardigel 18:01, 27. Apr 2006 (CEST)

Ich habe jetzt noch ein bisschen bei der Definition ergänzt und mehr zur Ableitung geschrieben. Den Satz mit der "eingebürgerten Schreibweise" hab ich rausgenommen, so schreibt man doch eigentlich nur Regeln. Was meinst du mit "A ist aus B in n Schritten ableitbar"? Ich kenne da keine weitere Symbolik... Etwa das $T_{m}^{n}$ aus dem Beweis für das Wortproblem von Typ-1-Sprachen? Das denke ich gehört hier nicht dazu. --Samx 16:21, 29. Jul 2006 (CEST)

Ich denke er meint $\to ^{n}$ für "in n Schritten ableitbar" und $\to ^{*}$ für "überhaupt ableitbar" $\to$ wird für "direkt ableitbar" benutzt, oder? Ich werde demnächst mal was dazu schreiben.

Formale Definition

Die formale Definition der Regelmenge ist m. E. nicht korrekt.

Mit $P\subseteq \left(N\cup \Sigma \right)^{+}$ wird zwar erzwungen, dass mindestens ein Symbol aus $N$ oder $\Sigma$ enthalten sein muss (also $\epsilon$ nicht erlaubt ist), aber es muss noch gewährleistet sein, dass mindestens ein Symbol aus $N$ vorkommt.

Ein Beispiel: Mit $a\in \Sigma$ gilt auch $a\in \left(N\cup \Sigma \right)^{+}$ und dies wäre nicht zulässig.

Richtig wäre die Definition so: $P\subseteq \left(\left(N\cup \Sigma \right)^{*}\backslash \Sigma ^{*}\right)\times \left(N\cup \Sigma \right)^{*}$

Marko

Hallo,

ich denke du hast recht. Es MUSS gewährleistet seint dass mindestens ein Symbol aus $N$ vorkommt. Ich würde folgende Schreibweise vorschlagen: $P\subseteq \left(\left(N\cup \Sigma \right)^{*}N(N\cup \Sigma \right)^{*})\times \left(N\cup \Sigma \right)^{*}$

Schönen Gruß

Andreas

--Andreas.husch 10:00, 11. Okt. 2007 (CEST)

Ich studiere momentan Informatik und muss mich daher mit der Theoretischen Informatik befassen. Grundsätzlich muss auf der linken Seite kein Nichtterminal vorkommen, das heisst die alte Schreibweise war korrekt. Zum Vergleich hierzu kann man im Artikel Chomsky-Hierarchie nachlesen, dass bei einem Grammatik des Typs 0 nicht zwingend ein Nichtterminal auf der linken Seite vorkommen muss. Dementsprechend müsste dann auch der Artikel geändert werden und zwar in der formalen Definition. Lars

Hallo,

ich studiere ebenfalls Informatik und habe auch schon einiges mit der Theoretischen Informatik zu tun gehabt. Bezüglich Typ 0 Grammatiken und der Frage, ob links mindestens 1 Nonterminal stehen muss, habe ich sowohl im Internet, also auch in Büchern als auch von Professoren widersprüchliche Antworten erhalten, also die einen bestehen darauf und die anderen nicht. Ich finde, wir sollten uns einmal mit der Frage befassen, ob es für die Mächtigkeit der Typ 0 Sprachen überhaupt einen Unterschied macht, ob ein Nonterminal vorhanden ist oder nicht, denn wenn es keinen Unterschied machtn, ist es soweit ich weiß auch unerheblich, wie genau Typ 0 definiert wird. Meiner Meinung nach macht es keinen Unterschied, ob ein Nonterminal vorhanden ist oder nicht. Man nehme z.B. folgende Regel:

abc --> def

Hängt man links ein Nonterminal an, wird daraus z.B.:

Xabc --> def oder aXbc --> def oder abcX --> def

und das ist definitiv Typ 0, egal nach welcher Definition. Ich denke, dass man bei allen Regeln, die links kein Nonterminal haben, einfach irgendwo eins reinpacken kann, also ist es unerheblich, ob bei Typ 0 links ein Nonterminal vorkommt oder nicht.

Dann noch zwei Punkte zum Beispiel einer Typ 1 Grammatik: Die Regel BS --> b ist nicht Typ 1, da für alle Regeln u-->v gelten muss: |u| <= |v|

Die Regel BA --> AB sehe ich persönlich zwar als Typ 1 tauglich an, nicht aber die Definition auf http://de.wikipedia.org/wiki/Chomsky-Hierarchie Die Definition dort versieht Typ 1 nämlich mit einer weiteren Einschränkung, nämlich dass aAb --> ayb gelten muss und A ein einzelnes Nonterminal sein muss. Somit wird gefordert, dass genau 1 Nonterminal pro Regel ersetzt wird und der Kontext dieses Nonterminals erhalten bleibt. Ich persönlich habe mit dieser Einschränkung folgende Schwierigkeit:

Die Sprache L(G) = a^n b^n c^n wird allgemein als kontextsensitiv betrachtet, nur die Lösungen, wie man diese Sprache erzeugt, waren laut der o.g. Einschränkung alle Typ 0 weil sie immer Regeln enthielten, die wie "AB --> BA" nur dazu da waren, 2 Buchstaben zu tauschen, was ja nach Wikipedia nicht Typ 1 konform ist. Kann jemand diese Sprache mit einer Wiki-konformen Typ 1 Grammatik erzeugen?

Grüße, Alex (Squall83)

Zum Thema: Muss ein links ein Nichtterminal vorkommen? Ich muss hier meinen Vorredner korrigieren, gebe ihm aber auch gleichzeitig recht... :) Links ein Nichtterminal zu fordern schadet zwar nichts , ist aber auch nicht zwingend notwendig. Einziger Unterschied ist, dass im ersten Fall eine Ableitung eindeutig beendet ist, wenn keine Nichtterminale mehr vorkommen. Wenn man das möchte... Andersherum kann man (wie bei der Umwandlung einer beliebigen CFL-Grammatik in CNF) für jedes Terminal $a$ eine Variable $A$ und die Produktion $A\to a$ einführen sowie auf rechten und linken Seiten von anderen Produktionen $a$ durch $A$ ersetzen. Dann wird z.B. $abc\to def$ zu $ABC\to DEF$ und alle sind glücklich. Das mit dem zusätzlichen Nichtterminal ist aber nicht so einfach umsetzbar, dann müsste man erstmal klären wie man X erzeugt...

Gruß Micha (nicht signierter Beitrag von 37.120.17.245 (Diskussion) 20:42, 2. Feb. 2015 (CET))

Fehler/Ungenauigkeiten

abschnitt definition, punkt zwei (mit dem $\Sigma$). wenn ich das richtig sehe, müsste in der zeile $T$ jedesmal gegen $\Sigma$ ausgetauscht werden. genaugenommen scheint sich das durch artikel hindurchzuziehen -- jedenfalls wird das $T$ nirgendwo eingeführt.

$\exists u,v\in (N\cup T)^{\ast }:\;\exists (R,Q)\in P:\;(w=u\circ P\circ v)\land (w^{\prime }=u\circ Q\circ v)$: da steht plötzlich ein klotz im raum, für den weder alle symbole erklärt sind noch erläutert wird, was das heisst bzw wie das zu lesen ist

auch wird nicht erklärt, wo das $\mathbb {N}$ auf einmal herkommt und was es bedeutet, auch im abschnitt beispiel taucht dieses $\mathbb {N}$ wieder auf, ebenso das $\varepsilon$, das auch nicht erklärt wird. (Der vorstehende, nicht signierte Beitrag stammt von 78.54.6.9 (Diskussion • Beiträge) 22:57, 26. Apr. 2008 --Stephan Kulla 14:17, 1. Mai 2008 (CEST))

Habe den Artikel dementsprechend geändert. Wie richtig erkannt wurde, musste nur $\Sigma$ durch $T$ ersetzt werden. $\varepsilon$ ist im übrigen das Symbol für das leere Wort und $\mathbb {N} _{0}$ meint die Menge der natürlichen Zahlen einschließlich der Null (welche imho nicht extra im Artikel erwähnt werden sollte).--Stephan Kulla 14:31, 1. Mai 2008 (CEST)

Satzform

ein aus Terminale und Nichtterminale bestehendes Wort sowas ist kein Wort (bzw. Satz der Sprache), sondern eine Satzform. Satzformen werden normalerweise klein griechisch bezeichnet. Mit Satzform kann man viel eleganter erklären, was passiert. Sollte nach Terminalsymbole kurz erklärt werden, dann kann man Produktionsregel auch einfach erklären als Satzform1 --> Satzform2, wobei Satzform1 1 Nonterminal enthalten muß. (nicht signierter Beitrag von 217.83.5.166 (Diskussion | Beiträge) 11:42, 4. Feb. 2010 (CET))

Es ist allerdings kein Wort der von der Grammatik erzeugten Sprache, aber ein Wort über dem Alphabet der Terminale und Nichtterminale ist es schon. Um eine Satzform zu sein, müsste es vom Startsymbol abgeleitet werden können -- daher ja die Bezeichnung "Satzform". -- UKoch 18:28, 4. Feb. 2011 (CET)

Ein Beleg wäre ganz schön, dann könnte man das mit der Satzform einbauen. Ansonsten gibt es die "konkurrierende" Definition, wie der Artikel und UKoch sie beschreiben, dass Wörter Folgen von Zeichen sind. Ob die Zeichen nun Terminale oder Nichtterminale sind, ist abstrakt gesehen egal. Was Terminale sind, hängt von einer Grammatik ab, und gilt außerhalb einer Grammatik nicht (aber Sprachen lassen sich auch außerhalb einer formalen Grammatik betrachten). --Zahnradzacken 20:14, 4. Feb. 2011 (CET)

Ein Beleg für die obige Def. der Satzform findet sich z.B. hier (S. 86): John E. Hopcroft und Jeffrey D. Ullman. Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Addison-Wesley, 1. Nachdruck der 3. Auflage, 1996. -- UKoch 14:06, 14. Feb. 2011 (CET)

Wunderbar, danke. --Zahnradzacken 14:45, 14. Feb. 2011 (CET)

Ich wollte es gerade einbauen, da stolperte ich über die Definition von Satzform in Schönings "Theoretische Informatik – kurzgefasst", dort sind es formal Wörter aus $(N\cup T)^{*}$. A und B halten sich auch an Schöning, wobei B in einer Fußnote die alternative Definition erwähnt. C und D fordern wie Hopcroft&Ullman die Ableitbarkeit aus S. Vielleicht sollte das besser im Artikel Ableitung (Informatik) erläutert werden, wo es schon einen Abschnitt zur Satzform gibt, und hier das Wort besser weiterhin gemieden werden(?) --Zahnradzacken 23:47, 14. Feb. 2011 (CET)

Hm, die Def., in der Ableitbarkeit aus S nicht gefordert wird, kannte ich nicht. Ich denke auch, dass man dann hier auf den Begriff "Satzform" verzichten sollte. -- UKoch 13:18, 15. Feb. 2011 (CET)

Beispiel falsch

Das Beispiel ist falsch:

BA -> AB

ist keine kontextsensitive Regel, also ist die Grammatik nicht kontextsensitiv (was aber behauptet wird), man kann die Regel aber gegen 3 kontextsensivtive Regeln austauschen:

BA -> BT BT -> AT AT -> AB (nicht signierter Beitrag von 141.35.12.168 (Diskussion) 14:09, 14. Jul 2010 (CEST))

Ach herrje, an wievielen weiteren Stellen befinden sich noch diese Überbleibsel ...

Also: Manche Autoren nennen solche Grammatiken wie oben durchaus kontextsensitiv, aber strenger betrachtet sollte man sie als monotone Grammatiken bezeichnen. Es ist der Lesbarkeit halber wahrscheinlich besser, nicht die Grammatik, sondern die Beschreibung zu ändern. --Zahnradzacken 15:30, 14. Jul. 2010 (CEST)

Allerdings ist die Grammatik bisher auch nicht monton, weil $(S,\varepsilon )$ in der Regelmenge ist und gleichzeitig $S$ auf der rechten Seite einer Regel vorkommt. Die Grammatik muss sich also so oder so ändern, der Aufwand ist aber geringer, sie monoton zu machen. --Zahnradzacken 15:34, 14. Jul. 2010 (CEST)

Kosmetik

In Bezug auf den Kommentar: „Angabezwang von S bewirkt bereits echte Teilmengeneigenschaft“

Bei aller Richtigkeit der kosmetischen Korrekturen bitte ich darum, darauf zu achten, nicht zu viel der Wahrheit implizit zu kodieren. Ich sehe es nicht als Problem, wenn man manche folgerichtigen Sachverhalte ausformuliert, um sie zu verdeutlichen. --Zahnradzacken 20:59, 21. Jul. 2010 (CEST)

Ich bin mir der Gefahr von zu viel Implizitheit bewusst. Im konkreten Fall bin ich der Meinung, dass es die Lesbarkeit und Verständlichkeit eher verbessert, weil sich der Leser nicht fragen muss, warum das nun eigentlich erwähnt wurde, und sich ggf. erinnern muss, was "echte Teilmenge" heißt. Des weiteren denke ich auch: Erklärungen gehören nicht inline in Definitionen hinein. Das erschwert, zu erkennen, was überhaupt definiert wurde. Ausformulierungen und Beleuchtung der Konsequenzen gehören woanders hin.

Wie dem auch sei. Das hier ist ein Wiki, nicht wahr? :) --Daniel5Ko 21:26, 21. Jul. 2010 (CEST)

@Wiki: Ja klar, aber wer will schon einen Edit-War wegen hier und dort ein paar Symbolen anfangen? ;) Letztlich finde ich das in diesem Fall ja auch nachvollziehbar und alle vorherigen Änderungen ebenso. Ich sah nur eine Tendenz – und jeder hat womöglich andere Grenzen.

@Inline-Erklärungen: Es sieht natürlich sauberer aus, wenn man es trennt. Aber je weiter man es trennt, desto mehr lässt man den Laien allein. Und nicht immer bietet es sich an, die Erklärung der Notation voranzustellen. --Zahnradzacken 23:00, 21. Jul. 2010 (CEST)

Jo, wie gesagt, einfach mal das Wiki als solchen benutzen, und Feedback (in Form von Edits oder Diskussionen) abwarten. Ich werde demnächst auch erstmal keine weiteren Änderungen vornehmen, außer vielleicht ganz triviale. Mal schauen, was 'rauskommt. --Daniel5Ko 23:28, 21. Jul. 2010 (CEST)

Ach schade, die Beispiele könnten nämlich mal überarbeitet werden ;) .. Was sagst du? Wiki? Da kann sich jeder beteiligen? Erwischt. --Zahnradzacken 23:45, 21. Jul. 2010 (CEST)

Hau ab! :D --Daniel5Ko 23:53, 21. Jul. 2010 (CEST)

Ach, egal. Nachher nimmt noch jemand diesen Thread (bzw. den untersten Teil davon) ernst. Let's stop it right here. --Daniel5Ko 00:10, 22. Jul. 2010 (CEST)

Frage

• $V\setminus \Sigma =N$
• $V^{*}\setminus \Sigma ^{*}=N^{*}$?

--Abdull 17:11, 27. Aug. 2010 (CEST)

Nein. Nimm $V=\{S,a\},\Sigma =\{a\}$, dann ist $N^{*}=(V\setminus \Sigma )^{*}=\{S\}^{*}$, $V^{*}\setminus \Sigma ^{*}$ enthält aber z.B. "SSaSa". Was es nicht enthält, sind Worte, die nur aus Terminalen bestehen. "aaa" hier zum Beispiel. (PS: Ich hab' mir mal erlaubt, die Überschrift "Frage" hinzuzufügen.) --Daniel5Ko 22:17, 27. Aug. 2010 (CEST)

Kleensche Hülle

Könnte vielleicht irgendwo darauf verwiesen werden, dass V* die kleensche Hülle von V ist, bzw. ein Link zur kleenschen Hülle eingefügt werden? Ich kannte die Schreibweise noch nicht (weil ich auch keine kleensche Hülle kannte). Ich hatte V* bzw. $\Sigma *$ beim ersten Lesen einfach für neue Namen gehalten, etwa als Teilmengen von V respektive $\Sigma$. Ich weiß aber auch nicht wie man das am besten verlinkt o.Ä., und ändere auch nichts, ich meckere lieber bloß ein bisschen rum :) --84.135.81.4 19:42, 10. Nov. 2010 (CET)

Ein in diesem Themengebiet sehr grundlegender und überall benutzter Begriff (mitsamt der Notation mit *). Soll man den wirklich überall künstlich erwähnen und verlinken? Man erklärt ja auch nicht andauernd $\in ,\subset ,\setminus ,\cap ,\times ,+$ etc. Der vorliegende Artikel hat Links zu formale Sprache (in der Einleitung) und Alphabet (Informatik) (in der Nähe der ersten Verwendung von *) . Beide erwähnen und verlinken die Kleenesche Hülle. Reicht das nicht?

(Habe trotzdem mal behelfsmäßig eine Erwähnung eingefügt.) --Daniel5Ko 22:46, 10. Nov. 2010 (CET)

Es ist schon eine komfortable Auflockerung, wenn die kompakte Definition auch nochmal erklärt wird (also nicht nur umschrieben, sondern etwa Zeichen für Zeichen). Dabei die richtige Balance zu finden, ist schwer, denn welcher Uneingeweihte klickt schon auf den blauen Link "Alphabet", wo doch jeder weiß, was ein Alphabet ist? Entsprechend ist nicht jedem klar, was eine Produktionsregel ist, und gerade deshalb die Notation mit dem * möglicherweise unbekannt. Das Defizit im Falle der Kleeneschen Hülle könnte hier auch darin liegen, dass der Artikel zu Produktionsregeln nicht nur unsauber ist, sondern selbst nicht auf die Kleenesche Hülle zu sprechen kommt (nicht mal symbolisch). Insofern kann man derzeit nicht unbedingt verlangen, dass man sich überall durchklickt, nur um zu hoffen, dass in einem Zielartikel irgendwo das Entsprechende erklärt oder wiederum verlinkt ist. Konsequenz: Ich habe ein paar Eingriffe bei Produktionsregel gemacht, hier bei Bedarf später. --Zahnradzacken 00:39, 11. Nov. 2010 (CET)

Ja, das war wahrscheinlich eine gute Änderung in Produktionsregel, allerdings wird dort nun vieles von hier wiederholt, um den Kontext herzustellen (genau genommen war das vorher auch schon so, es ist jetzt lediglich deutlicher sichtbar). Man könnte meinen, sinnvoller wäre ein Abschnitt namens Produktionsregel(n) hier. Alles nicht so einfach. Was meinst du? --Daniel5Ko 22:45, 11. Nov. 2010 (CET)

Verzeih, ich habe deine Antwort übersehen.

Generell habe ich nichts gegen Wiederholungen, denn man kann (und mMn sollte) nicht annehmen, dass die Artikel zu einem Thema in der richtigen Reihenfolge gelesen werden. Das setzt ja bereits Kenntnis über das Themengebiet voraus. Hier ist ja genug Platz für Redundanz, solange deren Pflegeleichtigkeit sich im Rahmen hält. Wenn aber der ausgelagerte Artikel selbst nicht mehr enthält, als die Erläuterung im Hauptartikel, dann ist das nicht optimal. Dem steht wiederum mein Empfinden entgegen, dass mir Redirects auf Unterkapitel nicht gut gefallen und ein Artikel zu etablierten Begriffen ja schon nützlich ist. Lange Rede, kurzer Sinn: Produktionsregel könnte aufpoliert werden, damit der Artikel seine Eigenständigkeit rechtfertigt. Den Abschnitt Produktionsregeln gibt es hier ja schon, den könnte man dann bezüglich der Formeln etwas entschlacken. --Zahnradzacken 20:21, 16. Nov. 2010 (CET)

Ich finde Redirects auf Unterkapitel auch oft befremdlich. Aber vielleicht ist das der falsche Lese-Ansatz.

Nur zum drüber-Nachdenken: Stell' dir vor, wir würden deinen Vorschlag der Entschlackung in extremem Maße umsetzen. Dann wäre Produktionsregeln hier praktisch nur ein Link auf Produktionsregel, und der Leser müsste dort alles erneut (geeignet über-) lesen. Ich rate einfach mal: Es existiert bestimmt eine gute, redundanzarme Lösung. Wir müssen die nur finden. :) --Daniel5Ko 00:33, 17. Nov. 2010 (CET)

Da ich das Entschlacken durch das Wort 'etwas' nach oben beschränkt habe, wäre eine extreme Umsetzung nicht sehr radikal :) Ich finde den Glauben an genau eine Lösung optimistisch. Dazu bräuchten wir vielleicht erstmal eine klarere Idee davon, was in den Artikeln stehen soll. Zum Beispiel könnte man in beiden Artikeln in gleichem oder verschiedenem Umfang den Zusammenhang zur Chomsky-Hierarchie ausformulieren. 1. Hier zum Beispiel allgemein ein kurzer Überblick, bei Produktionsregel dagegen der Bezug, dass die Einordnung zu den Ebenen anhand der Art der Produktionsregeln entschieden wird. Dort könnte man sich außerdem noch darüber auslassen, dass man die Regeln auch als Ableitungsrelation bezeichnen kann (und das mit liebevollen Worten erklären). 2. Hier könnte man dagegen noch Bezüge zu anderen formalen Grammatiken herstellen (Baumgrammatiken, Attributgrammatiken) und den Unterschied zu STS und Termerersetzungssystemen darstellen. Kennst du dich da ausreichend aus?

3. Achso eigentlich ging es ja nur um Produktionsregeln: Die Definition im Abschnitt Definition würde ja definitiv bleiben. Was spräche dagegen, im Abschnitt Produktionsregeln diese weniger formellastig zu erklären? Prämisse und Konklusion finden hier sonst keine Anwendung. Das könnte dann rüber. --Zahnradzacken 12:17, 17. Nov. 2010 (CET)

(Ich habe die Nummern vor die Abschnitte gesetzt, auf die ich hier nun eingehe)

1. Diese Vorschläge klingen erstmal genau richtig.
2. Klingt auch gut. Ich würde sagen, ich kenne mich ausreichend aus.
3. Es spricht nichts dagegen, weniger Formeln zu verwenden. Ich find' die, die da stehen, sowieso ein wenig sinnlos. "Prämisse" und "Konklusion" kann von mir aus auch ganz 'raus. Diese Bezeichnungen habe ich hier zum ersten mal gesehen (im Zusammenhang mit Produktionsregeln) und finde sie unpassend.

--Daniel5Ko 20:40, 17. Nov. 2010 (CET)

Danke für die Nummern :)

1. Dann werde ich das bei nächster Gelegenheit umsetzen.
2. Dann überlasse ich diesen Teil dir :)
3. Ja, die Begriffe finde ich hier auch deplatziert. Ich bin dann für ersatzloses Streichen. Wenn ich mich dann dran mache.

--Zahnradzacken 00:31, 18. Nov. 2010 (CET)

Alles klar. Machen wir so. Ich hab' zwar noch keinen guten Plan für 2., aber der kommt bestimmt bald... --Daniel5Ko 18:23, 20. Nov. 2010 (CET)

Ein erster Schritt ist getan. Habe entsprechend hier durchgestrichen. --Zahnradzacken 00:41, 24. Nov. 2010 (CET)

Definitionen doppelt

Der Artikel Chomsky-Hierarchie, der von diesem Artikel ja verlinkt wird, erklärt nochmal, was eine kontextfreie etc. Grammatik ist. Diese Definitionen sind darum hier m.E. überflüssig. Ich bin für Streichen. -- UKoch 18:25, 4. Feb. 2011 (CET)

Hättest du den Abschnitt eins weiter oben gelesen, hättest du festgestellt, dass dies genau erwünscht ist. Überflüssig müsstest du erstmal begründen. CFGs werden auch in einem eigenen Artikel erklärt, aber man muss nicht deswegen jede Erklärung andernorts löschen. Wer die Materie nicht kennt, braucht eine Einordnung. Zusammenfassungen anderer Artikel im richtigen Kontext sind keine Redundanz.

Danke für deine Korrekturen, auch an anderen Stellen. Aber Richtiges durch Richtiges ("sodass" → "so dass") sind etwas irritierend. Änderungen "Zur Erzeugung einer Sprache" zu "Zur Erzeugung einer gegebenen formalen Sprache" finde ich noch irritierender. Wieso gegeben? --Zahnradzacken 20:32, 4. Feb. 2011 (CET)

Wo genau die Grenze zwischen "hilfreich" und "überflüssig" liegt, darüber gibt's natürlich verschiedene Meinungen. Ich finde die Erklärungen von CFGs etc. hier zwar unnötig (und so kurz, dass sie missverständlich sind), aber lassen wir sie halt drin.

Mir war nicht klar, dass "sodass" jetzt auch geht, also keine böse Absicht. Und "gegeben" macht's hier klarer. Das Problem im Allgemeinen: Beim unbestimmten Artikel ist meist unklar, wie groß sein Skopus (als Quantor) ist. "Zur Erzeugung einer Sprache gibt es unendlich viele Grammatiken" könnte also heißen: "Es gibt unendlich viele Grammatiken, und jede erzeugt eine Sprache." Mit "gegeben" wird klar, dass es für jede formale Sprache unendlich viele erzeugende Grammatiken gibt. Und "formal" ist hier nötig (wird zumindest von Priese so verwendet); siehe Nachsatz: Es gibt Sprachen, die von keiner Grammatik erzeugt werden. -- UKoch 12:41, 7. Feb. 2011 (CET)

Deine konträre Meinung kannst du ja gerne hier oder im vorangehenden Abschnitt erläutern. Aber auch, wenn sich deine Meinung nicht durchsetzen sollte, wäre ich über deine Kritik dankbar. Also, warum sind die Erläuterungen wegen ihrer Kürze missverständlich?

Das ergänzte Wort gegeben war das einzige, das mich störte. Liest man den Satz mathematisch unbelastet, erkennt man nicht den Zweck als Quantor, sondern könnte meinen, es müsse erst die Sprache gegeben sein, um dazu unendlich viele Grammatiken zu finden. Aber die Beziehung besteht auch, ohne dass man eine einzelne Grammatik betrachtet. Vielleicht liest sich das hier besser? "Es gibt immer mehrere Grammatiken (und zwar...), die dieselbe Sprache erzeugen."

Hier präzise von formalen Sprachen zu sprechen, ist gut. Aber die Unterscheidung von Erk/Priese machen andere nicht: Für Hopcroft/Ullman ist eine (formale) Sprache eine Menge von Strings über einem gegebenen Alphabet. Die Typ-0-Grammatiken (und damit meines Wissens die formalen Grammatiken prinzipiell) erzeugen konkret die rekursiv aufzählbaren Sprachen. Egal nach welcher Definition man geht, in beiden Fällen wäre ein Beispiel schön, um die Existenzaussage zu begründen. Wüsstest du eines?

Deine Kritik aus Diskussion:Produktionsregel muss man nicht unterschlagen. Hast du dort resigniert oder zugestimmt? --Zahnradzacken 17:42, 7. Feb. 2011 (CET)

Bei CSGs finde ich es verwirrend, dass zuerst nur von genau einen Nichtterminal die Rede ist, dann aber ein Kontext erwähnt wird, und der nur auf der linken Seite der Regel. Eine Erklärung à la "Jede Regel muss die Form alpha A beta -> alpha gamma beta haben" fände ich besser; danach kann man ja erklären, dass alpha ... beta hier als Kontext gesehen werden können. "Reguläre Grammatiken" kenne ich als rechtslineare Grammatiken, und zumindest Erk/Priese verbieten dabei Kettenregeln, was bei der aktuellen Formulierung "bestehen die rechten Seiten der Regeln aus höchstens einem Terminalsymbol, dem höchstens ein Nichtterminalsymbol folgen darf" nicht klar wird.

"Es gibt immer ..." finde ich schon OK. Mir fiel noch ein: "Jede formale Sprache wird von mehreren (und zwar abzählbar unendlich vielen) Grammatiken erzeugt." Änder's doch in eine der beiden Fornulierungen.

OK, dann könnte man überall von rek. aufz. Sprachen sprechen statt von Formalen. -- Meinst du ein Bsp. für eine Sprache, die von keiner Grammatik erzeugt wird? Das dürfte schwer werden. Erk/Priese beweisen die Existenz so: Jede Grammatik ist selbst ein Wort aus einer Sprache, also gibt es nur abzählbar viele Grammatiken. Aber es gibt überabzählbar viele Sprachen.

Eher resigniert; eine Quelle wäre mir lieber. Aber bis jetzt hat sich ja niemand gemeldet, der eine hat. -- UKoch 19:26, 8. Feb. 2011 (CET)

Hallo.

Zu CSGs: Dass "genau ein Nichtterminalsymbol durch eine Zeichenfolge ersetzt wird" heißt ja nicht, dass genau ein NTS auf der linken Seite einer Regel steht. Die anderen dürfen aber nicht ersetzt werden. Eigentlich finde ich es schön, dass der Abschnitt ohne Formeln auskommt. Vielleicht können wir eher den jetzigen Satz verbessern?

Reguläre Grammatiken werden u.a. von Hopcroft/Ullman so genannt; rechts- bzw links-lineare Grammatiken sind dasselbe. In der Umschreibung habe ich mich nun auf die linkslinearen Grammatiken eingeschränkt, weil ich nicht unbedingt die Äquivalenz verschiedener Grammatik-Klassen thematisieren wollte. Könnte man aber ergänzen.

Warum sollte man überall von rek.aufz. Sprachen sprechen, wenn die Formulierungen so auch für formale Sprachen zutreffen? – Ich meinte ein Beispiel für beide Interpretationen.

Resignation ist nicht gut, nach nur einem Widerspruch :) Es tut der Qualität sicher gut, wenn du nicht so schnell locker lässt. --Zahnradzacken 20:18, 8. Feb. 2011 (CET)

Hab' erstmal Artikel und Disk. nur überflogen. Bisher kann ich folgendes sagen:

1. Ich teile UKochs Bedenken bzgl. einer eingedampften Version von Chomsky-Hierarchie hier. Richtig gut verständlich wird das ganze ja nur, wenn die ultra-kurz-Zusammenfassungen ihrerseits auch in einen Kontext eingebunden sind, was sie dann wieder länger macht... Trotzdem ist die gegenwärtige Version erstaunlich gut. Hätte nicht gedacht, dass das geht. Das liegt wohl daran, dass lediglich auf die Formen der Regeln eingegangen wird (ob die wirklich gut und richtig angegeben sind, prüfe ich aber noch). Aber wolltest du diese Betrachtung nicht in Produktionsregel unterbringen?
2. Bzgl. Formeln: Finde ich meistens leichter les- und schreibbar. Und wenn es um Klarheit geht, sind sie eigentlich unschlagbar. Nicht umsonst wird Mathematik seit einigen hundert Jahren nicht mehr auf arabisch, oder deutsch oder latein etc. betrieben. Gerade deswegen ist es natürlich ein gutes Zeichen, wenn man nicht auf klarheitschaffende Formeln angewiesen ist. Ob letzteres tatsächlich erreicht ist, checke ich auch mal ganz genau. :)

--Daniel5Ko 21:59, 8. Feb. 2011 (CET)

1. Es wäre nützlich, die zwei Fragen getrennt zu diskutieren: 1. Chomsky-Hierarchie hier anreißen, ja/nein? 2. Wenn ja, dann wie? Dass Punkt 1 davon abhängt, dass es gut und nicht falsch sein darf, ist klar.
2. Du magst Formeln leichter finden, aber du brauchst auch den Artikel nicht ;) Wer den Artikel liest, nicht um ihn zu verbessern, sondern selbst etwas zu lernen, ist vielleicht (noch) nicht gut im Lesen von Formeln. Unter der Annahme, dass die Erwähnung der Chomsky-Hierarchie hier für Einsteiger eine Einordnung liefert, ist der Verzicht auf Formeln eine für mich sinnvolle Entscheidung. --Zahnradzacken 23:56, 8. Feb. 2011 (CET)

1. 1. Ja, doch, kann man schon machen. Die englischsprachigen Kollegen haben sich ja scheinbar auch dazu entschlossen.
   2. Es ist wahrscheinlich in der jetzigen Form genau richtig: Auf die Regelformen beschränkte Kurzzusammenfassung.
2. Oh, ich sehe gerade, in Chomsky-Hierarchie gibt es gewissermaßen eine Version dieses Abschnittes hier, nur eben mit Formeln. Hatte ich ganz vergessen. Insofern fehlt soetwas nicht, und muss hier natürlich nicht wiederholt werden.

Im Ergebnis: Scheinbar alles gut, wie's jetzt ist. --Daniel5Ko 19:15, 9. Feb. 2011 (CET)

Ich ändere in dem einen Satz "formal" in "rek. aufz." und nehme das "gegeben" 'raus. -- UKoch 13:18, 15. Feb. 2011 (CET)

Nicht generisch genug abgegrenzt

Formales muss nicht zwingend auf Mathe hindeuten, auch wenn eine Üblichkeit in der Beziehung erkennbar ist. Die Einleitung des Artikels sollte also nicht gleich auf Mathematischen Formalismus und, im nächsten Sprung, nach Chomsky hüpfen. Chomsky wäre der nächste Aufhängepunkt, da auch zu ihm eine übliche Beziehung in der Informatik vorherrscht, dies aber nicht zwingend und vielleicht auch einer der größten Fehler in der Informatik ist (Reduktionismus, Pragmatismus etc. als ideologische Hirnverkalker.) (nicht signierter Beitrag von 2A02:8108:81C0:540:A534:F4FF:BC4B:EAF2 (Diskussion | Beiträge) 04:34, 21. Jul 2014 (CEST))

Defekter Weblink

Dieser Baustein verhindert die automatische Archivierung dieses Abschnitts und seiner Unterabschnitte.

Der folgende Weblink wurde von einem Bot („GiftBot“) als nicht erreichbar erkannt.
Ausführliche Erläuterungen und Hilfe zur korrekten Behebung dieses Fehlers finden sich auf Wikipedia:Defekte Weblinks. Ist ein von einem Bot als defekt gemeldeter externer Link doch erreichbar, dann bitte berichten – wie auch sonstige Probleme.

• http://www.informatik.tu-cottbus.de/~wwwpscb/lehre/GTI/vorl/skript.pdfhttp://giftbot.dwl.invalid/http://www.informatik.tu-cottbus.de/~wwwpscb/lehre/GTI/vorl/skript.pdf

– GiftBot (Diskussion) 20:50, 26. Nov. 2015 (CET)

Typ 0 = Phrasenstrukturgrammatik ?

Im Artikel wird "Typ-0-Grammatiken" mit "Phrasenstrukturgrammatiken" gleichgesetzt. Im Eintrag zu Phrasenstrukturgrammatiken (auf den auch verwiesen wird) steht jedoch, dass dieser Begriff nur für kontextsensitive Grammatiken zu verwenden ist. Das passt nicht zusammen. Jansan (Diskussion) 09:17, 29. Mär. 2016 (CEST)