Was ist eine kontextfreie Grammatik?

104

Kann mir jemand erklären, was eine kontextfreie Grammatik ist? Nachdem ich mir den Wikipedia-Eintrag und dann den Wikipedia-Eintrag zur formalen Grammatik angesehen habe, bin ich völlig verwirrt. Wäre jemand so freundlich zu erklären, was diese Dinge sind?

Ich wundere mich darüber, weil ich das Parsen und nebenbei die Einschränkung einer Regex-Engine untersuchen möchte.

Ich bin mir nicht sicher, ob diese Begriffe direkt mit der Programmierung zusammenhängen oder ob sie eher mit der Linguistik im Allgemeinen zusammenhängen. Wenn das der Fall ist, entschuldige ich mich, könnte dies vielleicht verschoben werden, wenn ja?

Ell
quelle
2
Es ist mehr verwandt mitAutomata Theorem
Rahul
2
Wenn Sie sich für formale Sprachen und Automatentheorie zum Parsen interessieren, empfehle ich ein Buch wie Sudkamps Languages ​​and Machines oder Aho, Sethi & Ullmans Compiler . Jedes Buch enthält eine formale Beschreibung einer kontextfreien Grammatik, bei der es sich um eine Art formale Grammatik handelt. Anschließend werden grundlegende Theoreme über kontextfreie Grammatiken angegeben und bewiesen, die zum Verständnis dieser Grammatik erforderlich sind (z. B. das Pump-Lemma für kontextfreie Sprachen und Konvertierung und Normalformsätze). Es gibt keine mathematische Voraussetzung für das Erlernen der formalen Sprachtheorie, die über ein flüchtiges Verständnis der Mengenlehre hinausgeht.
Danportin
1
Sollten solche Fragen nicht in die Theoretische Informatik migriert werden?
Hellblauer Punkt

Antworten:

110

Eine kontextfreie Grammatik ist eine Grammatik, die bestimmte Eigenschaften erfüllt. In der Informatik beschreiben Grammatiken Sprachen; Insbesondere beschreiben sie formale Sprachen.

Eine formale Sprache ist nur eine Menge (mathematischer Begriff für eine Sammlung von Objekten) von Zeichenfolgen (Folgen von Symbolen ... sehr ähnlich der Programmierverwendung des Wortes "Zeichenfolge"). Ein einfaches Beispiel für eine formale Sprache ist die Menge aller Binärzeichenfolgen der Länge drei, {000, 001, 010, 011, 100, 101, 110, 111}.

Grammatiken definieren Transformationen, die Sie vornehmen können, um eine Zeichenfolge in der von einer Grammatik beschriebenen Sprache zu erstellen. Grammatiken sagen, wie ein Startsymbol (normalerweise S) in eine Zeichenfolge umgewandelt wird. Eine Grammatik für die zuvor angegebene Sprache lautet:

S -> BBB
B -> 0
B -> 1

Die Art und Weise , dies zu interpretieren ist zu sagen , dass Sdurch ersetzt werden kann BBB, und Bkann durch 0 ersetzt werden, und Bkann durch 1. So ersetzt werden , um die Zeichenfolge 010 zu konstruieren , was wir tun können S -> BBB -> 0BB -> 01B -> 010.

Eine kontextfreie Grammatik ist einfach eine Grammatik, bei der das zu ersetzende Element (links vom Pfeil) ein einzelnes "nicht-terminales" Symbol ist. Ein nicht-terminales Symbol ist jedes Symbol, das Sie in der Grammatik verwenden und das nicht in Ihren endgültigen Zeichenfolgen enthalten ist. In der obigen Grammatik sind "S" und "B" nicht-terminale Symbole und "0" und "1" sind "terminale" Symbole. Grammatiken mögen

S -> AB
AB -> 1
A -> AA
B -> 0

Sind nicht regulär, da sie Regeln wie "AB -> 1" enthalten.

Aegrisomnie
quelle
12
Meinen Sie mit "nicht regelmäßig" "nicht kontextfrei"? (weil die Sprache, die durch CFGs dargestellt werden kann, eine Supermenge derjenigen ist, die durch reguläre Ausdrücke dargestellt werden können)
Anti Earth
3
Sollte "S kann durch B ersetzt werden" gelesen werden "S kann durch BBB ersetzt werden"?
Cosmo Harrigan
4
Guter Herr, dies ist eine der am besten erklärten Antworten, die ich auf SO gesehen habe.
Rafael Dias da Silva
1
@AntiEarth Das zweite Beispiel ist keine reguläre Grammatik, da es Regeln enthält, die zwei nicht-terminale Symbole aus einem einzelnen nicht-terminalen Symbol generieren, was in regulären Grammatiken nicht zulässig ist (wie OP hervorhob, enthält es auch Regeln mit mehreren nicht-terminalen Symbolen die linke). en.wikipedia.org/wiki/Regular_grammar
awwsmm
21

Die Sprachtheorie ist mit der Berechnungstheorie verwandt. Welches ist die philosophischere Seite der Informatik, über die Entscheidung, welche Programme möglich sind oder welche jemals geschrieben werden können, und welche Art von Problemen ist es unmöglich, einen Algorithmus zu schreiben, um sie zu lösen.

Ein regulärer Ausdruck beschreibt eine reguläre Sprache. Eine reguläre Sprache ist eine Sprache, die von einem deterministischen endlichen Automaten bestimmt werden kann.

Sie sollten den Artikel über Finite State Machines lesen: http://en.wikipedia.org/wiki/Finite_state_machine

Und reguläre Sprachen: http://en.wikipedia.org/wiki/Regular_language

Alle regulären Sprachen sind kontextfreie Sprachen, aber es gibt kontextfreie Sprachen, die nicht regulär sind. Eine kontextfreie Sprache ist die Menge aller Zeichenfolgen, die von einem kontextfreien Grammer oder Pushdown-Automaten akzeptiert werden, bei denen es sich um eine Finite-State-Maschine mit einem einzelnen Stapel handelt: http://en.wikipedia.org/wiki/Pushdown_automaton#PDA_and_Context-free_Languages

Es gibt kompliziertere Sprachen, für die eine Turing-Maschine (jedes mögliche Programm, das Sie auf Ihrem Computer schreiben können) erforderlich ist, um zu entscheiden, ob eine Zeichenfolge in der Sprache vorliegt oder nicht.

Die Sprachtheorie ist auch sehr verwandt mit dem P vs. NP-Problem und einigen anderen interessanten Dingen.

Meine Einführung in die Informatik im dritten Lehrjahr war ziemlich gut darin, dieses Zeug zu erklären: Einführung in die Theorie der Berechnung. Von Michael Sipser. Aber es hat mich 160 Dollar gekostet, es neu zu kaufen, und es ist nicht sehr groß. Vielleicht finden Sie eine gebrauchte Kopie oder eine Kopie in einer Bibliothek oder etwas, das Ihnen helfen könnte.

BEARBEITEN:

Die Einschränkungen von regulären Ausdrücken und höheren Sprachklassen wurden in den letzten 50 Jahren tonnenweise untersucht. Vielleicht interessiert Sie das Pumping Lemma für reguläre Sprachen. Es ist ein Mittel, um zu beweisen, dass eine bestimmte Sprache nicht regelmäßig ist:

http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages

Wenn eine Sprache nicht regulär ist, kann sie kontextfrei sein, was bedeutet, dass sie von einem kontextfreien Grammatiker beschrieben werden kann, oder sogar in einer höheren Sprachklasse. Sie können durch das Pump-Lemma für kontextfrei beweisen, dass sie nicht kontextfrei ist Sprachen, die denen für reguläre Ausdrücke ähnlich sind.

Eine Sprache kann sogar unentscheidbar sein, was bedeutet, dass selbst eine Turing-Maschine (möglicherweise kann Ihr Computer programmiert werden) nicht programmiert werden kann, um zu entscheiden, ob eine Zeichenfolge wie in der Sprache akzeptiert oder abgelehnt werden soll.

Ich denke, der Teil, an dem Sie am meisten interessiert sind, sind die Finite-State-Maschinen (sowohl deterministisch als auch deterministisch), um zu sehen, welche Sprachen ein regulärer Ausdruck entscheiden kann, und das Pump-Lemma, um zu beweisen, welche Sprachen nicht regulär sind.

Grundsätzlich ist eine Sprache nicht regulär, wenn sie eine Art Gedächtnis oder Zählfähigkeit benötigt. Die Sprache der übereinstimmenden Klammern ist beispielsweise nicht regulär, da sich die Maschine merken muss, ob sie eine Klammer geöffnet hat, um zu wissen, ob sie eine schließen muss.

Die Sprache aller Zeichenfolgen mit den Buchstaben a und b, die mindestens drei b enthalten, ist eine reguläre Sprache: a ba ba ba

Die Sprache aller Zeichenfolgen mit den Buchstaben a und b, die mehr b als a enthalten, ist nicht regulär.

Sie sollten auch nicht wissen, dass alle endlichen Sprachen regulär sind, zum Beispiel:

Die Sprache aller Zeichenfolgen mit einer Länge von weniger als 50 Zeichen unter Verwendung der Buchstaben a und b, die mehr b als a enthalten, ist regulär, da wir wissen, dass sie endlich als (b | abb | bab | bba | aabbb | ababb | beschrieben werden kann. ..) ect bis alle möglichen Kombinationen aufgelistet sind.

Paul
quelle
1
Reguläre Ausdrücke sind keine Entscheidungsprogramme, die Zeichenfolgen mit Mustern abgleichen. Sie sind Ausdrücke, die reguläre Mengen bezeichnen, für die das Mitgliedschaftsproblem entscheidbar ist.
Danportin
1
Wenn ein Set regelmäßig ist, ist es offensichtlich entscheidbar. Ich bin mir nicht sicher, wie ich es anders ausdrücken soll. Sie sind effektiv Entscheidungsprogramme, die keinen Speicher haben.
Paul
Sie beschreiben deterministische endliche Automaten, die ein Entscheidungsverfahren für reguläre Sprachen bereitstellen ("Entscheidungsprogramme ohne Speicher"). Reguläre Ausdrücke sind Begriffe , die bezeichnen reguläre Sprachen, keine Programme sind Verfahren. Dies war meine einzige Beschwerde.
Danportin
1
Ich habe es geändert in "Ein regulärer Ausdruck ist eine Art, eine reguläre Sprache zu beschreiben. Eine reguläre Sprache ist eine Sprache, die von einem deterministischen endlichen Automaten entschieden werden kann." Klingt das besser
Paul