Régulière vs grammaire non contextuelle

StackOverflow https://stackoverflow.com/questions/559763

Question

Je suis étudiant pour mon langues informatique test, et il y a une idée que je vais avoir des problèmes envelopper ma tête.

Je compris que grammaire régulière sont plus simples et ne peut contenir l'ambiguïté, mais ne peut pas faire beaucoup de tâches qui sont nécessaires pour les langages de programmation. Je compris aussi que grammaires hors contexte permettent l'ambiguïté, mais permettent certaines choses nécessaires pour les langages de programmation (comme palindromes).

Ce que je vais avoir du mal à comprendre comment est que je peux tirer de ce qui précède en sachant que nonterminals de grammaire régulière peut correspondre à un terminal ou un non-terminal suivi d'un terminal ou qu'un context- cartes gratuites à une combinaison non-terminaux de terminaux et non-terminaux.

Quelqu'un peut-il aider à me mettre tout cela ensemble?

Était-ce utile?

La solution

grammaire régulière est soit à droite ou à gauche linéaire, alors que le contexte grammaire libre est essentiellement une combinaison de terminaux et non-terminaux. Par conséquent, vous pouvez voir que la grammaire régulière est un sous-ensemble de la grammaire hors-contexte.

Donc, pour un palindrome par exemple, est de la forme, 

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

Vous pouvez voir clairement que les palindromes ne peuvent être exprimées en grammaire régulière, car il doit être linéaire droite ou à gauche et en tant que tel ne peut pas avoir des deux côtés non terminal.

Depuis grammaires régulières sont non ambiguës, il n'y a qu'une seule règle de production pour un non-terminal donné, alors il peut y avoir plus d'un dans le cas d'une grammaire hors-contexte.

Autres conseils

Je pense que ce que vous voulez penser sont les différents lemmes de pompage. Une langue régulière peut être reconnu par un automate fini. Une langue sans contexte une pile, et un langage contextuel nécessite deux piles (ce qui équivaut à dire qu'il faut une machine de Turing complète.)

Donc, si l'on pense aux pompage lemme pour les langues régulières , ce qu'il dit, essentiellement , est que toute langue régulière peut être décomposé en trois morceaux, x , y et z , où toutes les instances de la langue sont xy * z (où * est la répétition Kleene, à savoir, 0 ou plusieurs copies de y .) Vous avez essentiellement un "non-terminal" qui peut être étendu.

Maintenant, qu'en langues sans contexte? Il y a une lemme de pompage pour les langues sans contexte qui casse les chaînes dans la langue en cinq pièces, uvxyz , et où toutes les instances de la langue sont dans uv i xy i z , pour i ≥ 0. maintenant, vous avez deux "nonterminals" qui peuvent être répliquées, ou pompés, aussi longtemps que vous avez le même nombre .

La différence entre la grammaire régulière et sans contexte: (N, Σ, P, S): terminaux, non-terminaux, productions, à partir des symboles d'état de terminal

● symboles élémentaires de la langue définie par une grammaire formelle

● abc

symboles non terminaux (ou des variables syntaxiques)

● remplacés par des groupes de symboles terminaux selon les règles de production

● ABC

grammaire régulière: droite ou gauche grammaire régulière droit grammaire régulière, toutes les règles obéissent aux formes

  1. B → un où B est un non-terminal en N et est un terminal dans Σ
  2. B → aC où B et C sont en N et est dans Σ
  3. B → ε où B est N et ε désigne la chaîne vide, à savoir la chaîne de longueur 0

gauche grammaire régulière, toutes les règles obéissent aux formes

  1. A → A où A est un non-terminal en N et est un terminal dans Σ
  2. A → Ba où A et B sont en N et est dans Σ
  3. A → ε où A est N et ε est la chaîne vide

grammaire contexte libre (CFG)

○ la grammaire formelle dans laquelle toutes les règles de production est de la forme V → w

○ V est un symbole non terminal

w ○ est une chaîne de bornes et / ou des non-terminaux (w peut être vide)

Expressions rationnelles

  • Bases de l'analyse lexicale
  • Représentent langues régulières

Contexte grammaires

  • Base de l'analyse syntaxique
  • Représenter des constructions linguistiques

entrer image description ici

grammaire régulière: - grammaire contenant production comme suit est RG: 

V->TV or VT
V->T

où V = variable et T = borne

RG peut être linéaire gauche ou à droite Grammaire Liner grammaire, mais pas Moyen grammaire linéaire.

Comme nous le savons tous RG sont linéaires grammaire mais seulement à gauche ou à droite linéaire linéaire Grammar sont RG.

Une grammaire régulière peut être ambiguë. 

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

Ambigu Grammaire: -. pour une chaîne x leur existe plus d'un LMD ou Plus de RMD ou plus d'un arbre Parse ou un LMD et un RMD, mais les deux produisent différents arbre Parse 

                S                   S

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

La grammaire est grammaire ambiguë parce que deux arbre d'analyse syntaxique.

CFG: - Une grammaire dit à cfg si sa production est sous forme: 

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

DCFL: - comme nous le savons tous DCFL sont LL (1) Grammaire et tous LL (1) est LR (1) il est donc jamais ambiguë. si DCFG est jamais ambiguë.

Nous savons aussi tous les RL sont DCFL si RL ne soit ambigu. Notez que RG peut être ambiguë, mais RL pas.

CFL:. CFl ou non ambiguë

Remarque:. RL sera jamais Intrinsèquement ambigu

Une grammaire est libre de contexte si toutes les règles de production sont de la forme: A (qui est, le côté gauche d'une règle ne peut être qu'une seule variable, le côté droit est libre et peut être toute séquence de bornes et variables) . On peut définir une grammaire comme un 4-uplet où V est un ensemble fini (variables), _ est un ensemble fini (bornes), S est la variable de départ, et R est un ensemble fini de règles, dont chacune est une cartographie V
grammaire régulière est soit linéaire à droite ou à gauche, alors que le contexte grammaire libre est essentiellement une combinaison de terminaux et non-terminaux. Par conséquent, nous pouvons dire que la grammaire régulière est un sous-ensemble de la grammaire hors-contexte. Après ces propriétés, nous pouvons dire que les langues Contexte L'ensemble contient également gratuit Langues régulières définies

Fondamentalement la grammaire régulière est un sous-ensemble de la grammaire libre de contexte, mais nous ne pouvons pas dire chaque contexte grammaire libre est une grammaire régulière. Principalement la grammaire libre de contexte est ambigu et la grammaire régulière peut être ambiguë.

une Grammer régulière est jamais ambiguë, car elle est soit linéaire gauche ou à droite linéaire, de sorte que nous ne peux pas faire deux arbres de décision pour Grammer régulière de sorte qu'il est toujours unambiguous.but que la grammaire régulière Autret tous sont peut ou non être régulier

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top