Asymptotyczna gęstość niejednoznacznych gramatyk bezkontekstowych (CFG)

Jaki jest stosunek niejednoznacznych CFG do wszystkich CFG ?

Ponieważ oba zestawy są w nieskończoność nieskończone, stosunek nie jest dobrze zdefiniowany. Ale co z asymptotyczną gęstością :

lim_{n \mapsto \infty} \frac{# niejednoznaczny CFG wielkości < n}{# CFG wielkości < n}

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

gdzie symbole końcowe i nieterminalne pochodzą z ustalonego zbioru policzalnego.

Rozmiar gramatyki to dowolne rozsądne pojęcie wielkości gramatyki, np

całkowita liczba wystąpień zmiennych i terminali w regułach produkcji, lub
całkowita liczba wystąpień zmiennej, lub
całkowita liczba reguł produkcji, lub
liczba różnych zmiennych.

(Zakładam, że definicja rozmiaru nie wpłynie na odpowiedź).

fl.formal-languages grammars context-free

— użytkownik18064
źródło

Nawiasem mówiąc, w literaturze rozważono następujące pojęcia wielkości CFG: W odniesieniu do pojęć wielkości gramatycznej w literaturze pojawiły się następujące pojęcia. (1) Całkowita liczba wystąpień zmiennych i terminali po obu stronach wszystkich produkcji w gramatyce. (2) Liczba zmiennych wystąpień po obu stronach wszystkich produkcji gramatyki. (3) Liczba produkcji w gramatyce. (4) Liczba odrębnych zmiennych w gramatyce.

— Martin Berger,

Patrz na przykład: S. Ginsburg, N. Lynch, Złożoność rozmiaru w bezkontekstowych formach gramatycznych. J. Gruska, O wielkości gramatyki bezkontekstowej. J. Gruska, Złożoność i jednoznaczność gramatyk i języków bezkontekstowych. A. Kelemenova, Złożoność gramatyki normalnej.

— Martin Berger,

@ Martin, jeśli ktoś nie jest ostrożny, może istnieć nieskończenie wiele gramatycznie różnych gramatyk o danym rozmiarze, a stosunek nie będzie miał sensu. Bezpiecznym sposobem jest policzenie długości bitów jakiegoś ustalonego kodowania gramatyki.

— Kaveh

Prawdopodobnie chcesz zdefiniować asymptotyczną gęstość jako stosunek logarytmów odpowiednich wielkości, ponieważ obie wielkości są wykładnicze, prawdopodobnie o różnych zasadach.

— Mobius dumpling

@MartinBerger Zakładając, że mówimy o tym samym, tj. , to oczywiście wpłynęłoby na gęstość. Załóżmy, że liczba jednoznacznych CFG wynosi a liczba CFG wynosi , wtedy gęstość log jest a gęstość asymptotyczna wynosi 0. Jestem całkiem pewien, że gęstość asymptotyczna będzie wynosić 0 lub 1, ale asymptotyczna gęstość logów prawdopodobnie będzie interesującą liczbą.

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

Pytanie zależy od dokładnego kodowania. Wydaje się jednak, że w wielu rozsądnych kodowaniach, ponieważ długość zmierza do nieskończoności, liczba reguł produkcji (dla właściwej interpretacji początkowego symbolu i terminala ) będzie większa niż jeden z dużym prawdopodobieństwem; tutaj dosłownie mam na myśli ten sam terminal . Jeśli uznamy to za dwuznaczność, spodziewam się, że „większość” gramatyk będzie dwuznaczna. Możemy również wymyślić podobne sytuacje, takie jak reguły i każdej pojawiającej się co najmniej raz. $S\to a$ $S$ $a$ $a$ $S\to S$ $S\to a$

Zakładając tę ogólną hipotezę, że każda (ustalona) możliwa reguła powinna pojawić się z dużym prawdopodobieństwem, gdy długość zmierza do nieskończoności, stwierdzamy, że „większość” gramatyk generuje w niejednoznaczny sposób. $\Sigma^*$

Jako przykład rozważmy następujące kodowanie gramatyk nad . Alfabet gramatyczny składa się z symboli . Nieterminale są indeksowane przez ciągi binarne o długości co najmniej 2. Reguły są oddzielone kropkami. Każda reguła jest ciągiem ciągów binarnych oddzielonych średnikami. Pierwszy ciąg binarny jest nieterminalny po lewej stronie, a reszta (jeśli występuje) stanowi prawą stronę; jeśli pierwszy ciąg binarny nie jest nie-końcowy (tj. jest to , 0,1), to zakłada się, że początkowy nie-końcowy. Początkowy nieterminalny jest zawsze 00. $\Sigma = \{0,1\}$ $\{0,1,;,.\}$ $\epsilon$

W ramach tego kodowania każdy ciąg w Opisuje pewną gramatykę. Gramatyka losowa z dużym prawdopodobieństwem będzie zawierać wiele kopiii, a w szczególności będą niejednoznaczne. $\{0,1,;,.\}^*$ $.00;00.$ $.00;0.$

— Yuval Filmus
źródło

Tak, uważam takie zasady, jak i (występujące więcej niż jeden raz) w gramatyce, jako prawidłowe. Rzeczywiście, powoduje to, że gramatyka jest trywialnie niejednoznaczna. Twoje zdrowie.

S \to S

$S\to S$

S \to a

$S\to a$

— user18064

Ale czy nie jest tak również, że wraz ze wzrostem wielkości (CFG) liczba terminali i nie-terminali zwykle wzrasta, więc potrzebujemy więcej bitów do ich reprezentowania, dlatego potrzebujemy więcej bitów do reprezentowania poszczególnych reguł. Tak więc liczba CFG, które są jednoznaczne z błahych powodów (np. Tylko jedna reguła pasuje do rozmiaru) również rośnie.

— Martin Berger,

@ Martin To zależy od kodowania. Być może możesz wymyślić kodowanie wspierające twoje twierdzenie, na przykład, jeśli rozmiar alfabetu rośnie wraz z rozmiarem gramatyki. Moje kodowanie używa stałego rozmiaru alfabetu, więc ten efekt nie występuje.

— Yuval Filmus

@MartinBerger To ważny punkt na temat zwiększenia liczby symboli końcowych i nieterminalnych, gdy zwiększamy rozmiar gramatyki. Ma to sens w przypadkach użycia, takich jak języki programowania.

— user18064

@ user18064 Języki programowania zwykle używają alfabetu stałej wielkości, w większości przypadków podzbioru ASCII. Nie znam żadnego praktycznego języka o nieograniczonej wielkości alfabetu, choć można je łatwo zdefiniować.

— Yuval Filmus