Asymptotische Dichte mehrdeutiger kontextfreier Grammatiken (CFGs)

Wie ist das Verhältnis von mehrdeutigen CFGs zu allen CFGs ?

Da beide Sätze zählbar unendlich sind, ist das Verhältnis nicht genau definiert. Aber was ist mit der asymptotischen Dichte :

lim_{n \mapsto \infty} \frac{# mehrdeutige CFG der Größe < n}{# CFG der Größe < n}

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

wobei Terminal- und Nicht-Terminal-Symbole aus einem festen zählbaren Satz stammen.

Die Größe einer Grammatik ist ein vernünftiger Größenbegriff für Grammatiken, z

die Gesamtzahl der Vorkommen von Variablen und Terminals in den Produktionsregeln oder
die Gesamtzahl der Vorkommen von Variablen oder
die Gesamtzahl der Produktionsregeln oder
die Anzahl der verschiedenen Variablen.

(Ich gehe davon aus, dass die Definition der Größe die Antwort nicht beeinflusst.)

fl.formal-languages grammars context-free user18064
quelle

Abgesehen davon wurden in der Literatur die folgenden Begriffe der CFG-Größe berücksichtigt: In Bezug auf Begriffe der Grammatikgröße sind in der Literatur die folgenden Begriffe erschienen. (1) Gesamtzahl der Vorkommen von Variablen und Terminals auf beiden Seiten aller Produktionen in der Grammatik. (2) Anzahl variabler Vorkommen auf beiden Seiten aller Produktionen in der Grammatik. (3) Anzahl der Produktionen in der Grammatik. (4) Anzahl der verschiedenen Variablen in der Grammatik.

Martin Berger

Siehe zum Beispiel: S. Ginsburg, N. Lynch, Größenkomplexität in kontextfreien Grammatikformen. J. Gruska, Über die Größe kontextfreier Grammatiken. J. Gruska, Komplexität und Eindeutigkeit kontextfreier Grammatiken und Sprachen. A. Kelemenova, Komplexität von Normalformgrammatiken.

Martin Berger

@Martin, wenn man nicht aufpasst, kann es unendlich viele syntaktisch unterschiedliche Grammatiken einer bestimmten Größe geben und das Verhältnis macht keinen Sinn. Der sichere Weg besteht darin, die Bitlänge einer festen Codierung von Grammatiken zu zählen.

Kaveh

Sie möchten wahrscheinlich die asymptotische Dichte als das Verhältnis der Logarithmen der jeweiligen Größen definieren, da beide Größen exponentiell sind, wahrscheinlich mit unterschiedlichen Basen.

Mobius Knödel

@MartinBerger Angenommen, wir sprechen über dasselbe, dh die Definition von , würde dies offensichtlich die Dichte beeinflussen. Angenommen, die Anzahl der eindeutigen CFGs beträgt und die Anzahl der CFGs beträgt . Dann beträgt die logarithmische Dichte während die asymptotische Dichte 0 beträgt. Ich bin mir ziemlich sicher, dass die asymptotische Dichte gleich sein wird entweder 0 oder 1, aber die asymptotische logarithmische Dichte ist wahrscheinlich eine interessante Zahl.

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 Knödel

Antworten:

Die Frage hängt von der genauen Kodierung ab. Es scheint jedoch, dass in vielen vernünftigen Codierungen, da die Länge gegen unendlich tendiert, die Anzahl der Produktionsregeln (für eine geeignete Interpretation des Startsymbols und des Terminals ) mit hoher Wahrscheinlichkeit mehr als eins sein wird; hier meine ich wörtlich das gleiche terminal . Wenn wir dies als Mehrdeutigkeit betrachten, erwarte ich, dass "die meisten" Grammatiken mehrdeutig sind. Wir können auch ähnliche Situationen erfinden, wie die Regeln und jeweils mindestens einmal auftreten. $S\to a$ $S$ $a$ $a$ $S\to S$ $S\to a$

Unter der Annahme dieser allgemeinen Hypothese, dass jede (feste) denkbare Regel mit hoher Wahrscheinlichkeit erscheinen sollte, wenn die Länge gegen unendlich tendiert, stellen wir fest, dass "die meisten" Grammatiken auf mehrdeutige Weise erzeugen . $\Sigma^*$

Betrachten Sie als Beispiel die folgende Codierung für Grammatiken über . Das Grammatikalphabet besteht aus den Symbolen . Nicht-Terminals werden durch binäre Zeichenfolgen mit einer Länge von mindestens 2 indiziert. Regeln werden durch Punkte getrennt. Jede Regel ist eine Folge von binären Zeichenfolgen, die durch Semikolons getrennt sind. Die erste binäre Zeichenfolge ist das Nicht-Terminal auf der linken Seite, und der Rest (falls vorhanden) bildet die rechte Seite. Wenn die erste binäre Zeichenfolge kein Nicht-Terminal ist (dh , 0,1), wird das beginnende Nicht-Terminal angenommen. Das Start-Nicht-Terminal ist immer 00. $\Sigma = \{0,1\}$ $\{0,1,;,.\}$ $\epsilon$

Unter dieser Codierung beschreibt jede Zeichenfolge in Grammatik. Eine zufällige Grammatik enthält mit hoher Wahrscheinlichkeit viele Kopien vonundund wird insbesondere mehrdeutig sein. $\{0,1,;,.\}^*$ $.00;00.$ $.00;0.$

Yuval Filmus
quelle

Ja, ich halte Regeln wie und (die mehrmals vorkommen) in einer Grammatik für gültig. In der Tat macht dies eine Grammatik trivial mehrdeutig. Prost.

S \to S

$S\to S$

S \to a

$S\to a$

user18064

Aber ist es nicht auch so, dass mit zunehmender Größe (CFG) die Anzahl der Terminals und Nicht-Terminals normalerweise zunimmt, sodass wir mehr Bits benötigen, um sie darzustellen, und daher mehr Bits benötigen, um einzelne Regeln darzustellen. Daher nimmt auch die Anzahl der CFGs zu, die aus trivialen Gründen eindeutig sind (z. B. passt nur eine Regel in die Größengrenze).

Martin Berger

@ Martin Es kommt auf die Kodierung an. Vielleicht können Sie eine Kodierung finden, die Ihren Anspruch unterstützt, zum Beispiel wenn die Alphabetgröße mit der Grammatikgröße wächst. Meine Codierung verwendet eine konstante Alphabetgröße, sodass dieser Effekt nicht auftritt.

Yuval Filmus

@MartinBerger Dies ist ein gültiger Punkt zum Erhöhen der Anzahl von terminalen und nicht terminalen Symbolen, wenn wir die Grammatikgröße erhöhen. Für Anwendungsfälle wie Programmiersprachen ist dies sinnvoll.

user18064

@ user18064 Programmiersprachen verwenden normalerweise ein Alphabet konstanter Größe, in den meisten Fällen eine Teilmenge von ASCII. Mir ist keine praktische Sprache mit unbegrenzter Alphabetgröße bekannt, obwohl man sie leicht definieren könnte.

Yuval Filmus