Grammaires régulières ou sans contexte

97

J'étudie pour mon test de langage informatique , et il y a une idée qui me pose des problèmes.

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

Ce que j'ai du mal à comprendre, c'est de comprendre comment je peux dériver tout ce qui précède en sachant que les non - terminaux de grammaire régulière peuvent mapper vers un terminal ou un non-terminal suivi d'un terminal ou qu'un non-terminal sans contexte correspond à n'importe quelle combinaison de terminaux et de non-terminaux. .

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

context-free-grammar regular-language automata Jason Baker
la source

Réponses:

70

La grammaire régulière est linéaire à droite ou à gauche, tandis 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 de non-terminal des deux côtés.

Les grammaires régulières n'étant pas 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 plusieurs dans le cas d'une grammaire sans contexte.

Sujoy
la source
13
Premièrement: les grammaires régulières peuvent être ambiguës (exemple de Kai Kuchenbecker: S -> aA | aB, B -> a, A -> a). La seule chose est qu'il n'y a qu'une seule façon de positionner les nœuds dans l'arbre de syntaxe (par exemple, l'ambiguïté d'associativité n'existe pas lorsqu'une grammaire régulière est utilisée). Deuxièmement: il peut y avoir plus d'un côté droit à un non-terminal (A -> a, A -> aA; et wikipedia inclut même epsilon comme troisième alternative: en.wikipedia.org/wiki/Regular_grammar )
user764754
1
L'ambiguïté survient lorsqu'une phrase peut être dérivée de votre grammaire dans plus d'un chemin de dérivation. le simple fait d'avoir plus d'une règle de production pour un non-terminal ne rend pas la grammaire ambiguë
Sujoy
11
Cet exemple est en fait faux. Si nous imaginons les règles complètes A-> a | cet que B->bcette grammaire autorise les non-palindromes. Par exemple, je pourrais produire: S->ABA->aBA->abA->abc. Le problème est que nous ne voulons pas produire deux variables dans la première règle, mais plutôt deux terminaux. Une possibilité pour une grammaire qui autorise les palindromes est:S -> aSa | bSb | a | b
gdiazc
Il existe des palindromes qui peuvent être exprimés dans une grammaire régulière: les palindromes constitués d'un seul caractère. Par exemple, S -> aSa | eet les a(aa)*adeux décrivent une langue ordinaire. Cela montre qu'un CFG peut décrire un langage régulier, même s'il viole la linéarité gauche ou droite. Certes, c'est un palindrome pas si évident.
Martijn
À bien y penser, cette réponse est en fait fausse. Il dit que la grammaire "sans contexte" est essentiellement une combinaison de terminaux et de non-terminaux. "Cependant, tu ^ nvw ^ mxy ^ kz est une combinaison de terminaux et de non-terminaux, mais pas sans contexte.
Charlie Martin
58

Je pense que ce à quoi vous voulez penser, ce 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 sensible au contexte nécessite deux piles (ce qui équivaut à dire qu'il nécessite une machine de Turing complète.)

Donc, si nous pensons au lemme de pompage pour les langues régulières , ce qu'il dit, essentiellement, c'est que toute langue régulière peut être décomposée en trois parties, x , y et z , où toutes les instances du langage sont en xy * z (où * est la répétition de Kleene, c'est-à-dire 0 ou plusieurs copies de y .) Vous avez fondamentalement un "non terminal" qui peut être développé.

Maintenant, qu'en est-il des langages sans contexte? Il existe un lemme de pompage analogue pour les langages sans contexte qui divise les chaînes du langage en cinq parties, uvxyz , et où toutes les instances du langage sont en uv i xy i z , pour i ≥ 0. Maintenant, vous avez deux "non-terminaux" "qui peut être répliqué, ou pompé, tant que vous avez le même nombre .

Charlie Martin
la source
10
Un langage sensible au contexte ne nécessite pas une machine de Turing complète. Un automate linéaire borné suffit. Il s'agit d'une machine de Turing dont la bande est finie, la taille est limitée par une fonction linéaire sur la chaîne d'entrée.
Dave Clarke
16

La différence entre la grammaire régulière et sans contexte: (N, Σ, P, S): terminaux, non-terminaux, productions, état de départ Symboles terminaux

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

● abc

Symboles non terminaux (ou variables syntaxiques)

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

● ABC

grammaire régulière: grammaire régulière droite ou gauche 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 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 non terminal 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 toute règle de production est de la forme V → w

○ V est un seul symbole non terminal

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

stringRay2014
la source
5

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 la Grammaire Linéaire Gauche ou la Grammaire Liner Droite, mais pas la Grammaire Linéaire Moyenne.

Comme nous le savons, tous les RG sont de la grammaire linéaire, mais seule la grammaire linéaire gauche ou droite est RG.

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

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

Grammaire ambiguë: - pour une chaîne x, il existe plus d'un LMD ou plus de RMD ou plus d'un arbre d'analyse ou un LMD et un RMD mais tous deux produisent un arbre d'analyse différent.

                S                   S

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

cette grammaire est une grammaire ambiguë parce que deux arbres d'analyse.

CFG: - Une grammaire dite CFG si sa Production est sous forme:

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

DCFL: - comme nous le savons, tous les DCFL sont LL (1) Grammar et tous LL (1) sont LR (1) donc ce n'est jamais ambigu. donc DCFG n'est jamais ambigu.

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

CFL: CFl Peut ou non ambigu.

Remarque: RL ne doit jamais être intrinsèquement ambigu.

Dean Meehan
la source
4

Expressions régulières

  • Base de l'analyse lexicale
  • Représenter les langues régulières

Grammaires sans contexte

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

entrez la description de l'image ici

Ahmed Salem
la source
Non, c'est une brève description, veuillez relire et vérifier l'image.
Ahmed Salem le
3

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 est illimité 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 La
grammaire régulière V est linéaire à droite ou à gauche, tandis que la grammaire sans contexte est essentiellement une 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 l'ensemble de langues sans contexte contient également l'ensemble de langues régulières

Wafiullah NAeemzi Afghan
la source
-1

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

Babita Mehra
la source
-4

une grammaire régulière n'est jamais ambiguë car elle est soit linéaire à gauche, soit linéaire à droite, nous ne pouvons donc pas faire d'arbre de décision à deux pour la grammaire régulière, donc elle est toujours sans ambiguïté, mais à part la grammaire régulière, tous peuvent ou non être réguliers

dinesh
la source
4
@dinesh Une grammaire régulière peut être ambiguë. Rappelons qu'une grammaire est ambiguë s'il existe deux arbres syntaxiques différents et qu'un arbre syntaxique est étiqueté. Par conséquent, les arbres isomorphes sont des arbres différents. C'est à dire une grammaire simple comme S -> aA | aB, B -> a, A -> a est ambigu car il existe deux arbres syntaxiques pour le mot 'aa' qui sont isomorphes mais différents.
Kai Kuchenbecker