Regelmäßige vs kontextfreie Grammatiken

96

Ich lerne für meinen Computersprachtest und es gibt eine Idee, bei der ich Probleme habe, meinen Kopf herumzuwickeln.

Ich habe verstanden, dass reguläre Grammatiken einfacher sind und keine Mehrdeutigkeiten enthalten können, aber nicht viele Aufgaben erledigen können, die für Programmiersprachen erforderlich sind. Ich habe auch verstanden, dass kontextfreie Grammatiken Mehrdeutigkeiten zulassen, aber einige Dinge berücksichtigen, die für Programmiersprachen erforderlich sind (wie Palindrome).

Ich habe Probleme damit zu verstehen, wie ich all das ableiten kann, indem ich weiß, dass reguläre Grammatik-Nichtterminale einem Terminal oder einem Nichtterminal gefolgt von einem Terminal zugeordnet werden können oder dass ein kontextfreies Nichtterminal einer beliebigen Kombination von Terminals und Nichtterminalen zugeordnet werden kann .

Kann mir jemand helfen, das alles zusammenzustellen?

context-free-grammar regular-language automata Jason Baker
quelle

70

Die reguläre Grammatik ist entweder rechts oder links linear, während die kontextfreie Grammatik grundsätzlich eine beliebige Kombination von Terminals und Nicht-Terminals ist. Daher können Sie sehen, dass die reguläre Grammatik eine Teilmenge der kontextfreien Grammatik ist.

So ist zum Beispiel für ein Palindrom die Form,

S->ABA
A->something
B->something

Sie können deutlich sehen, dass Palindrome nicht in regulärer Grammatik ausgedrückt werden können, da sie entweder rechts oder links linear sein müssen und daher nicht auf beiden Seiten ein Nicht-Terminal haben können.

Da reguläre Grammatiken nicht mehrdeutig sind, gibt es nur eine Produktionsregel für ein bestimmtes Nicht-Terminal, während es bei einer kontextfreien Grammatik mehr als eine geben kann.

Sujoy
quelle

13

Erstens: Regelmäßige Grammatiken können mehrdeutig sein (Beispiel von Kai Kuchenbecker: S -> aA | aB, B -> a, A -> a). Das einzige ist, dass es nur eine Möglichkeit gibt, die Knoten im Syntaxbaum zu positionieren (zum Beispiel besteht die Assoziativitätsmehrdeutigkeit nicht, wenn eine reguläre Grammatik verwendet wird). Zweitens: Ein Nicht-Terminal kann mehr als eine rechte Seite haben (A -> a, A -> aA; und Wikipedia enthält sogar epsilon als dritte Alternative: en.wikipedia.org/wiki/Regular_grammar )

user764754

1

Mehrdeutigkeit entsteht, wenn ein Satz in mehr als einem Ableitungspfad aus Ihrer Grammatik abgeleitet werden kann. Nur mehr als eine Produktionsregel für ein Nicht-Terminal zu haben, macht die Grammatik nicht mehrdeutig

Sujoy

11

Dieses Beispiel ist eigentlich falsch. Wenn wir uns die vollständigen Regeln vorstellen A-> a | cund B->bdann erlaubt diese Grammatik Nicht-Palindrome. Zum Beispiel könnte ich produzieren : S->ABA->aBA->abA->abc. Das Problem ist, dass wir in der ersten Regel nicht zwei Variablen erzeugen wollen, sondern zwei Terminals. Eine Möglichkeit für eine Grammatik, die Palindrome erlaubt, ist:S -> aSa | bSb | a | b

gdiazc

Es gibt Palindrome, die in einer regulären Grammatik ausgedrückt werden können : die Palindrome, die aus einem einzelnen Zeichen bestehen. Zum Beispiel S -> aSa | eund a(aa)*abeide beschreiben eine reguläre Sprache. Dies zeigt, dass eine CFG eine reguläre Sprache beschreiben kann, selbst wenn sie die linke oder rechte Linearität verletzt. Zugegeben, dies ist ein nicht so offensichtliches Palindrom.

Martijn

Kommen Sie und denken Sie darüber nach, diese Antwort ist tatsächlich falsch. Es heißt, "kontextfreie" Grammatik sei im Grunde eine beliebige Kombination von Terminals und Nicht-Terminals. "Tu ^ nvw ^ mxy ^ kz ist jedoch eine Kombination von Terminals und Nicht-Terminals, aber nicht kontextfrei.

Charlie Martin

58

Ich denke, woran Sie denken möchten, sind die verschiedenen pumpenden Lemmata. Eine reguläre Sprache kann von einem endlichen Automaten erkannt werden. Für eine kontextfreie Sprache ist ein Stapel erforderlich, und für eine kontextsensitive Sprache sind zwei Stapel erforderlich (was bedeutet, dass eine vollständige Turing-Maschine erforderlich ist).

Wenn wir also über das Pump-Lemma für reguläre Sprachen nachdenken , heißt es im Wesentlichen, dass jede reguläre Sprache in drei Teile zerlegt werden kann, x , y und z , wobei alle Instanzen der Sprache in xy * z sind (wobei * Kleene-Wiederholung ist, dh 0 oder mehr Kopien von y .) Sie haben im Grunde ein "Nicht-Terminal", das erweitert werden kann.

Was ist nun mit kontextfreien Sprachen? Es gibt ein analoges Pump-Lemma für kontextfreie Sprachen , das die Zeichenfolgen in der Sprache in fünf Teile aufteilt , uvxyz , und in denen alle Instanzen der Sprache in uv ⁱ xy ⁱ z für i ≥ 0 sind. Jetzt haben Sie zwei "Nichtterminale" "das kann repliziert oder gepumpt werden, solange Sie die gleiche Nummer haben .

Charlie Martin
quelle

10

Eine kontextsensitive Sprache erfordert keine vollständige Turing-Maschine. Ein linear begrenzter Automat ist ausreichend. Dies ist eine Turing-Maschine, deren Band endlich ist. Die Größe wird durch eine lineare Funktion in der Eingabezeichenfolge begrenzt.

Dave Clarke

16

Der Unterschied zwischen regulärer und kontextfreier Grammatik: (N, Σ, P, S): Terminals, Nicht-Terminals, Produktionen, Startzustand Terminalsymbole

● elementare Symbole der Sprache, die durch eine formale Grammatik definiert sind

● abc

Nichtterminale Symbole (oder syntaktische Variablen)

● ersetzt durch Gruppen von Terminalsymbolen gemäß den Produktionsregeln

● ABC

reguläre Grammatik: rechte oder linke reguläre Grammatik rechte reguläre Grammatik, alle Regeln gehorchen den Formen

B → a wobei B ein Nichtterminal in N und a ein Terminal in Σ ist
B → aC wobei B und C in N und a in Σ sind
B → ε wobei B in N ist und ε die leere Zeichenkette bezeichnet, dh die Zeichenkette der Länge 0

links reguläre Grammatik, alle Regeln gehorchen den Formen

A → a wobei A ein Nichtterminal in N und a ein Terminal in Σ ist
A → Ba wobei A und B in N und a in Σ sind
A → ε wobei A in N ist und ε die leere Zeichenkette ist

kontextfreie Grammatik (CFG)

○ formale Grammatik, in der jede Produktionsregel die Form V → w hat

○ V ist ein einzelnes nichtterminales Symbol

○ w ist eine Folge von Terminals und / oder Nicht-Terminals (w kann leer sein)

stringRay2014
quelle

5

Regelmäßige Grammatik: - Grammatik, die folgende Produktion enthält, ist RG:

V->TV or VT
V->T

wobei V = variabel und T = terminal

RG kann eine linke lineare Grammatik oder eine rechte lineare Grammatik sein, jedoch keine mittlere lineare Grammatik.

Wie wir wissen, sind alle RG lineare Grammatik, aber nur linke lineare oder rechte lineare Grammatik sind RG.

Eine reguläre Grammatik kann mehrdeutig sein.

S->aA|aB
A->a
B->a

Mehrdeutige Grammatik: - Für eine Zeichenfolge x gibt es mehr als eine LMD oder mehr als RMD oder mehr als einen Analysebaum oder eine LMD und eine RMD, aber beide erzeugen unterschiedliche Analysebäume.

                S                   S

              /   \               /   \
             a     A             a     B
                    \                   \
                     a                   a

Diese Grammatik ist mehrdeutige Grammatik, weil zwei Baum analysieren.

CFG: - Eine Grammatik, die als CFG bezeichnet wird, wenn ihre Produktion in Form ist:

   V->@   where @ belongs to (V+T)*

DCFL: - Wie wir wissen, sind alle DCFL LL (1) Grammatik und alle LL (1) ist LR (1), also ist es niemals mehrdeutig. DCFG ist also niemals mehrdeutig.

Wir wissen auch, dass alle RL DCFL sind, so dass RL niemals mehrdeutig ist. Beachten Sie, dass RG möglicherweise nicht eindeutig ist, RL jedoch nicht.

CFL: CFl Kann oder kann nicht mehrdeutig sein.

Hinweis: RL ist niemals inhärent mehrdeutig.

Dean Meehan
quelle

4

Reguläre Ausdrücke

Grundlage der lexikalischen Analyse
Repräsentieren Sie reguläre Sprachen

Kontextfreie Grammatiken

Basis der Analyse
Sprachkonstrukte darstellen

Geben Sie hier die Bildbeschreibung ein

Ahmed Salem
quelle

Nein, das ist eine kurze Beschreibung, bitte lesen Sie noch einmal und überprüfen Sie das Bild.

Ahmed Salem

3

Eine Grammatik ist kontextfrei, wenn alle Produktionsregeln die Form haben: A (dh die linke Seite einer Regel kann nur eine einzelne Variable sein; die rechte Seite ist uneingeschränkt und kann eine beliebige Folge von Terminals und Variablen sein). Wir können eine Grammatik als 4-Tupel definieren, wobei V eine endliche Menge (Variablen), _ eine endliche Menge (Terminals), S die Startvariable und R eine endliche Menge von Regeln ist, von denen jede eine Abbildung ist Die
reguläre Grammatik ist entweder rechts oder links linear, während die kontextfreie Grammatik grundsätzlich eine beliebige Kombination von Terminals und Nicht-Terminals ist. Daher können wir sagen, dass reguläre Grammatik eine Teilmenge der kontextfreien Grammatik ist. Nach diesen Eigenschaften können wir sagen, dass das Set Context Free Languages auch das Set Regular Languages enthält

Wafiullah NAeemzi Afghan
quelle

-1

Grundsätzlich ist reguläre Grammatik eine Teilmenge der kontextfreien Grammatik, aber wir können nicht sagen, dass jede kontextfreie Grammatik eine reguläre Grammatik ist. Hauptsächlich kontextfreie Grammatik ist mehrdeutig und reguläre Grammatik kann mehrdeutig sein.

Babita Mehra
quelle

-4

Ein reguläres Grammatikprogramm ist niemals mehrdeutig, da es entweder linkslinear oder rechtslinear ist. Daher können wir für zwei reguläre Grammatiker keine zwei Entscheidungsbäume erstellen, sodass es immer eindeutig ist. Abgesehen von der regulären Grammatik können alle regulär sein oder nicht

Dinesh
quelle

4

@dinesh Eine reguläre Grammatik kann mehrdeutig sein. Denken Sie daran, dass eine Grammatik nicht eindeutig ist, wenn zwei verschiedene Syntaxbäume vorhanden sind und dass ein Syntaxbaum beschriftet ist. Daher sind isomorphe Bäume verschiedene Bäume. Dh eine einfache Grammatik wie S -> aA | aB, B -> a, A -> a ist mehrdeutig, da für das Wort 'aa' zwei Syntaxbäume existieren, die isomorph, aber unterschiedlich sind.

Kai Kuchenbecker

Regelmäßige vs kontextfreie Grammatiken

Antworten: