Grammaires régulières vs Context

Question

J'étudie pour mes les langages informatiques test, et il y a une idée que j'ai des problèmes pour envelopper ma tête.

J'ai compris que grammaires régulières sont plus simples et ne peuvent pas contenir d'ambiguïté, mais ne peuvent pas faire beaucoup de tâches qui sont nécessaires pour les langages de programmation. J'ai également compris que grammaires contextuelles permettent l'ambiguïté, mais permettent certaines choses nécessaires pour les langages de programmation (comme les palindromes).

Ce que je vais avoir du mal à se comprendre comment 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 des cartes non terminaux sans contexte toute combinaison de terminaux et de non-terminaux.

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

Answer 1

La grammaire régulière est droite ou gauche linéaire, alors que la grammaire sans contexte est fondamentalement n'importe quelle combinaison de terminaux et de non-terminaux. Par conséquent, vous pouvez voir que la grammaire régulière est un sous-ensemble de la grammaire sans 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 soit à droite ou à gauche linéaire et en tant que telle ne peut pas avoir un non-terminal des deux côtés. Comme les 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 qu'il peut y en avoir plus d'une dans le cas d'une grammaire sans contexte.

Answer 2

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

Donc, si l'on considère le pumping lemma for regular languages, 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 en xy * z (où * est la répétition Kleene, à savoir, 0 ou plus de copies de et.) Vous avez essentiellement un "non-terminal" qui peut être étendu.

Maintenant, concernant les langues sans contexte? Il y a un analogue pumping lemma for context-free languages qui brise les chaînes dans la langue en cinq parties, uvxyz, et où toutes les instances de la langue sont uv ⁱ xy ⁱ 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.

Answer 3

une Grammer régulière est jamais ambiguë, car elle est soit linéaire gauche ou à droite linéaire, de sorte que nous ne pouvons pas faire deux arbres de décision pour Grammer régulière de sorte qu'il est toujours sans ambiguïté.mais une grammaire autre que la grammaire ordinaire est ou peut ne pas être régulière

Answer 4

Une grammaire est sans contexte si toutes les règles de production ont la forme: A (c'est-à-dire que le côté gauche d'une règle ne peut être qu'une seule variable; le côté droit n'est pas restreint et peut être n'importe quelle séquence de terminaux et de variables). Nous pouvons définir une grammaire comme un 4-tuple où V est un ensemble fini (variables), _ est un ensemble fini (terminaux), S est la variable de départ, et R est un ensemble fini de règles, dont chacune est un Mappage V
grammaire régulière est droite ou gauche linéaire, alors que la grammaire sans contexte est fondamentalement toute combinaison de terminaux et de non-terminaux. par conséquent, nous pouvons dire que la grammaire régulière est un sous-ensemble de la grammaire sans contexte. Après ces propriétés, nous pouvons dire que Contexte Gratuit Langues L'ensemble contient également des langues régulières définies

Answer 5

Regular Expressions

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

Contexte grammaires

• Base d'analyse
• Représentez langage construit

Answer 6

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

Answer 7

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 gauche linéaire grammaire ou droite Liner grammaire, mais pas Grammaire linéaire moyenne. Comme nous le savons tous les RG sont la grammaire linéaire mais seulement la grammaire linéaire gauche ou droite 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 existence plus d'un ou plus de DMT RMD ou plus d'un arbre ou un Parse et un RMD LMD, mais à la fois produire différents arbres de Parse.

   S     S 

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

cette grammaire est ambigu grammaire car deux analyser l'arbre.

CFG: - Une grammaire dit être 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) donc il n'est jamais ambigu. DCFG n'est jamais ambigu.

Nous savons également que tous les RL sont DCFL donc RL ne sont jamais ambigus. Notez que RG peut être ambigu mais pas RL.

CFL: CFl Peut être ambigu ou non.

Remarque: RL n'est jamais ambiguë inhérente.

Answer 8

La différence entre la grammaire régulière et sans contexte: (N, Σ, P, S): terminaux, nonterminals, productions, état à partir des symboles Terminal

● symboles élémentaires de la langue définie par un officiel grammaire

● abc

symboles non terminaux (ou variables syntaxiques)

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

● ABC

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

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

grammaire régulière gauche, 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 a est dans Σ
3. a → ε où: a est N et ε est la chaîne vide

contexte grammaire libre (CFG)

○ 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 terminaux et/ou non terminaux (w peut être vide)