Frage Reguläre vs. kontextfreie Grammatiken


Ich lerne für mich Computersprachen Test, und es gibt eine Idee, die ich habe Probleme, meinen Kopf herum zu wickeln.

Ich habe das verstanden reguläre Grammatiken sind einfacher und können keine Mehrdeutigkeiten enthalten, können aber nicht viele Aufgaben ausführen, die für Programmiersprachen erforderlich sind. Das habe ich auch verstanden kontextfreie Grammatiken Mehrdeutigkeit erlauben, aber einige für Programmiersprachen notwendige Dinge zulassen (wie Palindrome).

Worüber ich Schwierigkeiten habe, ist zu verstehen, wie ich all das oben genannte ableiten kann, indem ich das weiß regelmäßige Grammatik Nonterminals kann auf ein Endgerät oder ein Nicht-Endgerät, gefolgt von einem Endgerät, abgebildet werden, oder dass ein kontextfreies Nicht-Endgerät einer beliebigen Kombination von Endgeräten und Nicht-Endgeräten zugeordnet wird.

Kann mir jemand helfen, all das zusammen zu stellen?


75
2018-02-18 03:46


Ursprung


Antworten:


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

So zum Beispiel für ein Palindrom ist von der 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 als solche kein Nicht-Terminal auf beiden Seiten haben können.

Da reguläre Grammatiken nicht eindeutig sind, gibt es nur eine Produktionsregel für ein gegebenes Nicht-Terminal, wohingegen es im Fall einer kontextfreien Grammatik mehr als eins geben kann.


58
2018-02-18 05:35



Ich denke, was Sie denken wollen, sind die verschiedenen pumpenden Lemmata. Eine reguläre Sprache kann von einem endlichen Automaten erkannt werden. Eine kontextfreie Sprache erfordert einen Stapel, und eine kontextsensitive Sprache benötigt zwei Stapel (das entspricht der Aussage, dass eine vollständige Turing-Maschine erforderlich ist).

Also, wenn wir an das denken Pumping Lemma für reguläre SprachenWas es im Wesentlichen sagt, ist, dass jede reguläre Sprache in drei Teile zerlegt werden kann, x, y, und z, wo alle Instanzen der Sprache sind xy * z (wobei * Kleene Wiederholung ist, dh 0 oder mehr Kopien von y.) Sie haben grundsätzlich ein "nonterminal", das erweitert werden kann.

Nun, was ist mit kontextfreien Sprachen? Es gibt ein Analoges Pumping Lemma für kontextfreie Sprachen das bricht die Strings in der Sprache in fünf Teile, uvxyzund wo alle Instanzen der Sprache sind uvichxyichz, für i ≥ 0. Jetzt hast du zwei "nonterminals", die repliziert oder gepumpt werden können solange du die gleiche Nummer hast.


50
2018-02-18 05:36



Der Unterschied zwischen regulärer und kontextfreier Grammatik: (N, Σ, P, S): Terminals, Nonterminals, 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 Richtig reguläre Grammatik, alle Regeln folgen den Formen

  1. B → a, wobei B ein Nichtterminal in N ist und a ein Ende in Σ ist
  2. B → aC wobei B und C in N sind und a in Σ ist
  3. B → & epsi ;, wobei B in N ist und & epsi; die leere Kette bezeichnet, d. H. Die Kette der Länge 0

linke reguläre Grammatik, alle Regeln gehorchen den Formen

  1. A → a wobei A ein Nichtterminal in N ist und a ein Terminal in Σ ist
  2. A → Ba, wobei A und B in N sind und a in Σ ist
  3. A → ε wobei A in N und ε die leere Zeichenfolge ist

kontextfreie Grammatik (CFG)

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

○ V ist ein einzelnes nichtterminales Symbol

○ w ist eine Kette von Terminals und / oder Nichtterminals (w kann leer sein)


8
2018-05-13 19:29



Reguläre Ausdrücke

  • Grundlage der lexikalischen Analyse
  • Normale Sprachen darstellen

Kontextfreie Grammatiken

  • Basis des Parsens
  • Sprachkonstrukte darstellen

enter image description here


4
2018-01-16 05:07



Eine Grammatik ist kontextfrei, wenn alle Produktionsregeln die folgende 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 ein 4-Tupel definieren, wobei V eine endliche Menge (Variablen) ist, _ eine endliche Menge (Endungen) ist, S die Startvariable ist und R eine endliche Menge von Regeln ist, von denen jede eine Abbildung ist V
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 die reguläre Grammatik eine Teilmenge der kontextfreien Grammatik ist. Nach diesen Eigenschaften können wir sagen, dass kontextfreie Sprachen auch reguläre Sprachen enthalten


3
2018-06-30 15:28



Regelmäßige Grammatik: - Grammatik mit Produktion wie folgt ist RG:

V->TV or VT
V->T

wo V = Variable und T = Terminal

RG kann linke lineare Grammatik oder rechte Linergrammatik sein, aber keine mittlere lineare Grammatik.

Wie wir alle 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 einen String x gibt es mehr als ein LMD oder mehr als RMD oder mehr als einen Parse-Baum oder ein LMD und ein RMD, aber beide produzieren unterschiedliche Parse-Bäume.

                S                   S

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

Diese Grammatik ist mehrdeutig, weil zwei Grammatischer Baum.

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

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

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

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

CFL: CFI Mai oder nicht mehrdeutig.

Hinweis: RL ist niemals inhärent zweideutig.


3
2017-07-26 20:07



Im Allgemeinen 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 regelmäßige Grammatik kann mehrdeutig sein.


-1
2018-03-03 14:51



Eine reguläre Grammatik ist niemals mehrdeutig, weil sie entweder linear oder rechts linear ist, so dass wir keinen Entscheidungsbaum für reguläre Grammatoren erstellen können, so dass sie immer eindeutig ist. Aber anders als normale Grammatik sind alle regulär


-4
2018-04-21 09:46