Worauf bezieht sich "Kontext" in "kontextfreier Grammatik"?

Es gibt viele Definitionen online darüber, was eine kontextfreie Grammatik ist, aber nichts, was ich finde, befriedigt meine Hauptprobleme:

Von welchem Kontext ist es frei?

Um das zu untersuchen, googelte ich "kontextsensitive Grammatik", konnte aber immer noch nicht herausfinden, worum es beim "Kontext" ging.

Kann mir bitte jemand erklären, worauf sich der contextBegriff in diesen Namen bezieht?

terminology context-free formal-grammars CodyBugstein
quelle

Ich finde die Wikipedia-Erklärung ziemlich gut - "Eine formale Grammatik gilt als" kontextfrei ", wenn ihre Produktionsregeln unabhängig vom Kontext eines Nichtterminals angewendet werden können. Unabhängig davon, welche Symbole sie umgeben, kann das einzelne Nichtterminal auf der linken Seite immer verwendet werden durch die rechte Seite ersetzt werden. " - Es kann umformuliert und vereinfacht werden, um "Plain English" zu werden, aber das Wesentliche scheint mir ziemlich klar zu sein.

jkff

@jkff es ist toll, dass du die Erklärung gut findest, aber ich verstehe immer noch nicht, was "Kontext" hier wirklich bedeutet. Ich muss ein Beispiel sehen, in dem es einen Kontext gibt und in dem es keinen Kontext gibt. Mir scheint, jede Grammatik, die ich gesehen habe, hat Kontext

CodyBugstein

Ist es nicht klar aus der Definition?

Raphael

Ironischerweise fehlte der entscheidende Teil des Kontextes in dieser Definition , deshalb habe ich nur einen Satz hinzugefügt, um es zu erklären.

reinierpost

Beispiel: In C ++ 11 overridekann es sich entweder um einen Variablennamen oder ein Schlüsselwort handeln, je nachdem, wo es verwendet wird (dh in welchem Kontext). Bei Verwendung nach einer Methodendeklaration handelt es sich um ein Schlüsselwort. Sonst ist es nicht. Dies ist ein Beispiel für eine kontextsensitive Grammatik.

Thomas Eding

Antworten:

Sie haben recht, es gibt immer einen Zusammenhang in gewissem Sinne. Ich glaube nicht, dass man verstehen kann, was "Kontext" in "kontextfrei" bedeutet, ohne eine Produktion zu verstehen.

Eine Produktion ist eine Substitutionsregel. Es heißt, dass Sie zum Erzeugen von Zeichenfolgen in der Sprache das, was links ist, durch das, was rechts ist, ersetzen können:

A -> xy

Dies bedeutet, dass die abstrakte Folge A durch das Zeichen "x" gefolgt vom Zeichen "y" ersetzt werden kann. Sie können auch komplexere Produktionen haben:

zA -> xy

Dies bedeutet, dass das Zeichen "z" gefolgt von der abstrakten Sequenz A durch die Zeichen "x" und "y" ersetzt werden kann.

Eine kontextfreie Produktion bedeutet einfach, dass nur eins auf der linken Seite ist. Das erste Beispiel ist kontextfrei, da A durch "x" und "y" ersetzt werden kann, unabhängig davon, was davor oder danach kommt. Im zweiten Beispiel muss jedoch das Zeichen "z" vor dem A stehen, und dann kann die Kombination durch "x" und "y" ersetzt werden, sodass ein gewisser Zusammenhang besteht.

Eine kontextfreie Grammatik ist dann nur eine Grammatik mit nur kontextfreien Produktionen.

Das zweite Beispiel ist eigentlich ein Beispiel für eine uneingeschränkte Produktion. Es gibt eine andere Kategorie zwischen kontextfrei und uneingeschränkt, die als "kontextsensitiv" bezeichnet wird. Ein Beispiel für eine kontextsensitive Produktion ist:

zA -> zxy

Der Unterschied besteht darin, dass das, was vor A (und nach A) auf der linken Seite steht, auf der rechten Seite erhalten bleiben muss. Dies bedeutet effektiv, dass nur A substituiert wird, aber nur im richtigen Kontext substituiert werden kann.

Vaughn Cato
quelle

Danke, das ist eine große Hilfe! Ich habe noch nie ein Grammatikbeispiel mit mehr als einer Variablen auf der linken Seite gesehen, wie Sie gezeigt haben. Ich denke, deshalb konnte ich nicht sehen, was der "Kontext" war. Vielen Dank

CodyBugstein

Vielleicht wäre ein einfacheres Kontextbeispiel zA -> zxy: A wird immer noch durch xy ersetzt, aber erst nach z.

MSalters

Im Einzelnen geht es in dieser Antwort um eine uneingeschränkte Grammatik , während @MSalters darauf hinweist, dass eine kontextsensitive Grammatik ein besseres Beispiel für die Bedeutung des Kontexts wäre.

@MSalters: Du hast einen guten Punkt. Ich habe meine Antwort geändert. Es fiel mir schwer, einen Weg zu finden, wie ich diese Details zu meiner Beschreibung hinzufügen konnte, ohne dass dies komplexer klang. Also habe ich am Ende einfach mehr Details hinzugefügt.

Vaughn Cato

A \to β

$A \rightarrow \beta$

α A δ

$αAδ$

iLoveCamelCase
quelle

Was ist Beta? Ist es ein Terminal oder eine Variable? Und kannst du "sentential form" erklären? Bedeutet das, dass es nicht weiter abgeleitet werden kann?

CodyBugstein

Beta kann alles sein, nur dass A-> Beta eine Regel ist. Sententiale Form bedeutet, dass wir Ihr Startsymbol nach den Regeln der Grammatik in ein Ergebnis umwandeln. Dieses Ergebnis wird als sententiale Form bezeichnet. Nach jeder Anwendung jeder Regel erhalten wir ein neues Sentential-Formular.

iLoveCamelCase

@Imray Sie müssen sich die formalen Definitionen für Grammatiken und kontextfreie Grammatiken ansehen . Es gibt keine Abkürzung zum Verstehen formaler Objekte.

Raphael

@Imray A Satzform ist eine Kette von Terminal und nicht-terminale Symbole ergibt sich aus der Axiom (auch als Anfangssymbol durch Anwendung von Grammatik) Regeln (auch genannt Produktionen ). Eine sententiale Form kann durch Anwenden einer Regel auf eines ihrer nicht-terminalen Symbole in eine andere abgeleitet werden. Wenn keine Nicht-Terminals mehr vorhanden sind, ist die Sententialform ein Satz , dh eine Zeichenfolge oder ein Wort in der Sprache , die von der Grammatik definiert oder generiert wird. Die Terminologie stammt von den Linguisten, die zu einer Zeit die Hauptverantwortlichen für diesen Teil der formalen Sprachtheorie waren.

Babou

Ich dachte, ein sententiales Formular kann keine Variablen enthalten - es muss nur ein Terminal sein.

CodyBugstein