Question Grammaires régulières et sans contexte


J'étudie pour mon langages informatiques test, et il y a une idée que j'ai des problèmes à me casser la tête.

J'ai compris ça grammaires régulières sont plus simples et ne peuvent contenir aucune ambiguïté, mais ne peuvent pas effectuer beaucoup de tâches requises pour les langages de programmation. J'ai aussi compris que grammaires sans contexte permettre l'ambiguïté, mais autoriser certaines choses nécessaires pour les langages de programmation (comme les palindromes).

Ce qui me pose problème, c'est de comprendre comment je peux tirer tout ce qui précède en sachant que non-grammaire régulière peut mapper vers un terminal ou un terminal non suivi d'un terminal ou qu'un terminal non contextuel correspond à n'importe quelle combinaison de terminaux et de terminaux.

Est-ce que quelqu'un peut m'aider à mettre tout cela ensemble?


75
2018-02-18 03:46


origine


Réponses:


La grammaire régulière est linéaire ou droite, alors que la grammaire sans contexte est essentiellement une 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 clairement voir que les palindromes ne peuvent pas être exprimés en grammaire régulière car ils doivent être linéaires à droite ou à gauche et ne peuvent donc pas avoir un côté non terminal des deux côtés.

Les grammaires régulières étant non ambiguës, il existe une seule règle de production pour un non-terminal donné, alors qu'il peut en exister plusieurs dans le cas d'une grammaire sans contexte.


58
2018-02-18 05:35



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 Turing complète).

Donc, si nous pensons à la pompage du lemme pour les langues régulières, ce qui est dit, essentiellement, est que tout langage courant peut être divisé en trois parties, X, y, et z, où toutes les instances de la langue sont dans xy * z (où * est la répétition de Kleene, c.-à-d. 0 ou plusieurs copies de y.) Vous avez fondamentalement un "non-terminal" qui peut être étendu.

Maintenant, qu'en est-il des langages sans contexte? Il y a un analogue pompage du lemme pour les langages sans contexte qui brise les chaînes dans la langue en cinq parties, uvxyz, et où toutes les instances de la langue sont dans uvjexyjez, pour i ≥ 0. Maintenant, vous avez deux "non étroits" pouvant être répliqués ou pompés, tant que vous avez le même numéro.


50
2018-02-18 05:36



La différence entre la grammaire régulière et sans grammaire: (N, Σ, P, S): terminaux, non terminaux, productions, état initial

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

● abc

Symboles non terminaux (ou variables syntaxiques)

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

● ABC

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

  1. B → a où B est un nonterminal dans N et a est un terminal dans Σ
  2. B → aC où B et C sont en N et a est en Σ
  3. B → ε où B est dans N et ε désigne la chaîne vide, c'est-à-dire 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 nonterminal dans N et a est un terminal dans Σ
  2. A → Ba où A et B sont dans N et a est dans Σ
  3. A → ε où A est dans N et ε est la chaîne vide

grammaire sans contexte (CFG)

○ grammaire formelle dans laquelle chaque règle de production est de la forme V → w

○ V est un symbole unique non terminal

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


8
2018-05-13 19:29



Expressions régulières

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

Grammars sans contexte

  • Base d'analyse
  • Représenter des constructions de langage

enter image description here


4
2018-01-16 05:07



Une grammaire est dépourvue de contexte si toutes les règles de production ont la forme suivante: A (le côté gauche d'une règle ne peut être qu'une seule variable; le côté droit est illimité et peut être n'importe quelle séquence de terminaux et de variables). On peut définir une grammaire comme un 4-tuple 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, chacune étant un mappage V
la grammaire régulière est linéaire ou droite, alors que la grammaire sans contexte est essentiellement une combinaison de terminaux et de non-terminaux. On peut donc 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 l'ensemble des langues libres de contexte contient également un ensemble de langues régulières.


3
2018-06-30 15:28



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

V->TV or VT
V->T

où V = variable et T = terminal

RG peut être une grammaire linéaire gauche ou droite, mais pas une grammaire linéaire.

Comme nous le savons, tous les RG sont des grammaires linéaires, mais seules les grammaires linéaires gauche et droite sont RG.

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

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

Grammaire Ambiguë: - pour une chaîne x, ils existent plus d'un LMD ou Plus qu'un RMD ou Plus d'un arbre d'analyse ou Un LMD et un RMD mais les deux produisent un arbre d'analyse différent.

                S                   S

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

cette grammaire est ambiguë grammaticale parce que deux analysent l'arbre.

CFG: -  Une grammaire dite CFG si sa production est en forme:

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

DCFL:- comme nous le savons, tous les DCFL sont LL (1) La grammaire et tous les LL (1) sont LR (1), donc il ne faut jamais être ambigu. Donc DCFG n'est jamais ambigu.

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

CFL: CFl Mai ou peut ne pas être ambigu.

Remarque: RL ne soit jamais intrinsèquement ambigu.


3
2017-07-26 20:07



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


-1
2018-03-03 14:51



un grammer normal n'est jamais ambigu car il est soit linéaire linéaire, soit linéaire, donc nous ne pouvons pas faire deux arbres de décision pour un grammer normal, donc il est toujours sans ambiguïté.


-4
2018-04-21 09:46