Densidad asintótica de gramáticas ambiguas libres de contexto (CFG)

¿Cuál es la proporción de CFG ambiguos a todos los CFG ?

Como ambos conjuntos son infinitamente contables, la relación no está bien definida. Pero qué pasa con la densidad asintótica :

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}$

donde los símbolos terminales y no terminales provienen de un conjunto contable fijo.

El tamaño de una gramática es cualquier noción razonable de tamaño para las gramáticas, p. Ej.

el número total de ocurrencias de variables y terminales en las reglas de producción, o
el número total de ocurrencias de variable, o
el número total de reglas de producción, o
El número de variables distintas.

(Supongo que la definición de tamaño no afectará la respuesta).

fl.formal-languages grammars context-free usuario18064
fuente

Por otro lado, las siguientes nociones de tamaño de CFG se han considerado en la literatura: En cuanto a las nociones de tamaño de la gramática, las siguientes han aparecido en la literatura. (1) Número total de ocurrencias de variables y terminales en ambos lados de todas las producciones en la gramática. (2) Número de ocurrencias variables en ambos lados de todas las producciones en la gramática. (3) Número de producciones en la gramática. (4) Número de variables distintas en la gramática.

Martin Berger

Véase, por ejemplo: S. Ginsburg, N. Lynch, Complejidad de tamaño en formularios de gramática sin contexto. J. Gruska, Sobre el tamaño de las gramáticas libres de contexto. J. Gruska, Complejidad y falta de ambigüedad de las gramáticas y lenguajes sin contexto. A. Kelemenova, Complejidad de las gramáticas de forma normal.

Martin Berger

@ Martin, si uno no tiene cuidado, puede haber infinitas gramáticas sintácticamente diferentes de un tamaño determinado y la relación no tendrá sentido. La forma segura es contar la longitud de bits de alguna codificación fija de gramáticas.

Kaveh

Probablemente desee definir la densidad asintótica como la relación de logaritmos de las cantidades respectivas, ya que ambas cantidades son exponenciales, probablemente con bases diferentes.

mobius dumpling

@MartinBerger Suponiendo que estamos hablando de lo mismo, es decir, definir , esto obviamente afectaría la densidad. Suponga que el número de CFG no ambiguos es el número de CFG es , entonces la densidad es mientras que la densidad asintótica es 0. Estoy bastante seguro de que la densidad asintótica será 0 o 1, pero la densidad logarítmica asintótica probablemente sea un número interesante.

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

Respuestas:

La pregunta depende de la codificación exacta. Sin embargo, parece que en muchas codificaciones razonables, ya que la longitud tiende al infinito, el número de reglas de producción (para una interpretación adecuada del símbolo de inicio y el terminal ) será más de uno con alta probabilidad; aquí literalmente me refiero a la misma terminal . Si consideramos esto como ambigüedad, entonces espero que "la mayoría" de las gramáticas sean ambiguas. También podemos inventar situaciones similares, como las reglas y cada aparezca al menos una vez. $S\to a$ $S$ $a$ $a$ $S\to S$ $S\to a$

Suponiendo esta hipótesis general, que cada regla concebible (fija) debe aparecer con alta probabilidad ya que la longitud tiende al infinito, encontramos que "la mayoría" de las gramáticas generan de manera ambigua. $\Sigma^*$

Como ejemplo, considere la siguiente codificación para gramáticas sobre . El alfabeto gramatical consiste en los símbolos . Los no terminales están indexados por cadenas binarias de longitud de al menos 2. Las reglas están separadas por puntos. Cada regla es una secuencia de cadenas binarias separadas por punto y coma. La primera cadena binaria es la no terminal en el lado izquierdo, y el resto (si lo hay) constituye el lado derecho; si la primera cadena binaria no es un no terminal (es decir, es , 0,1), entonces se asume el no terminal inicial. El inicio no terminal es siempre 00. $\Sigma = \{0,1\}$ $\{0,1,;,.\}$ $\epsilon$

Bajo esta codificación, cada cadena en Describe alguna gramática. Una gramática aleatoria con alta probabilidad contendrá muchas copias dey, y en particular será ambiguo. $\{0,1,;,.\}^*$ $.00;00.$ $.00;0.$

Yuval Filmus
fuente

Sí, considero que reglas como y (que aparecen más de una vez) en una gramática son válidas. De hecho, esto hace que una gramática sea trivialmente ambigua. Salud.

S \to S

$S\to S$

S \to a

$S\to a$

user18064

Pero no es también el caso de que, a medida que aumenta el tamaño (CFG), el número de terminales y no terminales generalmente aumenta, por lo que necesitamos más bits para representarlos, por lo tanto, necesitamos más bits para representar reglas individuales. Por lo tanto, también aumenta el número de CFG que no son ambiguos por razones triviales (por ejemplo, solo una regla se ajusta al límite de tamaño).

Martin Berger

@ Martin Depende de la codificación. Quizás pueda encontrar una codificación que respalde su reclamo, por ejemplo, si el tamaño del alfabeto crece con el tamaño de la gramática. Mi codificación usa un tamaño de alfabeto constante, por lo que este efecto no ocurre.

Yuval Filmus

@MartinBerger Ese es un punto válido sobre el aumento del número de símbolos terminales y no terminales a medida que aumentamos el tamaño de la gramática. Para casos de uso como lenguajes de programación, eso tiene sentido.

user18064

@ user18064 Los lenguajes de programación generalmente usan un alfabeto de tamaño constante, en la mayoría de los casos un subconjunto de ASCII. No conozco ningún lenguaje práctico con un tamaño de alfabeto ilimitado, aunque uno podría definirlo fácilmente.

Yuval Filmus