Diskussion:Kontextfreie Grammatik

Existenzberechtigung des Artikels

Dieser Artikel sollte (und so ist es geplannt) mit selbigen Thema gefüllt werden, also aus Chomsky-Hierarchie herausgearbeitet werden ;) --Kleinvieh macht auch Mist 18:12, 29. Nov 2005 (CET)

Mach es, wenn du es planst, aber ein "Überarbeiten" in einem leeren Artikel ist sinnfrei. Wieder auf Ist-Zustand revertiert. -- Harro von Wuff 19:36, 9. Dez 2005 (CET)

Ich bin der Meinung, das dieser Artikel komplett weg gehört. Es ist nur nen Stub, und das bisschen erklärung kann genausogut in den Artikel "kontextfreie Sprache" eingearbeitet werden. -- Lordthundering 00:16, 9. Feb 2006 (CET)

Ich bin anderer Meinung und werde demnächst einiges nachtragen. -- Tombox2005 29. März 2006 (CET)

Zum Abschnitt "Deterministisch Kontextfrei"

Hi, zum einen ist an diesem Abschnitt zu bemängeln, dass hier die Definition Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle z \in Z, a \in \Sigma, A \in \Gamma} gilt: Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle |\delta (z,a,A)|+|\delta (z,\epsilon ,A)|\leq 1} , ohne zu erläutern, was eigentlich die Mengen Z, Sigma und Gamma bedeuten sollen. Auch wenn ich solche Definitionen kenne und es mir schon denken kann - das gilt schließlich nicht für jeden Leser.

Zweitens bin ich mir auch über die Aussage Ein deterministischer Automat akzeptiert einen Endzustand, und nicht einen leeren Keller nicht sicher. Ich kenne das genau anders herum! Also bitte nochmal nachprüfen und ggf. belegen. Mkleine 19:41, 4. Jun 2006 (CEST)

Mehrdeutiges Beispiel kann ich nicht nachvollziehen.

Ich bitte um Prüfung des mehrdeutigen Beispiels. A(epsylon) finde ich eben nicht. A(x,B(epsylon),y) würde anderes Ergebnis liefern. Durcht A->AA wird hier meiner Meinung nach keine Mehrdeutigkeit erzeugt. Danke.

Bitte naechstesmal Beitrag auf Disk.-Seite unterschreiben. Habe Beispiel geaendert. --Gms 16:20, 19. Feb. 2009 (CET)

Ich bitte um Prüfung des mehrdeutigen Beispiels. Hier sind 3 Ableitungen von xy angegeben, von denen mir nur die erste richtig zu sein scheint. S sollte bei diesen Produktionsregeln im Ableitungsbaum immer nur einen Sohn/Nachfolger haben, nicht mehr als einen. Statt dem angegebenen zweiten und dritten Ableitungsbaum wäre z. B. $S(A(A(x,A(\varepsilon ),y),A(\varepsilon )))$ ein alternativer Ableitungsbaum. Zudem müsste die Startvariable doch $S_{2}$ heißen, nicht $S$. --henning1000 (Diskussion) 22:47, 15. Dez. 2013 (CET)

Bezüglich S bzw S_2 hast du recht. Aber die Grammatik ist doch mehrdeutig. Fangen wir mal an mit S_2 -> A -> AA. Dann können wir entweder das linke A durch xAy und das rechte durch das leere Wort ersetzen oder umgekehrt. Im nächsten Schritt ersetzen wir das verbliebene A durchs leere Wort. Wir haben dann zwei verschiedene Ableitungsbäume. Einverstanden? --Herbert Klaeren (Diskussion) 19:45, 16. Dez. 2013 (CET)

Nein, nicht so ganz. Klar ist, dass diese Grammatik mehrdeutig ist. Klar ist auch, dass man für kontextfreie Sprachen Regeln der Form Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A\rightarrow\varepsilon} erlauben kann, wodurch hier die Mehrdeutigkeit entsteht. Aber wenn wir so wie von Ihnen vorgeschlagen beginnen, also Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_2\rightarrow A\rightarrow AA} , dann hat Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_2} im Ableitungsbaum den Sohn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A} und nicht die beiden Söhne Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle AA} . Ich habe den Artikel jetzt mal dahingehend verbessert, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A} der direkte Nachfolger von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_2} ist.

--henning1000 (Diskussion) 20:20, 16. Dez. 2013 (CET)

Wie kann man beweisen dass eine Grammatik nicht mehrdeutig ist?

Steht im Artikel, bzw. in der verlinkten Master-Arbeit. --Gms 16:20, 19. Feb. 2009 (CET)

Epsilon-Regeln

Seh ich das richtig, dass die Definition (wegen 1 <= ... <= l_r) Epsilon-Regeln ausschliesst? Im Text werden sie explizit erlaubt: Kontextfreie Sprachen können das leere Wort enthalten, z.B. durch eine Produktionsregel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (S \rightarrow \varepsilon)} . --UncleOwen 19:01, 10. Sep. 2009 (CEST)

Die Definition ist schon ok, da man ja Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle l_r < 1} wählen kann.

Allerdings könnte man an der Stelle die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varepsilon} -Notation erklären. Also das mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varepsilon} gerade das leere Wort gemeint ist und man es verwendet, da man sonst white-space in white-space hinschreiben müsste. --Gms 18:52, 11. Sep. 2009 (CEST)

Schließe mich der Meinung von Gms an. Analog zur leeren Summe, leerem Produkt etc. würde man hier das leere Wort als neutrales Element erwarten. Was mich aber interessieren würde wäre woher diese Definition stammt wenn es eine offline-Quelle gibt (finde sie sehr gut). Der Klarheit halber könnte man aber wirklich noch ein Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle l_r \in \mathbb{N_0}} (N_Null) hinzufügen. --Methossant 23:50, 25. Okt. 2009 (CET)

Wow

dieser Artikel ist so kontextfrei das man als Nichtinformatiker (selbst wenn man ein technisches Fach studiert hat) nur Bahnhof versteht ;-) Wie wärs mit ein paar allgemeinverständlichen Sätzen für Dummies - die erkennen läßt was denn nun die Idee von CFGs ist ? (nicht signierter Beitrag von 80.187.109.125 (Diskussion | Beiträge) 12:22, 28. Nov. 2009 (CET))

Stimmt schon. Einerseits ist dieses Gebiet gerade deswegen so schön, weil alles genau formalisiert ist, aber einen einfachen Quereinstieg gibts (hier) nicht. Vorschlag wäre: (1) Eine Sektion "Informelle Beschreibung", (2) Verweis auf einen Einführungsartikel zum Thema Formale Sprachen sowie (3) Erweiterung des ersten Absatzes um eine sehr kurze informelle Beschreibung.--Methossant 14:50, 28. Nov. 2009 (CET)

Ich habe mir gerade mal den englischen Artikel angeschaut, und da ist die Thematik wesentlich verständlicher erklärt. Vielleicht kann einer der Experten da etwas für den deutschen Artikel übernehmen :) -- 95.113.10.3 18:45, 25. Apr. 2010 (CEST)

Der 28. Nov. 2009 (CET) ist doch schon 'ne ganze Weile her... Ich finde, Methossant hat recht, und ein Fachwissender ;-) sollte das vielleicht mal umsetzen? Lediglich ein Verweis auf Formale Sprache reicht in meinen Augen nicht, für eine kurze "Laienerklärung" ist das zu umständlich. Aber dort in der Diskussionsseite (Diskussion:Formale_Sprache#Grauenvoll) habe ich ausführlicher etwas dazu geschrieben, davon sind leider viele Artikel betroffen. -- Zopp (Diskussion) 13:43, 21. Jun. 2012 (CEST)

Was soll denn bitte eine "kurze Laienerklärung" sein? Sowas wie "Kontextfreie Grammatiken sind bestimmte formale Grammatiken, die wegen ihrer Art der Regeln kontextfrei genannt werden"? (Da beißt sich die Katze in den Schwanz). Oder soll man weiter ausholen und erklären, was formale Sprachen sind, was formale Grammatiken sind, wie sie sich zu formalen Sprachen verhalten, was Produktionsregeln sind, was Terminalsymbole, was Nichtterminalsymbole, und wie die Grammatiken in der Chomsky-Hierarchie klassifiziert sind – womit man eine Hand voll Themen aufmacht, die man aber genauso wenig mit zwei Sätzen erklären kann, woraufhin man die Hauptartikel dazu dann doch wird lesen müssen? --Zahnradzacken (Diskussion) 01:21, 22. Jun. 2012 (CEST)

Erklärung von Kontext

Mit dem Edit [1] wurde die Passage gelöscht, die erklärt, warum eine kontextfreie Grammatik gerade als kontextfrei bezeichnet wird.

D.h. 'in Prosa' wird die mathematisch formale Definition in Bezug auf diesen einen Punkt erläutert.

Deshalb setze ich die Passage wieder rein.

--Gms 22:09, 30. Nov. 2009 (CET)

Zum mehrdeutigen Beispiel in den Beispiele

Selbst als Informatiker tue ich mir ziemlich schwer dem Artikel zu folgen und bin mir deshalb nicht sicher ob ich wirklich einen Fehler gefunden habe oder das aus einem mir nicht erkennbaren Grund so geschrieben wurde:

Es steht:

"Für $w_{3}=xy$ existieren unter anderem die Ableitungen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S(A(x,A(\varepsilon),y))} , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S(A(\varepsilon),A(x,A(\varepsilon),y))} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S(A(x,A(\varepsilon),y),A(\varepsilon))} ."

Sollte daß nicht so sein:

"Für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w_3=xy} existieren unter anderem die Ableitungen $S(A(x,A(\varepsilon ),y))$, Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S(A(A(\varepsilon),A(x,A(\varepsilon),y)))} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S(A(A(x,A(\varepsilon),y),A(\varepsilon))} ."

Schließlich muß das Startsymbol S (eigentlich Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_2} ) immer genau ein A enthalten.

Wie bereits geschrieben bin ich nicht sicher ob ich es richtig verstanden habe. Wäre toll wenn das jemand kontrollieren und entweder korrigieren oder meinen Beitrag kommentieren könnte

--Andreas Hammerschmidt 12:32, 15. Aug. 2010 (CEST)

Gut hingeschaut! Bei den letzen beiden Ableitunsbaeumen im aktuellen Artikel ist in der Tat das Problem, dass so getan wird als ob es eine Regel S -> AA geben wuerde, was nicht der Fall ist.

Also, Dein 2. Ableitungsbaum ist auch möglich, der dritte allerdings enthällt 5 öffnende und 4 schliessende Klammern.

Die Indices im jetztigen Beispiel werden nicht konsequent verwendet. D.h. S muesste durchgaengig durch S_2 ersetzt werden, analog A. Oder man verwendet einfach andere Buchstaben, ist wahrscheinlich uebersichtlicher. Oder man verwendet einfach S, A in der Definition von G_2.

--Gms 22:55, 30. Aug. 2010 (CEST)

Ist das mehrdeutige Beispiel überhaupt eine Typ-2 Grammatik? Durch die Produktionsregel A -> epsilon wird die Wortlängenmonotonie nicht mehr eingehalten. Dennoch ist es möglich, das eine Typ-2 Sprache erzeugt wird.

--Idefix1981 16:35, 23. Okt. 2010 (CEST)

Eine Wortlängenmonotonie gibt es bei CFGs nicht, Epsilonproduktionen sind völlig normal und natürlich ist das Beispiel eine Typ-2-Grammatik. --Herbert Klaeren 17:11, 23. Okt. 2010 (CEST)

Die Typ-2 Sprachen sind ja Teilmengen von Typ-1 Sprachen. Das epsilon Prduktionen in Typ-2 Grammatiken nur für das Startsymbol zulässig sind, findest du unter anderem hier: http://lehre.hki.uni-koeln.de/seminare/basisinformationstechnologie-i/theoretische-informatik-i/kontextfreie-grammatiken und hier: http://www.stud.uni-karlsruhe.de/~usauk/studium/WS0708/tutorium/chomsky.pdf.

Hätte die Grammatik die Produktion:

S -> A S -> epsilon A -> AA A -> xAy A -> xy

wäre sie wortlängenmonoton.

--Idefix1981 19:27, 23. Okt. 2010 (CEST)

Und wo wäre dann die Mehrdeutigkeit in der Herleitung von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle xy} ? Es gilt zwar $CF\subset CS$, aber daraus folgt noch keine Teilmengenbeziehung der Grammatiken. Mit den hier gewählten Definitionen gibt es keine durchgängige Inklusionshierarchie der Grammatiken. --Zahnradzacken 22:35, 23. Okt. 2010 (CEST)

Definition

Hi, müsste es hier nicht

• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P} ist eine endliche Teilmenge von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N \times (N \cup T)^+}

anstatt

• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P} ist eine endliche Teilmenge von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N \times (N \cup T)^*}

heißen?

Ist nicht jede Typ-2 Sprache auch eine Typ-1 Sprache? Damit dürfte von einem Nonterminal nicht auf das leere Wort abgebildet werden oder? -- Slllu 18:14, 14. Nov. 2010 (CET)

Regeln mit dem leeren Wort auf der rechten Seite muss es definitiv geben, sonst könnten nicht alle kontextfreien Sprachen erzeugt werden.--Ronnydotnet 13:01, 1. Dez. 2011 (CET)

Quellen

Die Quelle "Schöning, 2001" wird mehrfach verwendet. Welches Buch ist damit gemeint? "Theoretische Informatik - kurzgefasst" mit der ISBN 3827410991? --MartinThoma 15:08, 9. Feb. 2012 (CET)

Der Vorteil von Kontextfreien Grammatiken im Vergleich zu anderen und deren Einsatz

Meines Erachtens fehlt noch eins in diesem Artikel: Was ist der Vorteil von kontextfreien Grammatiken im Vergleich zu anderen Grammatiken der Chomsky Hierarchie? Nach meinem Kenntnisstand ist der Vorteil (einfach ausgedrückt), dass man eine Sprache mit wenigen, aber dafür besonders "mächtigen" Regeln ausdrücken kann. Daher lassen sie sich gut beim Parsing (PCFG-Parser) einsetzen. Zwei Fragen: 1) Ist meine Vorstellung korrekt? 2) Wie könnte man es etwas wissenschaftlicher ausdrücken (falls nötig)? Danke Hille181 18:18, 15. Okt. 2019 (CET)