Densité asymptotique de grammaires ambiguës sans contexte (CFG)

Quel est le rapport entre les CFG ambigus et tous les CFG ?

Étant donné que les deux ensembles sont infiniment dénombrables, le rapport n'est pas bien défini. Mais qu'en est-il de la densité asymptotique :

lim_{n \mapsto \infty} \frac{# ambiguous CFG of size < n}{# CFG of size < n}

$\lim_{n \mapsto \infty}\frac {\# \text{ ambiguous CFG of size} < n} {\# \text{ CFG of size} < n}$

où les symboles terminaux et non terminaux proviennent d'un ensemble dénombrable fixe.

La taille d'une grammaire est toute notion raisonnable de taille pour les grammaires, par exemple

le nombre total d'occurrences de variables et de terminaux dans les règles de production, ou
le nombre total d'occurrences de variable, ou
le nombre total de règles de production, ou
le nombre de variables distinctes.

(Je suppose que la définition de la taille n'affectera pas la réponse.)

fl.formal-languages grammars context-free user18064
la source

Soit dit en passant, les notions suivantes de taille CFG ont été prises en compte dans la littérature: En ce qui concerne les notions de taille grammaticale, les notions suivantes sont apparues dans la littérature. (1) Nombre total d'occurrences de variables et de terminaux des deux côtés de toutes les productions dans la grammaire. (2) Nombre d'occurrences variables des deux côtés de toutes les productions de la grammaire. (3) Nombre de productions dans la grammaire. (4) Nombre de variables distinctes dans la grammaire.

Martin Berger

Voir par exemple: S. Ginsburg, N. Lynch, Size Complexity in Context-Free Grammar Forms. J. Gruska, Sur la taille des grammaires hors contexte. J. Gruska, Complexity and Unambiguity of Context-Free Grammars and Languages. A. Kelemenova, Complexité des grammaires de forme normale.

Martin Berger

@Martin, si l'on ne fait pas attention, il peut y avoir une infinité de grammaires syntaxiquement différentes d'une taille donnée et le rapport n'aura pas de sens. Le moyen sûr est de compter la longueur en bits de certains codages fixes de grammaires.

Kaveh

Vous voulez probablement définir la densité asymptotique comme le rapport des logarithmes des quantités respectives, car les deux quantités sont exponentielles, probablement avec des bases différentes.

mobius dumpling

@MartinBerger En supposant que nous parlons de la même chose, c'est-à-dire de définir , cela affecterait évidemment la densité. Supposons que le nombre de CFG sans ambiguïté soit de et le nombre de CFG de , alors la densité de log est tandis que la densité asymptotique est de 0. Je suis assez sûr que la densité asymptotique sera soit 0, soit 1, mais la densité logarithmique asymptotique est probablement un nombre intéressant.

l o g d e n s i t y = l o g (# u n a m b i g u o u s C F G s) / l o g (# C F G s)

$logdensity = log(\#unambiguousCFGs) / log(\#CFGs)$

{1.5}^{n}

$1.5^n$

2^{n}

$2^n$

l o g_{1.5} 2

$log_{1.5} 2$

mobius dumpling

Réponses:

La question dépend du codage exact. Cependant, il semble que dans de nombreux codages raisonnables, comme la longueur tend vers l'infini, le nombre de règles de production (pour une interprétation appropriée du symbole de départ et du terminal ) sera plus d'un avec une probabilité élevée; ici, je veux dire littéralement le même terminal . Si nous considérons cela comme une ambiguïté, je m'attends à ce que "la plupart" des grammaires soient ambiguës. On peut également concocter des situations similaires telles que les règles et chacune apparaissant au moins une fois. $S\to a$ $S$ $a$ $a$ $S\to S$ $S\to a$

En supposant cette hypothèse générale, que chaque règle concevable (fixe) devrait apparaître avec une forte probabilité que la longueur tend vers l'infini, nous constatons que "la plupart" des grammaires génèrent de manière ambiguë. $\Sigma^*$

Par exemple, considérons l'encodage suivant pour les grammaires sur . L'alphabet grammatical est composé des symboles . Les non-terminaux sont indexés par des chaînes binaires d'une longueur d'au moins 2. Les règles sont séparées par des points. Chaque règle est une séquence de chaînes binaires séparées par des points-virgules. La première chaîne binaire est le non-terminal sur le côté gauche, et le reste (le cas échéant) constitue le côté droit; si la première chaîne binaire n'est pas un non-terminal (c'est-à-dire , 0,1), alors le non-terminal de départ est supposé. Le non-terminal de départ est toujours 00. $\Sigma = \{0,1\}$ $\{0,1,;,.\}$ $\epsilon$

Sous cet encodage, chaque chaîne de Décrit une grammaire. Une grammaire aléatoire contiendra très probablement de nombreuses copies deet, et en particulier sera ambigu. $\{0,1,;,.\}^*$ $.00;00.$ $.00;0.$

Yuval Filmus
la source

Oui, je considère comme valides des règles telles que et (apparaissant plus d'une fois) dans une grammaire. En effet, cela rend une grammaire trivialement ambiguë. À votre santé.

S \to S

$S\to S$

S \to a

$S\to a$

user18064

Mais n'est-ce pas également le cas que, à mesure que la taille (CFG) augmente, le nombre de terminaux et de non-terminaux augmente généralement, nous avons donc besoin de plus de bits pour les représenter, donc nous avons besoin de plus de bits pour représenter les règles individuelles. Ainsi, le nombre de CFG qui ne sont pas ambigus pour des raisons triviales (par exemple une seule règle s'inscrit dans la limite de taille) augmente également.

Martin Berger

@Martin Cela dépend de l'encodage. Vous pouvez peut-être trouver un codage à l'appui de votre revendication, par exemple si la taille de l'alphabet augmente avec la taille de la grammaire. Mon encodage utilise une taille d'alphabet constante, donc cet effet ne se produit pas.

Yuval Filmus

@MartinBerger C'est un point valable sur l'augmentation du nombre de symboles terminaux et non terminaux lorsque nous augmentons la taille de la grammaire. Pour les cas d'utilisation tels que les langages de programmation, cela a du sens.

user18064

@ user18064 Les langages de programmation utilisent généralement un alphabet de taille constante, dans la plupart des cas un sous-ensemble d'ASCII. Je ne connais aucune langue pratique avec une taille d'alphabet illimitée, bien que l'on puisse facilement les définir.

Yuval Filmus