Diskussion:Ableitung (Informatik)

ÜA

Wie gehabt:

Wikipedia:Wie schreibe ich gute Artikel

Gibt es ein oder mehrere praktische Beispiele, die für jeden nachvollziehbar sind, woran man den Sinn, die Verwendung einer Ableitung erkennen kann? Kein mathematisches Beispiel.

Auch wenn das Beispiel nicht richtig sein sollte, geht es um den Sinn der Aussage.

In der Computertechnik wird ein Computerprogramm, ein Compiler, zur Übersetzung eines in einer Programmiersprache geschriebenen Quelltextes in ein Zielprogramm verwendet. Ein Parser, oft ein Teil eines Compilers, wird dazu verwendet ein Quellprogramm ganz oder schrittweise in einen Syntaxbaum, eine baumförmige Darstellung einer Ableitung, umzuwandeln. Scheitert der Parser dabei, so zeigt das an, dass das Quellprogramm kein syntaktisch korrektes Programm ist. Der Parser hat also in diesem Falle das Wortproblem und hat die Frage ob das das Programm ein Wort der Programmiersprache ist negativ beantwortet. Eine Zeichenkette gehört immer dann zu einer formalen Sprache, wenn die Zeichenkette eine Ableitung beinhaltet. --Strelok 19:34, 28. Mär. 2010 (CEST)

Moderne Compiler (bzw. ihr Parser-Anteil) arbeiten nicht so, dass sie direkt die Ableitung des Wortes bilden. "Ableitung" ist ein wesentlicher Begriff der Theoretischen Informatik und insbesondere zum Aufbau und zum Verständnis der Grammatiken formaler Sprachen unverzichtbar. Er hat allerdings keine aktuelle direkte Entsprechung im Compilerbau.

--Bri B. 12:35, 4. Jan. 2012 (CET)

Ich weiß nicht, was für einen Hokuspokus moderne Parser betreiben, um syntaktische Korrektheit zu erkennen. An den theoretischen Grundlagen kommen sie nicht vorbei. ANTLR jedenfalls verwendet noch abstrakte Syntaxbäume. Erkennt es eine Eingabe als korrekt, ist die Eingabe eine Ableitung aus der Grammatik. Nichts, was man nicht tun könnte, ohne einen Namen dafür zu haben, aber der Name wird durch das Parser-Beispiel veranschaulicht. --Zahnradzacken 14:25, 4. Jan. 2012 (CET)

Ein abstrakter Syntaxbaum ist aber kein Ableitungsbaum; insofern stimmt die Aussage des Artikels. -- UKoch 19:41, 11. Jan. 2012 (CET)

QS

Was die Einleitung betrifft weitgehend erledigt.--Strelok 19:34, 28. Mär. 2010 (CEST)

1. So wie der Artikel präsentiert wird, ist er ein schlechter Artikel und hat eher etwas von einem Auszug aus einem Lehrbuch an sich.

Die Wikipedia ist eine allgemeine Enzyklopädie und kein Fachbuch und sollte auch für Laien verständlich sein. Auszug aus Wikipedia:Wie schreibe ich gute Artikel

2. „Dieser Artikel setzt Vorkenntnisse im Bereich Theoretische Informatik voraus“ ist kein guter Ansatz, zum Mindesten sollte die Einleitung jedem Leser ermöglichen zu verstehen, um was es geht, wofür es ist, wer oder was es bracht und für wen oder was es von Bedeutung ist.

3. Die Relevanz ist aus dem Artikel nicht klar erkennbar; wenn das Thema eine Relevanz hat, sollte diese auch klar für jeden erkennbar und nachvollziehbar sein.

4. Die Ratschläge für „Wie schreibe ich gute Artikel“ sollten starker beachtet werden.

5. Keine Quellen, keine Literatur.

6. Gibt es praktische Beispiele, die für jeden nachvollziehbar sind, woran man den Sinn, die Verwendung erkennen kann? Kein mathematisches Beispiel.

7. Hinweis von Herr Klaeren: „Ziemlich schräg und unfertig. Ableitungen und Reduktionen sollten nicht ohne Not vermischt werden. Das Bsp. zur Ableitung verwendet in Wirklichkeit Reduktionen.“

--Strelok 15:55, 15. Nov. 2009 (CET)

Ein bisschen korrigiert und ausgebaut. Man darf m.E. nicht schlechterdings CFGs voraussetzen, den ganze Ableitungsmechanismus gibt's für recht viel allgemeinere generative Sprachklassen genauso, deshalb hab ich's zunächst mal wenigstens aufs Niveau gehoben, wo die gesamte Chomsky-Hierarchie mit dabei ist. Dann kann man leider nicht mehr von dem letzten Vorkommnis einer linken Seite einer Produktion reden, denn was wäre das? Der Teilstring, der am weitesten rechts anfängt — oder aufhört? Entsprechend führt Salomaa den Begriff der Rechtsableitung nur für CFGs ein. Die daraus rührenden Kautelen machen alles natürlich etwas schwieriger zu formulieren.

Vielleicht sollte man auch, weil der Begriff der Ableitung bei den Semi-Thue-Systemen schon ganz entsprechend existiert, ihn dafür auch mit abhandeln; dann für Chomsky-Grammatiken; dann für CFGs. Dann bekäme man allerdings von der Sprachklasse abhängige Definitionen, mit der schwierigsten für CG0, so oder so, in der Mitten, ich bezweifle, das das den unbewanderten Lesern unbedingt helfen würde. Vor allem auch die zwei Alphabete bei CGs gegen das eine bei STSs dürften höchst verwirren.

Oder sollte man die Definitionen in die entsprechenden Sprachklassen verschieben und dort dann so etwas wie verallgemeinert eine entsprechende Definition für die umfassende Grammatikklasse der ... hinzufügen?

-- Silvicola Diskussion Silvicola 21:30, 24. Nov. 2009 (CET)

@ Silvicola. Sind Sie der Ansicht das die Einleitung und Ihre Ausführungen einem Laien oder Lesern mit Grundkenntnissen ein Einblick verschafft um was es geht?--Strelok 23:03, 24. Nov. 2009 (CET)

Habe den Artikel überarbeitet. Insbesondere der erste Teil sollte nun verständlicher sein. Des Weiteren habe ich ein weiteres Beispiel hinzugefügt. Der Sinn ist nun hoffentlich klarer geworden. --NullKomma00 18:57, 23. Mär. 2010 (CET)

Ich habe offenbar die Streloksche Kritik nicht bemerkt, sonst wäre ich selber schon ran.

Abschnitt Definition

Einwände gegen die jetzige Fassung:

• Terminale, also für Zeichen, die nicht weiter abgeleitet werden — das stimmt nur für CFGs; im allgemeinen können die ersetzten $\alpha$ durchaus auch Terminale mitenthalten.
• Nichtterminalsymbole, also die Zeichen, die noch zu Terminalen ungewandelt werden müssen. — das Verb umwandeln gibt vielleicht Anlass zum Missverständnis, dass sie immer separat ersetzt werden und auch durch ein einzelnes Terminalsymbol.
• Werden mehrere Regeln auf einmal angewendet schreibt man $w\Rightarrow _{G}^{*}w'$ — das auf einmal führt in die Irre. $\Rightarrow _{G}^{*}$ ist definiert als sukzessive Einzelersetzung, nicht als simultane. Das macht einen Unterschied, weil weiter zu ersetzende Nonterminale erst in vorherigen Schritten entstehen können, und weil (bei Klassen oberhalb CF) eine voll simultane Ersetzung längere Kontexte, an denen manche der Produktionen ansetzen, erst gar nicht entstehen lassen könnte. Bsp: $N=\{S,A,B\}$, $P=\{S\rightarrow AB,A\rightarrow AB,B\rightarrow AB,AA\rightarrow c,A\rightarrow a,B\rightarrow b\}$. Bei simultaner Ersetzung enthält kein erzeugtes Wort ein c, bei sukzessiver Einzelersetzung schon.
• Da es sich hierbei häufig um kontextfreie Sprachen handelt, ist ein Kellerautomat nötig. — Nötig ist er im allgemeinen nicht; Reguläre Sprachen etwa können ja schon mit einem DFA analysiert werden. Und auch bei komplizierteren Sprachen könnte es natürlich im Einzelfall Parse-Mechanismen geben, die keine Kellerautomaten sind. Davon abgesehen, ist diese Aussage aus dem Kontext hier heraus gar nicht verständlich.

Ich schlage die folgende neue Fassung der Definition vor:

Sei $G=\left(N,T,P,S\right)$ eine Chomsky-Grammatik. Sie besteht aus 4 Teilen:

• aus $T$, dem endlichen Alphabet der Terminalsymbole oder Terminale in der Grammatik. Tritt im Zuge einer Ableitung eine Zeichenkette nur mit Zeichen aus $T$ auf, dann ist die Ableitung beendet.
• aus $N$, dem endlichen Alphabet der Nonterminalsymbole oder Nonterminale in der Grammatik. Solange im Zuge einer Ableitung die Zeichenkette noch irgend ein Zeichen aus $N$ enthält, ist die Ableitung noch nicht beendet. Alle Nonterminale müssen also am Ende einer Ableitung verschwunden sein, wobei aber zwischendurch die Zahl der Nonterminale durchaus auch wachsen kann.
• aus $S$, dem sogenannten Startsymbol. Jede Ableitung fängt mit $S$ an, und $S$ muss ein Nonterminal sein. (Sonst begönne und endete jede Ableitung mit S, damit wäre von einer solchen Grammatik nur genau das Wort $S$ selbst erzeugbar, also wäre die Sprache zu einem solchen $G$ reichlich trivial.)
• aus $P$, der endlichen Menge der Produktionsregeln oder Produktionen. Sie geben an, welche vorkommenden Teilzeichenketten durch welche anderen ersetzt werden dürfen. Eine einzelne Produktionsregel $p$ hat die Gestalt $p=\alpha \rightarrow \beta$, worin $\alpha$ und $\beta$ für irgendwelchen endlichen Ketten aus Zeichen aus dem Gesamtalphabet $\left(N\cup T\right)$ stehen. Wenn ein solches $p=\alpha \rightarrow \beta$ in der Produktionenmenge enthalten ist, dann erlaubt dies gerade, ein im Zwischenerzeugnis irgendwo vorkommendes $\alpha$ genau an dieser Stelle im Zuge eines Ableitungsschritt durch $\beta$ zu ersetzen. (Je nachdem, welche allgemeine Gestalt die $\alpha$ und $\beta$ aller Produktionen haben dürfen, unterscheidet man verschiedene Klassen von Grammatiken.)

-- Silvicola Diskussion Silvicola 22:48, 23. Mär. 2010 (CET)

Deine Definition ist besser gelungen.

Terminale dürfen in regulären, kontextfreine und kontextsensitiven Grammatiken nicht ersetzt werden, das könnte man im Artikel auch erwähnen. Bei Typ-0-Sprachen gilt die Aussage aber nicht.

Zu $w\Rightarrow _{G}^{*}w'$: Wie wäre es mit der Formulierung "Die Nacheinanderausführung von Ableitungsschritten kann statt $w\Rightarrow _{G}w'\Rightarrow _{G}w''\Rightarrow _{G}\cdots \Rightarrow _{G}w^{(n)}$ auch kurz als $w\Rightarrow _{G}^{*}w^{(n)}$ geschrieben werden."? --NullKomma00 11:22, 24. Mär. 2010 (CET)

Einleitung

Guten Tag,

schön das sich Autoren gefunden haben die sich dieses schwierigen Artikels annehmen. Aber leider bestehen die oben aufgeführten Mängel immer noch. Die Einleitung ist von dem Anspruch allgemein verständlich zu sein weit entfernt. Ich weiß das es sehr schwer ist diese Thematik allgemein verständlich zu vermitteln, aber es muss doch möglich sein zu mindestens eine Einleitung und eine Einführung so zu schreiben das es dem Leser möglich ist zu verstehen worum es geht. Siehe hierzu auch: Diskussion:Rechtsableitung. Ich vermisse eine gute Einleitung und eine allgemeinverständliche Zuordnung der Ableitung; wofür, wo gehört das hin, wer, was, usw. Alles was dann ab Definition beginnt ist natürlich für Außenstehende sehr spezial und wahrscheinlich uninteressant aber für Wissende relevant. Ich schließe mich Herrn Klaeren an: „Verständlich ist der Text nur für Experten“. --Strelok 12:37, 24. Mär. 2010 (CET)

Ich möchte den Punkt, die oben aufgeführten Mängel bestünden noch, relativieren:

• Ergänzend zum Zitat in Punkt 1: "Wenn das Verständnis eines Themas Spezialwissen erfordert, dann sollte die Einleitung dem Laien ermöglichen, den Artikelgegenstand zumindest einzuordnen."
• Punkt 3,5 und 7 haben sich erledigt, Beispiele gibt es auch inzwischen
• Meiner Meinung nach sind die verbleibenden Mängel: die Einleitung könnte (laienverständlich) mehr Information zum Einordnen liefern, die Bedeutung muss verdeutlicht werden, die vielen (teils neuen) Rechtschreib- und Formulierungsfehler müssen korrigiert werden, die Beispiele müssen anschaulicher werden – mehr Beispiele der gleichen Art sind kein Mehrwert

--Zahnradzacken 01:16, 25. Mär. 2010 (CET)

Moin, Wie wäre es mit dieser Formulierung als Einleitung?

Als Ableitung wird in der Theoretischen Informatik der Vorgang bezeichnet, ein Wort zu erzuegen, welches bestimmte syntaktische Anforderungen erfüllt. Dazu beginnt man mit einem einzigen Symbol und ersetzt es gemäß bestimmter, von den Anforderungen abhängigen, Regeln zu einer neuen Zeichenkombination. Die neu entstandenen Zeichenkombinationen können durch weitere Regelanwendungen weiter umgeformt werden.

Ist das verständlicher? --NullKomma00 15:54, 24. Mär. 2010 (CET)

Gefällt mir gut. Das Wort Anforderungen würde ich vielleicht durch Grammatik oder Sprache ersetzen? Ich glaube zu etw. ersetzen ist stilistisch unschön. Vielleicht eher was in Richtung "mit einer neuen Zeichenkombination ersetzen"? Sonst geht es m. M. n. in eine gute Richtung. Es müsste nur Strelok, der Wächter über die Bausteine, überzeugt werden ^^--Das Ed 16:59, 24. Mär. 2010 (CET)

Nein, ist nicht verständlicher, aber besser.

Hier ein Ansatz: Eine Ableitung ist in der Theoretischen Informatik eine Folge von Ableitungsschritten, die anhand eines mathematischen Modells von Grammatiken, ein Wort , daher eine endliche Folge von Symbolen aus einem Alphabet, erzeugt. Dazu beginnt man mit einem einzigen Symbol und ersetzt diese nach bestimmten Regeln durch eine (bestimmte, vorgegebene?)Zeichenkette.--Strelok 18:49, 24. Mär. 2010 (CET)

@ Das ED. Sie kennen doch die Problematik noch aus dem Artikel Rechtsableitung, lassen Sie doch Ihre Erfahrungen daraus einfließen. Vergessen Sie bitte nicht, das nicht jeder Leser mit den Fachbegriffen wie: formalen Grammatik, formale Sprache oder Wort (endliche Folge von Symbolen) vertraut ist. Es dürfte schwer werden den Wächter über die Bausteine zu überzeugen, aber machbar. :) --Strelok 18:49, 24. Mär. 2010 (CET)

Ich finde es schon interessant, dass ein Artikel herausgepickt wurde, der unter den Artikeln im Kontext formaler Sprachen das große Sorgenkind sein soll. Warum nicht Produktionsregel, Nichtterminalsymbol oder Terminalsymbol (dort mein Lieblingssatz, von hinten durch die Brust ins Auge: "Die Menge aller Terminalsymbole einer Grammatik bildet das Alphabet der Symbole, aus denen die Wörter der durch die Grammatik erzeugten Sprachen bestehen.")?

Ja, auch dieser Artikel muss besser werden. Aber muss man mit Biegen und Brechen eine Einleitung formulieren, die den Artikel salopp zusammenfasst? Was ist denn an der jetzigen Formulierung unverständlich? "Eine Ableitung bezeichnet in der Theoretischen Informatik das Erzeugen eines Wortes mittels einer Grammatik." Die Essenz ist hiermit schon gesagt, alles andere sind Formalismen. --Zahnradzacken 01:16, 25. Mär. 2010 (CET)

Wir arbeiten an diesem Artikel, weil wir irgendwo anfangen müssen. Um die weiteren Artikel werden wir, oder andere, uns sicher noch kümmern. Ich finde den momentanen ersten Satz als Definition gut. Zur Präzisierung und zur Verbesserung der Allgemeinverständlichkeit könnte ich mir eine Ergänzung mit Streloks Idee gut vorstellen. Vorschlag für den zweiten und dritten Satz:

Eine Grammatik ist ein mathematisches Modell, mit dem eine endliche Folge von Symbolen aus einem Alphabet, erzeugt werden kann. Dazu beginnt man mit einem einzigen Symbol und ersetzt es nach bestimmten Regeln durch eine in der Grammatik vorgegebene Zeichenkette --Das Ed 03:29, 25. Mär. 2010 (CET)

Ja, die sind richtig gut, diese beiden Sätze, rein damit! --Herbert Klaeren 08:45, 25. Mär. 2010 (CET)

Guten Tag,

der Artikel ist nicht das größte Sorgenkind. Warum nicht die anderen Artikel wie Produktionsregel, Nichtterminalsymbol oder Terminalsymbol? Ganz einfach weil ich die anderen Artikel noch nicht gelesen habe und mich erst mal an der Verbesserung dieses Artikels beteiligen möchte. Eine Einleitung sollte jedem Leser ermöglichen zu verstehen warum es geht. Nicht jeder Leser weiß das ein „Wort“ aus einer Folge von Symbolen besteht, sondern denkt wohl eher an eine Folge von Buchstaben, bei dem Alphabet denkt man wohl eher an das deutsche A-B-C als an das Alphabet der Theoretischen Informatik. Die Einleitung ist keine saloppe Zusammenfassung des Artikelinhaltes sondern soll, wie es bei Wiki üblich ist, eine Einleitung werden die es dem Laien ermöglicht den Artikelgegenstand einzuordnen bzw. zu verstehen. Es ist bestimmt kein Formalismus einem Artikel eine gute Einleitung zugeben.--Strelok 09:21, 25. Mär. 2010 (CET)

Wenn man es schafft, dass jeder Leser den Begriff versteht, ist das toll. Aber das schafft man mit der derzeitigen Formulierung (die ich übrigens ganz gelungen finde) ebenso wenig, wie mit den früheren Versuchen. Deshalb habe ich die Mindestanforderung zitiert, dass ein Laie den Begriff wenigstens einordnen können muss (und natürlich genauer einordnen als "aha, das ist theoretische Informatik – weiß bescheid"). Deshalb hätte es meiner Meinung nach gereicht, wenn ein Laie glaubt, dass ein Wort eine Folge von Buchstaben ist (wobei man $a\in \Sigma$ ja gerne auch als Buchstabe bezeichnet), solange der Begriff der Ableitung konzeptuell klar ist. Ich möchte auch keine saloppe Zusammenfassung, aber genau als solche empfand ich die bisherigen Versuche, die Einleitung "verständlich" zu machen. Mit Formalismus meinte ich etwas anderes: Die Details, die hinter der Ableitung stecken, sind mathematische Formalismen, auf die man in der Einleitung nicht eingehen muss. Deshalb möchte ich Details aus der Einleitung fernhalten. --Zahnradzacken 10:19, 25. Mär. 2010 (CET)

Das ist ein sehr ambitioniertes Ziel, Strelok. Du willst wirklich einem Leser, der nichts über Informatik weiss, innerhalb von drei, vier Sätzen das ganze Konzept exakt erklären? Wenn du das hinbekommst, solltest du ein Lehrbuch schreiben. Ansonsten stimme ich, bzgl. Allgemeinverständlichkeit, dem Zacken eins drüber zu. --Das Ed 12:33, 25. Mär. 2010 (CET)

Neue Einleitung

Guten Tag,

ich habe mir erlaubt eine überarbeitete Einleitung einzustellen und hoffe auf produktive Unterstützung zur Verbesserung der Einleitung sowie des ganzen Artikels. Danke.--Strelok 09:23, 25. Mär. 2010 (CET)

Diese Ausführung gefällt mir nicht so gut. Bereits im ersten Satz wird das Wort "Ableitung" mit dem Verb "ableiten" erklärt. Der zweite Satz ist unverständlich und irreführend. Mein neuer Vorschlag sieht so aus:

Als Ableitung wird in der Theoretischen Informatik das Erzeugen einer endliche Folge von Symbolen aus einem Alphabet bezeichnet. Die Folge von Symbolen wird Wort genannt; zum Erzeugen werden in einer formalen Grammatik definierte Regeln verwendet. Man beginnt dabei mit einem einzigen Symbol und ersetzt es durch eine in der Grammatik vorgegebene Zeichenkette.

--NullKomma00 10:18, 25. Mär. 2010 (CET)

Ganz blöde Frage: Weiter oben hast du einen Vorschlag gemacht, der mir und Herbert Klaeren gut gefallen hat. Wieso hast du jetzt eine andere Einleitung in den Artikel geschrieben? --Das Ed 12:29, 25. Mär. 2010 (CET)

• Mir gefällt die Version mit den genannten Ergänzungen auch gut, aber Strelok hat eine andere Formulierung in den Artikel geschrieben, die mit nicht gefällt. Daher habe ich noch einen Alternativvorschlag geschrieben.--NullKomma00 15:44, 25. Mär. 2010 (CET)

Also sammeln wir weiter ;) Mein Vorschlag ist eine Abänderung von Streloks Variante:

"Als Ableitung wird in der Theoretischen Informatik der Vorgang bezeichnet, ein Wort nach den Regeln einer formalen Grammatik zu bilden.

Hierbei versteht man in der theoretischen Informatik ein Wort als aneinandergereihte Zeichen (kurz Zeichenkette). Eine formale Grammatik ist ein mathematisches Modell zur Beschreibung einer Menge solcher Wörter. Diese Menge bezeichnet man als formale Sprache. Durch eine formale Grammatik werden außerdem Symbole festgelegt, die durch Zeichenketten ersetzt werden dürfen. Das einmalige Ersetzen eines dieser Symbole bezeichnet man als Ableitungsschritt.

Zum Ableiten eines Wortes beginnt man mit einem einzigen Symbol und ersetzt es nach den Regeln der formalen Grammatik schrittweise durch Zeichenketten, bis keine Symbole mehr ersetzt werden können.

Ableitungen bilden die Grundlage für Ableitungsbäume, die für Compiler zur maschinellen Darstellung von Programmcode dienen. In der theoretischen Informatik ist die Frage nach dem Vorhandensein einer Ableitung zu einem Wort gleichbedeutend mit dem Wortproblem, also mit der Frage, ob ein dieses Wort zur gegebenen Sprache gehört oder nicht."

Dann wäre es noch hilfreich, in einem ersten Abschnitt Grundlagen Grammatiken und Sprachen genauer zu erklären, wobei man hier dann sämtliche benötigte Fachbegriffe mitsamt intuitiver Erklärung einführen könnte (zum Beispiel die Begriffe Alphabet, Terminalsymbol, Nichtterminalsymbol). --Zahnradzacken 13:59, 25. Mär. 2010 (CET)

Aktion gleich Reaktion. Klappt doch. Weiter so, bitte.--Strelok 14:28, 25. Mär. 2010 (CET)

Kritik der derzeitigen Fassung:

Als Ableitung wird in der Theoretischen Informatik der Vorgang bezeichnet, ein Wort nach den Regeln einer formalen Grammatik zu bilden.

Wobei ein Wort aus einer endlichen Folge von Symbolen (Zeichenkette) besteht und eine formale Grammatik ein mathematisches Modell zur Beschreibung einer Menge solcher Wörter ist. Diese Menge bezeichnet man als formale Sprache. Durch eine formale Grammatik werden außerdem Symbole festgelegt, die durch Zeichenketten ersetzt werden dürfen. Das einmalige Ersetzen eines dieser Symbole bezeichnet man als Ableitungsschritt. Zum Ableiten eines Wortes beginnt man mit einem einzigen Symbol und ersetzt es nach den Regeln der formalen Grammatik schrittweise durch Zeichenketten, bis keine Symbole mehr ersetzt werden können.

• ein Wort … zu bilden — besser zu erzeugen.

Besser, stimmt.--Strelok 19:20, 25. Mär. 2010 (CET)

Mir ist beides recht. Mich interessiert aber, wieso erzeugen mehr Anklang findet. --Zahnradzacken 00:08, 26. Mär. 2010 (CET)

• Anschluss mit Wobei ist ganz schlecht. Hat die Definition Voraussetzungen, so sollten sie zuvor genannt werden, gerade im Interesse der Laien, und nicht hinterhergeschoben.

Definitionen sind keine Voraussetzung und man beginnt einen Artikel nicht mit Definitionen.--Strelok 19:20, 25. Mär. 2010 (CET)

Ich finde den Satz schlecht. Vielmehr ist "Wobei ... ist." eigentlich kein Satz, sondern ein Nebensatz. Gegen meine Formulierung mit Hierbei hätte ich aber weiterhin nichts einzuwenden. Denn an sich ist der erste Satz ja verständlich, was folgt sind Präzisierungen, damit man sich vom nicht-theoretischen Verständnis der Begriffe löst.

Ich möchte an der Stelle nun fragen, wieso wir uns nicht erst mal auf eine Einleitung einigen, statt dass komische Mischformen sofort eingearbeitet werden.--Zahnradzacken 00:08, 26. Mär. 2010 (CET)

• Das einmalige Ersetzen eines dieser Symbole — setzt wieder mal umstandslos und fälschlicherweise Typ-2-Sprachen voraus, im Allgemeinen werden aber Zeichenketten, die wenigstens ein Nichtterminal enthalten ersetzt.

Stimmt, da ist mir leider der gleiche Fehler unterlaufen, wie anderen offenbar zuvor. Wobei die Formulierung auch noch auf Typ-1-Grammatiken zutrifft. Ein verbesserter Vorschlag findet sich weiter unten. --Zahnradzacken 00:08, 26. Mär. 2010 (CET)

• einziges Symbol = Startsymbol gebraucht Symbol in der spezifischeren Bedeutung Nichtterminalsymbol, das schafft so nur Verwirrung. Wieso nicht beginnt man mit einem in der jeweiligen Grammatik ausgezeichneten Symbol, deren sogenanntem Startsymbol?

Im Prinzip ja, aber ausgezeichnet ist wieder so ein Jargon-Wort, das Laien nicht unbedingt als das interpretieren, was es bedeutet. --Zahnradzacken 00:08, 26. Mär. 2010 (CET)

• Ein Symbol, nämlich das Startsymbol, kann man i.A. nicht schrittweise ersetzen, weil es schon nach der ersten Ersetzung nicht mehr vorhanden sein mag in der hierbei erzeugten Satzform. Vgl. die Normalformen, in denen das Startsymbol in keiner Produktion rechts auftreten darf. Sobald man eine Substitution ausgeführt hat, steht eben i.A. etwas anderes da, man … ersetzt es … referiert also mit dem Pronomen falsch.

-- Silvicola Diskussion Silvicola 16:15, 25. Mär. 2010 (CET)

Guten Tag,

ich habe den letzten Kritikpunkt mehrmals gelesen und die Aussage dann doch noch erfasst.:) Für was steht i.A.? Doch nicht für „im Allgemeinem“. Logisch, wenn ein Symbol ersetzt wurde kann es nicht weiter bearbeitet werden. Der betreffende Satz wurde dementsprechend korrigiert.--Strelok 20:08, 25. Mär. 2010 (CET)

Ich glaube, "i.A." stand hier wirklich für "im Allgemeinen". Die korrigierte Fassung dürfte gut sein, aber das Wort Grammatik kommt vielleicht einmal zu oft vor.

Ich mache einen erneuten Vorschlag:

[Erster Satz unverändert]. "Hierbei bezeichnet man in der theoretischen Informatik ein Wort als eine endliche Folge von Symbolen (kurz Zeichenkette). Eine formale Grammatik ist ein mathematisches Modell zur Beschreibung einer Menge solcher Wörter. Diese Menge nennt man eine formale Sprache. Durch eine formale Grammatik werden außerdem Symbole festgelegt, die in Zwischenschritten der Ableitung, nicht aber im endgültigen Wort enthalten sein dürfen. Das einmalige Ersetzen von Teilen einer Zeichenkette nach den Regeln der formalen Grammatik bezeichnet man als Ableitungsschritt. Zum Ableiten eines Wortes beginnt man mit einem vorgegebenen Symbol, dem Startsymbol, und führt nacheinander Ableitungsschritte durch, bis man das Wort erhalten hat."

Anmerkungen:

• Bitte in die Klammern schreiben, was der geklammerte Einschub bedeutet. Sonst stolpert man beim Lesen.
• Ein Wort ist keine Zeichenkette, sondern ist in der theoretischen Informatik so definiert. Ich finde es gut, wenn man betont, dass dieser geläufige Begriff eine nicht so geläufige, strenge Definition hat.
• Bitte um Rückmeldung, ohne dass es gleich wieder abgewandelt eingearbeitet wird.

--Zahnradzacken 00:08, 26. Mär. 2010 (CET)

Guten Tag,

ich finde die ersten drei Sätze des Vorschlags sehr gut und habe diese so in den Artikel eingesetzt. Aber....:

Vielleicht so:

„Das einmalige Ersetzen von Teilen einer Zeichenkette, daher eines Symbols, nach den Regeln der formalen Grammatik bezeichnet man als Ableitungsschritt. Durch eine formale Grammatik werden Symbole festgelegt, die durch Zeichenketten ersetzt werden dürfen und solche die nach den Zwischenschritten einer Ableitung im dem zu erzeugendem Wort nicht enthalten sein dürfen. Zum Ableiten eines Wortes beginnt man mit einem vorgegebenen Symbol dem Startsymbol und führt, nach den Regeln der formalen Grammatik, nacheinander Ableitungsschritte bis man ein Wort erzeugt hat“.

Auch nur ein Vorschlag, aber noch nicht ausgereift.--Strelok 08:46, 26. Mär. 2010 (CET)

"Das einmalige Ersetzen von Teilen einer Zeichenkette, daher eines Symbols" – Wieso möchtest du das eine Symbol dort wieder erwähnen? Das war ja gerade der Knackpunkt, den Silvicola aufgezeigt hat: Bei Typ-0-Grammatiken kann man prinzipiell alles ersetzen. Man könnte also eine Regel $abXYba\rightarrow Zba$ haben. Auch eine nicht-verkürzende Grammatik (welche Typ-1-Sprachen erzeugt), kann Regeln der Form $abXY\rightarrow abcWdZ$ enthalten. Deshalb kann man nicht von nur einem Symbol reden und deshalb sind es nicht bloß die Symbole, die ersetzt werden, sondern allgemein Zeichenketten, die durch andere ersetzt werden.--Zahnradzacken 11:52, 26. Mär. 2010 (CET)

Will ich nicht, das war mein Fehler, bei dieser Änderung habe ich nicht richtig nachgedacht.--Strelok 09:14, 27. Mär. 2010 (CET)

Von Zahnradzacken: „Ich möchte an der Stelle nun fragen, wieso wir uns nicht erst mal auf eine Einleitung einigen, statt dass komische Mischformen sofort eingearbeitet werden.“

Antwort von Strelok: Weil dadurch die Fortschritte besser zu erkennen und zu erfassen sind, jeder Teilnehmer bzw. Interessierte liest sofort die Veränderungen im Artikel und muss nicht erst die ganze Diskussionsseite durchsuchen um den aktuellen Stand zu finden. Vielleicht beteiligt sich dadurch noch jemand an dieser Aktion.--Strelok 08:46, 26. Mär. 2010 (CET)

Nachvollziehbar, würde aber bedeuten, dass auch ich meine Vorschläge lieber in den Artikel schreiben sollte und nicht hierhin. Das würde aber zu einem ständigen Hin und Her führen, vor allem, weil du meine Vorschläge unsauber übernimmst (Rechtschreibfehler und Kommafehler). Ein weiterer Nachteil: Zwischenzeitlich sieht ein zufälliger Besucher nun die inhaltlichen Fehler, ohne zu wissen, dass dieser Text gerade zur Diskussion steht.

Wäre jeder Vorschlag eine Verbesserung, würde das besser funktionieren. Aber wir haben die Einleitung zwischendurch teilweise verschlechtert. --Zahnradzacken 11:52, 26. Mär. 2010 (CET)

Hallo Zahnradzacken, da nicht jeder Vorschlag oder Veränderung eine Verbesserung zur Folge haben muss, funktioniert es weder besser noch schlechter. Aber Sie haben Recht, wir sollten zuerst auf dieser Seite eine Einleitung ausarbeiten und nicht mehr im Artikel Änderungen vornehmen.--Strelok 09:14, 27. Mär. 2010 (CET)

Aktueller Vorschlag 1.0: In der theoretischen Informatik bezeichnet ein Wort eine endliche Folge von Symbolen (kurz Zeichenkette). Eine formale Grammatik ist ein mathematisches Modell zur Beschreibung einer Menge solcher Wörter, diese Menge nennt man eine formale Sprache. Das einmalige Ersetzen von Teilen einer Zeichenkette nach den Regeln der formalen Grammatik bezeichnet man als Ableitungsschritt. Durch eine formale Grammatik werden Symbole festgelegt, die durch Zeichenketten ersetzt werden dürfen, und solche, die nach den Zwischenschritten einer Ableitung im dem zu erzeugendem Wort nicht enthalten sein dürfen. Zum Ableiten eines Wortes beginnt man mit einem vorgegebenen Symbol, dem Startsymbol, und führt nacheinander Ableitungsschritte durch, bis ein Wort erzeugt wurde.

Nach kurzer Syntaxkorrektur bleibt mir nur (immer) noch ein Kritikpunkt: Der Satz

"Durch eine formale Grammatik werden Symbole festgelegt, die durch Zeichenketten ersetzt werden dürfen, und solche, die nach den Zwischenschritten einer Ableitung im dem zu erzeugendem Wort nicht enthalten sein dürfen."

trifft es wieder nicht: In einem Ableitungsschritt dürfen auch Terminale im Kontext von Nichtterminalen ersetzt werden. Beispiel $aXb\rightarrow c$. Die Menge der Symbole, die eine Grammatik zu ersetzen erlaubt, ist also bei Typ-0 (unter anderem bei monotonen Grammatiken) $N\cup T$, ansonsten $N$. So detailliert gehört das aber nicht in den Artikel, finde ich. Und wenn mit dem zweiten Teil des Satzes die Nichtterminalsymbole gemeint waren, so klingt das für mich missverständlich: Diese dürfen erst nach dem letzten Ableitungsschritt nicht mehr vorhanden sein. Vorschlag für den Satz:

"Durch eine formale Grammatik werden Symbole festgelegt, aus denen die Wörter bestehen dürfen, und weitere Symbole, die nur in den Zwischenergebnissen der Ableitung eines Worts noch enthalten sein dürfen."

--Zahnradzacken 11:19, 27. Mär. 2010 (CET)

Nach kurzer Syntaxkorrektur: Durch eine formale Grammatik werden Symbole festgelegt aus denen ein Wort bestehen darf und weitere die nur in den Zwischenergebnissen der Ableitung eines Wortes noch enthalten sein dürfen.

• § 72 Sind die gleichrangigen Teilsätze, Wortgruppen oder Wörter durch und, oder, beziehungsweise/bzw., sowie (= und), wie (= und), entweder ... oder, nicht ... noch, sowohl ... als (auch), sowohl ... wie (auch) oder durch weder ... noch verbunden, so setzt man kein Komma.
• K101 Zwischen nicht gleichrangigen Adjektiven (von denen das erste die folgende Fügung näher bestimmt) steht kein Komma.
• K119 Werden gleichrangige (nebengeordnete) Teilsätze durch Konjunktionen wie „und“ oder „oder“ verbunden, so setzt man kein Komma <§ 72 (1)>.--Strelok 14:19, 27. Mär. 2010 (CET)

Nett, aber das spielt keine Rolle: Die Kommata gehören dort hin, weil sie Nebensätze vom Hauptsatz abgrenzen.--Zahnradzacken 15:25, 27. Mär. 2010 (CET)

Vorschlag 1.1: In der theoretischen Informatik bezeichnet ein Wort eine endliche Folge von Symbolen (kurz Zeichenkette). Eine formale Grammatik ist ein mathematisches Modell zur Beschreibung einer Menge solcher Wörter, diese Menge nennt man eine formale Sprache. Das einmalige Ersetzen von Teilen einer Zeichenkette nach den Regeln der formalen Grammatik bezeichnet man als Ableitungsschritt. Durch eine formale Grammatik werden Symbole festgelegt aus denen ein Wort bestehen darf und weitere die nur in den Zwischenergebnissen der Ableitung eines Wortes noch enthalten sein dürfen. Zum Ableiten eines Wortes beginnt man mit einem vorgegebenen Symbol, dem Startsymbol, und führt nacheinander Ableitungsschritte durch bis ein Wort erzeugt wurde.

Vorschlag 1.2: In der theoretischen Informatik bezeichnet ein Wort eine endliche Folge von Symbolen (kurz Zeichenkette). Eine formale Grammatik ist ein mathematisches Modell zur Beschreibung einer Menge solcher Wörter, diese Menge nennt man eine formale Sprache. Das einmalige Ersetzen von Teilen einer Zeichenkette nach den Regeln der formalen Grammatik bezeichnet man als Ableitungsschritt. Durch eine formale Grammatik werden Symbole festgelegt, aus denen ein Wort bestehen darf und weitere, die nur in den Zwischenergebnissen der Ableitung eines Wortes enthalten sein dürfen. Zum Ableiten eines Wortes beginnt man mit einem vorgegebenen Symbol, dem Startsymbol, und führt nacheinander Ableitungsschritte durch, bis ein Wort der Sprache erzeugt ist.

Ich finde, dass nicht auf die Folge der Mathematik gelinkt werden sollte, da dies irreführend ist. Außerdem sind Interpunktion und Tempuswahl überarbeitet.--NullKomma00 14:45, 27. Mär. 2010 (CET)

Neuer Vorschlag

Beschreibung und Motivierung:

• etwas umgeordnet
• ausführlicher
• konsequent auf Zeichenkettenersatz umgestellt, also weg von CFG-Vorurteil
• vermieden, die NTS einzuführen im Kontext eines Verbotes, so etwas scheint mir den blutigen Laien nur zu irritieren, mit Reaktion: Wieso jetzt das Neue, wenn man dann doch sowieso nicht … damit darf? Besser positiv formulieren.

Weitere Ideen:

• Sollte man den die Laien bestimmt verwirrenden Gebrauch von „Wort” erklären? (Er kennt den Begriff ja nur naiv oder nach der Linguistik natürlicher Sprachen.) — Etwa in der Linie, dass bei der FS-Theorie „Wort”, „Satz” und „Äußerung/Text” identifiziert werden, weil keine Notwendigkeit besteht, verschiedene Methoden für die verschiedenen Sprach-Hierarchieebenen zu benutzen; weil eine FS von oben bis unten einheitliche Verfahren benutzt, weshalb Wort = Satz = Äußerung.
• Hier gibt es viele Baustellen, den Artikel, die verschiedenen Meldungen hier mit noch dazu Teil-Vorschlägen, die nach Einbau im Kontext vielleicht ganz anders aussähen. Mir wird das zu unübersichtlich.

Bitte:

• Wer am Text editiert, sollte doch bitte schön ihn so hinterlassen, dass er nicht schon allein orthographisch ein Graus ist.

In der theoretischen Informatik versteht man unter Worten endliche Folgen von Symbolen aus einem endlichen Alphabet, die man auch kurz Zeichenketten nennt. Sprache nennt man hier jede beliebige – insbesondere auch unendliche – Menge von solchen Worten/Zeichenketten. Die meisten der so definierten Sprachen sind sinnlos, weil ihre Sprachumfang nicht in Regeln zu fassen ist, die man bräuchte, um ihre Worte überhaupt sinnvoll zu gebrauchen und zu verstehen, weshalb man sich meist auf regelhaft gebildete Sprachen beschränkt.

Als günstig hat sich erwiesen, für solche Sprachen generative Regeln zu formulieren, also anzugeben, wie man sämtliche Worte einer speziellen Sprache nach einem iterativen Textersatzverfahren erzeugen kann. Jede Ersetzungsregel besteht dabei aus einem Suchmuster und einer Ersetzungsmuster, beides Zeichenketten. Ihre einmalige Anwendung besteht darin, dass man einen Fund des Suchmusters im Ausgangszustand mit der Ersetzungsmuster überschreibt.

Eine formale Grammatik ist ein mathematisches Modell, mit dem man solche Textersatzregeln unzweideutig definiert. Die Menge der mit den Regeln einer speziellen formalen Grammatik erzeugbaren Worte nennt man die zugehörige formale Sprache. Ein Ableitungsschritt ist eine einmalige erfolgreiche Anwendung einer Textersatzregel. Eine Ableitung ist eine Folge von Ableitungsschritten.

Jede Erzeugung eines Wortes beginnt beim immer selben Ausgangspunkt, dem sogenannten Startsymbol der spezifischen Grammatik. Das Startsymbol ist kein Zeichen der erzeugten Sprache selbst. Daneben gibt es im allgemeinen noch weitere Symbole, die zwar in den Zwischenzuständen der Worterzeugung auftreten können, aber nicht in Worten der erzeugten Sprache selbst vorkommen. Die zugrundeliegenden Grammatik legt also neben dem Sprachalphabet, den Ersetzungsregeln und dem Startsymbol auch sie im einzelnen fest. Die Ersetzungsregeln können also in ihrem Such- wie ihrem Ersetzungsmuster auch solche sogenannten Nonterminalsymbole enthalten.

-- Silvicola Diskussion Silvicola 15:14, 27. Mär. 2010 (CET)

Danke für die Rückkehr zur Übersichtlichkeit. Zur Beschreibung/Motivation/Ideen: Wo war im letzten Entwurf denn noch etwas von CFG-Vorurteilen zu lesen?

Ich hatte an Vorschlag 1.3 so lange gekocht, dass ein anderer dazwischen editiert hatte, ich wollte dann jedenfalls erst mal speichern, sonst kann leicht etwas verloren gehen. Deshalb Bezug auf den alten Stand zu CFG.

Zum Entwurf:

• Wenn es um blutige Laien geht, dann verwirrt meiner Meinung nach die Anmerkung, dass Sprachen unendlich sein können.

Ja, kann sein. -- Silvicola Diskussion Silvicola 16:36, 27. Mär. 2010 (CET)

• "Die meisten so definierten Sprachen sind sinnlos" – Bitte? Auch das Nachfolgende klingt sehr unausgewogen, vor allem aber finde ich das zu ausschweifend für eine Einleitung

Die Menge der Sprachen über einem nichttrivialen Alphabet ist überabzählbar. Mit einem endlichen Algorithmus erzeugen/erkennen/akzeptieren lassen sich nur abzählbar viele Sprachen. Wieso stört die Mächtigkeitslücke nicht? – Weil die soviel zahlreicheren anderen Sprachen für den menschlichen Gebrauch nutzlos sind. "Überabzählbar" wollte ich natürlich keinesfalls nennen; wenn der Text für speziell nur das Laienpublikum verwendet wird und entsprechend abgesagt, darf das natürlich gerne wegfallen. -- Silvicola Diskussion Silvicola 16:36, 27. Mär. 2010 (CET)

Ich finde, dass nicht jede Information in die Einleitung gehört. Und vor allem sollte im Auge behalten werden, dass dies der Artikel zur Ableitung ist, nicht zu formalen Sprachen allgemein.--Zahnradzacken 18:12, 27. Mär. 2010 (CET)

• Den Absatz ab "Als günstig hat sich erwiesen" finde ich anschaulich, aber je ausführlicher die Einleitung wird, desto unübersichtlicher finde ich sie. Ich bevorzuge eine Lösung, in der dem Einstieg für blutige Laien ein erstes Kapitel gewidmet wird (zum Beispiel mit obigem Text), während die Einleitung dem Laien als Überblick/zur Einordnung dient. Ich sehe zwar ein, dass der letzte Entwurf auch noch holprig war, aber so viel Text macht es mir persönlich nicht gerade zugänglicher.

Die Länge und ist ein Problem, zugegeben. Für ein spezielles Kapitel für die b-L-Zielgruppe mag es taugen. -- Silvicola Diskussion Silvicola 16:36, 27. Mär. 2010 (CET)

• Idee: Mir schwebt – leider nur sehr vage – eine Lösung vor, bei der Teile dieses Entwurfs in die Einleitung einfließen und Teile in ein Einstiegs-Kapitel.

--Zahnradzacken 15:47, 27. Mär. 2010 (CET)

Ich finde diese Idee gut. Wenn man bei einem Text sowohl pingeligst auf Korrektheit achten muss als auch gleichzeitig noch auf allgemeine Verständlichkeit, führt das, wie mir scheint, ins Formulierungs-Dilemma. Dabei sollte man dann auch bei dem Laien-Teil das Problem mit dem Wort, was kein Wort im umgangssprachlichen Sinn ist, ansprechen und klären. M.E.n. hakt es gerade bei Laien oft am Verständnis dadurch, dass Worte in einer willkürlichen Bedeutung verwendet werden, mag die auch zuvor klar definiert sein; es droht trotzdem die Interferenz. -- Silvicola Diskussion Silvicola 16:36, 27. Mär. 2010 (CET)

Es besteht in der Einleitung kein Problem mit dem Wort. „In der theoretischen Informatik bezeichnet ein Wort eine endliche Folge von Symbolen (kurz Zeichenkette).“ Damit dürfte wohl klar sein das es sich nicht um ein Wort im umgangssprachlichen Sinn handelt.--Strelok 16:57, 27. Mär. 2010 (CET)

Ich finde auch, dass diese Formulierung für eine Einleitung genügt. Ich stimme aber gleichzeitig Silvicola zu, dass jemand völlig Fachfremdes sich nicht wegen dieser kurzen Bemerkung all zu schnell von seinem Laienverständnis des Begriffs Wort trennen wird. "Umgangssprachlicher Sinn" ist auch nicht das Problem, denn "Wort" ist nicht Umgangs- sondern Hochsprache und somit jedem geläufig: Ein Wort ist etwas Kleineres als ein Satz, aber größer als eine Silbe. Im formalen Kontext ist das nicht der Fall. Ein Programm ist immer ein Wort seiner Programmiersprache, egal wie kurz oder lang.

Dieses Problem hat man bei so gut wie jedem Wort, das in eine Fachsprache übernommen wird. Wäre man konsequent, müsste also jeder Artikel eine Laien-Einleitung besitzen, der nicht umhin kommt, Fachjargon zu verwenden. Vielleicht kann man das anders lösen, aber zu Gunsten der Attraktivität sowohl für Laien als auch Experten, finde ich das Zusatzkapitel hier einen sinnvollen Ansatz.--Zahnradzacken 18:12, 27. Mär. 2010 (CET)

Der Vorschlag 1.3 ist als Einleitung ungeeignet, ist von der Allgemeinverständlichkeit zu weit entfernt. Ich schließe mich Zahnradzackens Meinung an das die Notwendigkeit besteht noch einen weiteren Abschnitt einzurichten, worin die Thematik spezifischer Beschrieben wird. Daher muss die Einleitung auch nicht perfekt werden, sondern nur verständlich. Durch einen zusätzlichen Abschnitt besteht die Möglichkeit die Thematik eher auf Fachbuch Niveau wiederzugeben.

Beispiel:

• Einleitung (Allgemeinverständlich)

Als Ableitung wird in der Theoretischen Informatik der Vorgang bezeichnet, ein Wort nach den Regeln einer formalen Grammatik zu erzeugen. In der theoretischen Informatik bezeichnet ein Wort eine endliche Folge von Symbolen (kurz Zeichenkette). Eine formale Grammatik ist ein mathematisches Modell zur Beschreibung einer Menge solcher Wörter, diese Menge nennt man eine formale Sprache. Das einmalige Ersetzen von Teilen einer Zeichenkette nach den Regeln der formalen Grammatik bezeichnet man als Ableitungsschritt. Durch eine formale Grammatik werden Symbole festgelegt, aus denen ein Wort bestehen darf, und weitere, die nur in den Zwischenergebnissen der Ableitung eines Wortes enthalten sein dürfen. Zum Ableiten eines Wortes beginnt man mit einem vorgegebenen Symbol, dem Startsymbol, und führt nacheinander Ableitungsschritte durch, bis ein Wort erzeugt wurde.

• Anwendungsbereich
• Definition Ableitung (Fachspezifisch)

In der theoretischen Informatik versteht man unter Worten...(spezifischer, genauer und ausführlicher als die Einleitung, worin die Ableitung eher fachlich richtig beschrieben wird.)

• Mathematische Definitionen

--Strelok 16:22, 27. Mär. 2010 (CET)

Ich hatte Zahnradzacken so verstanden, dass er ein Kapitel für die Laien haben will und stimme dem zu. Also ein gerade nicht fachspezifisches. Die fachspezifischen Ausführungen sollten zum Abschnitt Mathematische Definitionen dazu, der dann auch gerne anders heißen darf.

Kleinere, oft eher stilistische Einwände gegen Deine Fassung unter Einleitung (Allgemeinverständlich)

• Vorgang ist ein Gran zu konkret.
• In der theoretischen Informatik bezeichnet — besser: versteht man unter
• mit einem vorgegebenen Symbol — besser: besonderen, sonst könnte verstanden werden mit irgendeinem vorgegebenem.
• Kleineres (v.a. Zeichensetzung) im Text selbst korrigiert.

-- Silvicola Diskussion Silvicola 16:51, 27. Mär. 2010 (CET)

Hallo Silvicola,

das ist nicht meine Fassung, sondern unsere.

Nochmals, die Einleitung soll so verfasst werden das sie auch für Laien verständlich ist. Daher wäre ein Kapitel für Laien nicht unbedingt nötig.

Die fachspezifische Erörterung mit unter den Abschnitt Definition einzustellen ist ein gute Idee.

Die Einleitung ist bisher recht gut und keineswegs zu konkret.

Beispiel 2:

• Einleitung (Allgemeinverständlich)

Als Ableitung wird in der Theoretischen Informatik der Vorgang bezeichnet, ein Wort nach den Regeln einer formalen Grammatik zu erzeugen. In der theoretischen Informatik versteht man unter einem Wort eine endliche Folge von Symbolen (kurz Zeichenkette). Eine formale Grammatik ist ein mathematisches Modell zur Beschreibung einer Menge solcher Wörter, diese Menge nennt man eine formale Sprache. Das einmalige Ersetzen von Teilen einer Zeichenkette nach den Regeln der formalen Grammatik bezeichnet man als Ableitungsschritt. Durch eine formale Grammatik werden Symbole festgelegt, aus denen ein Wort bestehen darf und weitere Symbole die nur in den Zwischenergebnissen der Ableitung eines Wortes enthalten sein dürfen. Zum Ableiten eines Wortes beginnt man mit einem besonderen Symbol, dem Startsymbol, und führt nacheinander Ableitungsschritte durch, bis ein Wort erzeugt wurde.

• Anwendungsbereich
• Definition (Fachspezifisch)

In der theoretischen Informatik versteht man unter Worten...(spezifischer, genauer und ausführlicher als die Einleitung, worin die Ableitung eher fachlich richtig beschrieben wird.)

--Strelok 17:18, 27. Mär. 2010 (CET)

Hallo Strelok,

ich schlage noch die folgenden Änderungen vor:

"zur Beschreibung einer Menge solcher Wörter, diese Menge nennt man eine formale Sprache" — "von Mengen solcher Wörter, solche Mengen nennt man". Begründung: Nicht jede Menge von solchen Wörtern wird von einer FS beschrieben. In der eben vorgeschlagenen Fassung kann man die Wendung zumindest auch so verstehen, dass nur manche der Wortmengen von einer FS beschrieben werden, also kann man den Satz dann richtig auffassen. Lieber wäre mir allerdings, bei der Menge (vor dem Komma) noch irgendwas hinzuzufügen, was völlig klar machte, dass wirklich nur manche so erzeugbar sind, ich habe aber nichts Passendes gefunden, was nicht den Satz zu klobig, kautelienhaft, formal-fachmännisch machte.

Kommasetzung wieder im vorstehenden Text selbst korrigiert. Nach der Regel: Jedes Relativsatz wird stets vorn und hinten durch Komma abgetrennt (außer am Satzrand, selbstredend).

Dann ist die Formulierung aus meiner Sicht wirklich gut. Gruß -- Silvicola Diskussion Silvicola 18:32, 27. Mär. 2010 (CET)

Hallo Silvicola,

Auch wenn die Erklärung für ein WORT nicht zu 100% zutreffend ist, so ist diese in der Einleitung und zum Erfassen der Thematik ausreichend. Die von Ihnen aufgezeigten Defizite können Sie im Abschnitt "Definition", wie im Beispiel 2 aufgezeigt, durch eine entsprechende ausführliche und fachspezifisch Erklärung ausgleichen. --Strelok 20:53, 27. Mär. 2010 (CET)

Silvicola hat mich (vielleicht) richtig verstanden, siehe oben. Will man eine Einleitung verfassen, die jeder Laie verstehen kann, ohne Wikilinks zu folgen, ist die Einleitung länger als der Artikel selbst. Eine (evtl. kurze) Einleitung vor allen anderen Kapiteln braucht aber ein Artikel – und wenn er nur zwei Sätze enthält. Ich bin dafür, die Einleitung unter "Beispiel 2" als Artikeleinleitung zu wählen, gefolgt von einer Einführung für Laien, die man "Grundlagen" oder "Vorkenntnisse" nennen könnte. Anschließend sollte die Definition der neuen Begriffe sauber formal erfolgen, mit zusätzlicher intuitiver Erklärung. --- Je länger ich darüber nachdenke, desto unsinniger finde ich meine Idee. Eigentlich sollte im Laienkapitel dann schon der ganze Sachverhalt erklärt werden, nur eben nachdem die Vorkenntnisse erklärt wurden. --Zahnradzacken 18:12, 27. Mär. 2010 (CET)

Hallo Zahnradzacken,

Die Frage sollte nicht sein, wie Sie ein Kapitel über die Thematik der Ableitung in einer Allgemeinverständlicher Form mit allen relevanten Kriterien schreiben, sondern ob es Sinn macht, ob es nötig ist oder gibt es nicht genug hinführende Literatur über dieses Thema, die einen Interessierten besser einführt? Dann gibt es noch den Aspekt des Erarbeiten, ähnlich wie in der Schule oder im Studium. Wenn jemanden das Thema interessiert, bietet Wiki ihm reichlich Möglichkeiten weiter in das Thema einzusteigen. Wie sie gesehen haben ist es schon recht aufwendig eine gute Einleitung zu finden und ein Kapitel über die Ableitung nach Ihren Vorstellungen bzw. Ansprüchen (Allgemeinverständlich, fachlich Richtig und mit sämtlichen Einschränkungen, Definitionen usw.) dürfte wohl eine sehr komplexe Aufgabe werden. Viel Erfolg.--Strelok 20:53, 27. Mär. 2010 (CET)

Ein Laie wird wohl nie die formale Definition bis zum Ende lesen. Wenn man sich dazu versteht, etwas auf Laienniveau mit der dazu nötigen Länge zu erklären, sollte man es wirklich ganz so erklären. Ich weiß aber nicht, ob die hier gültige Editions-Politik es vorsieht, dass man sozusagen zwei separate Fassungen für zweierlei Publikum schreibt. Das wäre wohl ggf. noch vorab zu eruieren. -- Silvicola Diskussion Silvicola 18:32, 27. Mär. 2010 (CET)

Endfassung Einleitung?

Version 1.0
Als Ableitung wird in der Theoretischen Informatik der Vorgang bezeichnet, ein Wort nach den Regeln einer formalen Grammatik zu erzeugen.

In der theoretischen Informatik versteht man unter einem Wort eine endliche Folge von Symbolen (kurz Zeichenkette). Eine formale Grammatik ist ein mathematisches Modell zur Beschreibung einer Menge solcher Wörter, diese Menge nennt man eine formale Sprache. Das einmalige Ersetzen von Teilen einer Zeichenkette nach den Regeln der formalen Grammatik bezeichnet man als Ableitungsschritt. Durch eine formale Grammatik werden Symbole festgelegt, aus denen ein Wort bestehen darf und weitere Symbole die nur in den Zwischenergebnissen der Ableitung eines Wortes enthalten sein dürfen. Zum Ableiten eines Wortes beginnt man mit einem besonderen Symbol, dem Startsymbol, und führt nacheinander Ableitungsschritte durch, bis ein Wort erzeugt wurde.--Strelok 20:53, 27. Mär. 2010 (CET)

Version 1.1
Als Ableitung bezeichnet man in der Theoretischen Informatik ein Verfahren, mit dem ein Wort nach den Regeln einer formalen Grammatik erzeugt wird.

In der theoretischen Informatik versteht man unter einem Wort eine Zeichenkette, also eine endliche Folge von Symbolen. Eine formale Grammatik ist ein mathematisches Modell, das eine Menge solcher Wörter festlegt, nämlich die nach dieser Grammatik ableitbaren Wörter; man nennt diese Menge die zugehörige formale Sprache. Das einmalige Ersetzen eines Teilabschnitts einer Zeichenkette nach einer der Regeln der formalen Grammatik bezeichnet man als Ableitungsschritt. Durch eine formale Grammatik werden auch Symbole festgelegt, aus denen ein Wort bestehen darf, und weitere Symbole, die allein in den Zwischenergebnissen auftreten dürfen, die im Zuge der Ableitung eines Wortes durchlaufen werden. Zum Ableiten eines Wortes beginnt man mit einem besonderen Symbol, dem Startsymbol, und führt dann nacheinander passende Ableitungsschritte durch, bis schließlich das Wort erzeugt ist.

Begründungen

• Verfahren statt Vorgang: Da es nicht um ein einmaliges, konkretes Erzeugen geht.

Ein Vorgang muss kein einmaliger Prozess oder Ablauf sein. Aber Verfahren ist passender.--Strelok 00:47, 28. Mär. 2010 (CET)

Eine Ableitung eines Worts i.S.d. Definition ist aber kein Verfahren ... --Zahnradzacken 03:10, 28. Mär. 2010 (CEST)

Ableitung ist beides: die Aktion wie das Resultat. -- Silvicola Diskussion Silvicola 13:52, 28. Mär. 2010 (CEST)

Vielleicht. Vielleicht sieht die deutsche Sprache hier aber deshalb den Unterschieden zwischen dem Ableiten und der Ableitung vor. Der mathematischen Definition des Begriffs Ableitung nach verstehe ich darunter den vollendeten Vorgang. Jedenfalls wäre es eine völlige Überfrachtung der Einleitung, auch diese sprachliche Ungenauigkeit aufzulösen. Aber man könnte durchaus (ungefähr) so anfangen: "Als Ableitung bezeichnet man [...] ein Verfahren, [...], als auch dessen erfolgreiche Anwendung."--Zahnradzacken 18:01, 28. Mär. 2010 (CEST)

• Zeichenkette und Folge von Symbolen umgestellt: erst durch das Gängigere definieren, danach formale Präzisierung, es ist schließlich der allgemeinsprachliche Teil. Vielleicht braucht man die Präzisierung gar nicht?

- Es ist nicht der Allgemein Sprachliche Teil, sondern die Allgemeinverständliche Einleitung. Die Umstellung ist besser, aber die anderen Änderung eher irritierend. --Strelok 00:47, 28. Mär. 2010 (CET)

Ich würde die Frage mit "ja" beantworten: "endliche Folge" muss man nicht schon hier erwähnen.

Was ist irritierend? -- Silvicola Diskussion Silvicola 13:52, 28. Mär. 2010 (CEST)

• ein mathematisches Modell zur Beschreibung: ausgeführt wieso, durch Bezug auf hier schon Bekanntes. Sonst ist der Zusammenhang rätselhaft. Bedeutung von ableitbar klar, da vorher Ableitung benannt.

- Keine Verbesserung für die Allgemeinverständliche Einleitung, zu umständlich. Das gehört eher in den Abschnitt Definition.--Strelok 00:47, 28. Mär. 2010 (CET)

Ich fand die Passage gut. Hat eine bessere Brücke zwischen Einleitungssatz und dem ganzen Erklärungsabschnitt geschlagen. --Zahnradzacken 03:10, 28. Mär. 2010 (CEST)

Dann neu formulieren.--Strelok 11:29, 28. Mär. 2010 (CEST)

Wie wär's mit definiert statt festlegt? -- Silvicola Diskussion Silvicola 13:52, 28. Mär. 2010 (CEST)

• um diese Menge herum: diese muss sich sprachlich auf etwas Vorheriges und Feststehendes beziehen; aber das eine Menge zuvor meint eine Menge, die ja von der Grammatik abhängt, insofern also variabel ist. Das passt also nicht.

- Passt schon. In der Einleitung besteht noch nicht die Notwendigkeit die Restriktionen so ausführlich dazulegen, im Abschnitt Definition müssen diese aufgeführt werden.--Strelok 00:47, 28. Mär. 2010 (CET)

In Wahrheit nennt man jede Menge, die nach irgendeiner Grammatik so zustandkommt, eine FS, und nicht nur diese. Dann bitte wenigstens Solche Mengen nennt man … (Sprachlicher Einwand) -- Silvicola Diskussion Silvicola 13:52, 28. Mär. 2010 (CEST)

• eines Teilabschnitts statt von Teilen: die alte Formulierung konnte auch so verstehen verstanden werden, dass man mehrere nicht zusammenhängende Teilzeichenketten zusammen ersetzen könnte, speziell etwa (im Falle einer CFG-Ersetzung) jedes Vorkommen desselben NTS zugleich. Gemeint ist aber genau ein Infix, Präfix oder Suffix (Bezeichnungen, die ich hier meiden wollte).

- Der Ansatz ist falsch, hierbei setzten Sie voraus das der Leser Vorkenntnisse besitzt. Da dem nicht unbedingt so ist, genügt die vereinfachte Version. In Definition unterbringen.--Strelok 00:47, 28. Mär. 2010 (CET)

Strelok, Sie setzten nun aber voraus, es würden nur Laien den Artikel lesen – was man genauso wenig voraussetzen kann. Deshalb genügt die einfache Form nicht, die Präzisierung ist richtig und wichtig. --Zahnradzacken 03:10, 28. Mär. 2010 (CEST)

Nein, setzte ich nicht voraus. Jeder kann den Artikel lesen aber die Richtlinien von Wiki für einen guten Artikel sollten schon erfüllt werden. Dann muss die Formulierung auch den Anspruch der Allgemeinverständlichkeit in der Einleitung erfüllen.--Strelok 11:29, 28. Mär. 2010 (CEST)

Es geht um zwei Anforderungen zugleich: 1. korrekt, 2. verständlich. Etwas nicht Korrektes zu schreiben, ist unbedingt verkehrt und schlimmer als schwer verständlich, weil das doch immerhin einige verstehen könnten. Ein Lexikonartikel muss auch noch bestehen können, nachdem man ihn verstanden hat. Wir bauen hier keine Eselsbrücken. -- Silvicola Diskussion Silvicola 13:52, 28. Mär. 2010 (CEST)

Richtig. Außerdem ist es doch bitte schön nicht zu viel verlangt, dass ein Laie "von einem Teilabschnitt einer Zeichenkette" genauso gut versteht wie "von Teilen einer Zeichenkette" – mit dem Unterschied, das letzteres nicht ganz richtig ist. --Zahnradzacken 18:01, 28. Mär. 2010 (CEST)

• neu passende: wenigstens einmal erwähnen, dass man bei einer Ableitung i.d.R. eine Wahl hat, wie man sie fortsetzen will; und dass nicht jede Ableitung in jedem beliebigen Wort endet; sonst könnte der Leser vielleicht meinen, das Verfahren sei deterministisch.

- Der Ansatz ist falsch, hierbei setzten Sie wieder Vorkenntnisse voraus. In der Einleitung nicht nötig aber muss natürlich in der Definition untergebracht werden. Was passiert wenn nicht passende Ableitungsschritte durchgeführt würde?--Strelok 00:47, 28. Mär. 2010 (CET)

Ich empfände das auch als zu detailliert. Ihre Frage, Strelok, zeigt außerdem einen Schwachpunkt der Formulierung auf: Es gibt nur passende Ableitungsschritte. Würde das Wort also streichen. --Zahnradzacken 03:10, 28. Mär. 2010 (CEST)

Wenn man bei einer Ableitung eines Wortes einen Zwischenschritt ändert, verfehlt man i.A. das Wort und leitet ein anderes ab; wenn man immer nur Produktionen anwendet, die rechts zumindest ein NTS haben, dann endet die Ableitung gar nicht. Man kommt nicht etwa sozusagen "automatisch bei einem Wort vorbei", das wollte ich ansprechen. -- Silvicola Diskussion Silvicola 13:52, 28. Mär. 2010 (CEST)

Verstehe die Problematik, aber "passend" passt nicht und "gemäß der Grammatik" taucht schon oft genug auf. Also doch ein längerer Satz (siehe unten)?--Zahnradzacken 18:03, 28. Mär. 2010 (CEST)

• Sonst nur Stil (Aktiv statt Passiv, Klammer aufgelöst, verbaler) und Rechtschreibung (Relativsatz-Kommas).

Gruß -- Silvicola Diskussion Silvicola 22:26, 27. Mär. 2010 (CET)

Version 1.2
Als Ableitung wird in der theoretischen Informatik der Vorgang bezeichnet, ein Wort nach den Regeln einer formalen Grammatik zu erzeugen.

Unter einem Wort versteht man eine beliebige Zeichenkette, also eine endliche Folge von Symbolen. Eine formale Grammatik ist ein mathematisches Modell, das eine Menge solcher ableitbaren Wörter festlegt. Solche Mengen nennt man formale Sprachen. Das einmalige Ersetzen von einem Teilabschnitt einer Zeichenkette, gemäß einer der Regeln der formalen Grammatik, stellt einen Ableitungsschritt dar. Durch die formale Grammatik werden auch die Symbole festgelegt, aus denen ein Wort bestehen darf, und solche, die alleine in den Zwischenergebnissen der Ableitung eines Wortes auftreten dürfen. Zum Ableiten eines Wortes beginnt man mit einem besonderen Symbol, dem Startsymbol, und führt dann nacheinander Ableitungsschritte durch (bei Wahl geeigneter Regeln), bis schließlich das Wort erzeugt worden ist.

Ich habe mir erlaubt, Version 1.2 zu überschreiben, das hat hier ja schon genug gewuchert. Änderungen, Begründungen:

• Eine Ableitung eines Worts ist kein Verfahren (klingt zu sehr nach Algorithmus), sondern die Anwendung eines Verfahrens oder vielmehr ein Ergebnis (das Ergebnis des Ableitens ist die Ableitung – aber inklusive "Rechenweg"). Ich finde deshalb "Vorgang" besser, auch wenn es selbst nicht ganz zutrifft. (Bei der Gelegenheit: Warum war nochmal "Wort erzeugen" besser als "Wort bilden"?)

Weil Wort bilden an den linguistischen Begriff der Wortbildung denken lässt, das kann irritieren. -- Silvicola Diskussion Silvicola 13:52, 28. Mär. 2010 (CEST)

Was ist daran irritierend? Gerade Wortbildung kann doch durch Grammatiken beschrieben werden.--Zahnradzacken 18:01, 28. Mär. 2010 (CEST)

• "beliebige Zeichenkette", Präzisierung als endliche Folge weggelassen, dafür "beliebig" hinzugefügt, um den unnatürlichen Charakter zu betonen.

beliebig ist gar nicht da.

(Verstehe den Satz nicht) Du meinst, die Zeichenketten sind nicht beliebig? Ein beliebiges Wort ist eine beliebige Zeichenkette. Es ist erst dann nicht mehr beliebig, wenn es um Zugehörigkeit zu einer Sprache geht.--Zahnradzacken 18:01, 28. Mär. 2010 (CEST)

• Satz ab "Das einmalige Ersetzen": einmal weniger Genitiv und Klammern dazu, damit das Auge den Satz noch überblickt.

nach einer der Regeln ist weggefallen. -- Silvicola Diskussion Silvicola 13:52, 28. Mär. 2010 (CEST)

Ja, schade .. Warum, Strelok? --Zahnradzacken 18:01, 28. Mär. 2010 (CEST)

• Umschreibung der Terminalsymbole präzisiert
• "passende" entfernt (man kann keine unpassenden Ableitungsschritte durchführen), "Passiv statt Aktiv" klingt für mich an der Stelle runder

S.o. Um ein bestimmtes Wort zu "treffen", muss man geeignet vorgehen. -- Silvicola Diskussion Silvicola 13:52, 28. Mär. 2010 (CEST)

• Anmerkung: 2x "in der theoretischen Informatik" kurz nacheinander liest sich blöd, könnte auch noch besser werden.

--Zahnradzacken 03:10, 28. Mär. 2010 (CEST)

Nochmals Version 1.2 überarbeitet, neuer Syntax. Alle Änderungen sind erhalten geblieben, bitte neue Version erstellen.--Strelok 11:29, 28. Mär. 2010 (CEST)

Neue Syntax = neue Fehler? Tut mir leid, aber immer die gleichen Kommafehler gehen mir langsam etwas auf die Nerven.

Habe ebenfalls kleine Anpassungen entsprechend meiner Kommentare vorgenommen, plus:

"Unter einem Wort ...., wobei die formale Grammatik" In dem Satz wird die formale Grammatik nicht genannt, finde das "wobei" deshalb sehr holprig. --Zahnradzacken 18:01, 28. Mär. 2010 (CEST)

Hab jetzt leider keine Zeit mehr -- Silvicola Diskussion Silvicola 13:52, 28. Mär. 2010 (CEST)

Schade ....Bis bald. --Strelok 14:14, 28. Mär. 2010 (CEST)

Nachdem ich mir nochmals die ganze Diskussionsseite durch gelesen habe, finde ich die letzte Version von Ihnen als Einleitung für den Artikel als Allgemeinverständlich. Letztendlich steht die Einleitung und es werden bestimmt noch kleinere Veränderungen vorgenommen. Ich hoffe das dieses Beispiel in den anderen Artikel der theoretischen Informatik, in einer passenden Form, übernommen wird. Nicht nur um die Wiki-Ansprüche zu erfüllen. Es wäre ein qualitativer Gewinn für den Artikel, wenn Sie Ihre Idee mit der Erweiterung der Definition über die Ableitung (formale Definition), durch eine Kombination aus ein wenig Allgemeinverständlichkeit und spezifischen Fachwissen ausbauen würden. --Strelok 19:52, 28. Mär. 2010 (CEST)

Danke für die produktive Atmosphäre und Zusammenarbeit. Ich glaube, in dem Zustand ist der Artikel motivierend genug für weitere Verbesserungen. Wenn es die Zeit erlaubt, versuche ich mich an einem Abschnitt eines verständlichen Überblicks.--Zahnradzacken 22:58, 28. Mär. 2010 (CEST)

Abschnitt Anwendungsbereich

Es wird wohl Zeit, dass der Abschnitt überarbeitet wird. Erstens könnte man hier neben Parsern als zweites Beispiel auf die Linguistik verweisen (s. etwas verstecktes Beispiel bei Nichtterminalsymbol). Dort gibt es Ableitungen auch ohne Parser (in der Computerlinguistik werden aber auch Parser genutzt). Zweitens bin ich nicht mit der neusten Änderung einverstanden, die Ableitung sei nur ein begriffliches Konzept. Parser erstellen doch erst einen Syntaxbaum, bevor sie ihn in einen AST abstrahieren, oder nicht? Parser ohne AST finden dennoch eine Ableitung oder eben nicht, nämlich durch Anwenden von Regeln in einer bestimmten Reihenfolge. Ob die Ableitung später noch interessiert (i.d.R. schon, wenn man die Syntax nicht nur für einen Syntaxcheck parst, sondern um dann damit etwas zu tun), oder nicht, eine Ableitung fand statt (oder schlug fehl). --Zahnradzacken 19:13, 4. Jan. 2012 (CET)

Besseres Beispiel (?) Inkonsistenz zu formale Grammatik / Produktionsregel

Ich komme von "Mit einer formalen Grammatik lassen sich ausgehend von einem Startsymbol S (auch Startvariable genannt) Produktionsregeln aus einer Regelmenge P anwenden, die aus dem Startsymbol neue Zeichenfolgen erzeugen, welche wiederum weiter ersetzt werden können. Diesen Vorgang nennt man auch Ableitung" (de.wikipedia.org/wiki/Formale_Grammatik) siehe auch ..../Produktionsregel.

Mit den ersten beiden Beschreibungen (besonders den Beispielen) komme ich recht gut zurecht. Das Beispiel mit dem Palindrom aber kommt mir doch sehr verwirrend vor. Gibt es kein besseres Beispiel, was sich an Grammatik / Produktionsregel (Wiki-Artikel) besser anlehnt ? Wäre schade wenn der Artikel deswegen verschmäht würde.

Platt ausgedrückt könnte "Ableitung" heißen : Von einem abstrakteren (Nichtterminal) zu einen konkreterem (Nichtterminal/Terminal) bis hin zum "Ende" ?? 31.19.219.149 20:58, 22. Mai 2013 (CEST)

Unter Formale Grammatik wird sich etwas ungenau ausgedrückt, dort fehlt der Hinweis, dass die Ableitung ein Wort ergibt (was sich nicht so leicht unterbringen lässt in einem gewollt einfachen Abschnitt, aber mit deiner "platten" Formulierung bist du in der richtigen Richtung). Doch worin genau siehst du denn eine Inkonsistenz? Was schreckt dich genau am Palindrom-Beispiel ab? --Zahnradzacken (Diskussion) 23:53, 22. Mai 2013 (CEST)