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

Odpowiedzi:

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