Rozważ następujące naturalne pytanie: Biorąc pod uwagę skończony język , jaka jest najmniejsza bezkontekstowa gramatyka generująca ?
Możemy uczynić pytanie bardziej interesującym, określając sekwencję języków , na przykład jest zbiorem wszystkich permutacji : intuicyjnie, CFG dla „musiałby” mieć rozmiar . Jesteśmy więc zainteresowani asymptotycznym rozmiarem najmniejszych CFG dla języków.
Podobne pytania zostały poruszone w kilku artykułach:
- Charikar i in. („Aproksymacja najmniejszej gramatyki: złożoność Kołmogorowa w modelach naturalnych”) zastanów się, jak trudno jest oszacować wielkość najmniejszej CFG generującej dane słowo .
- Dalsze prace w tym kierunku to Arpe i Reischuk, „O złożoności kompresji opartej na optymalnej gramatyce”.
- Peter Asveld ma kilka artykułów na ten temat (np. „Generowanie wszystkich permutacji przez gramatyki bezkontekstowe w normalnej formie Chomsky'ego”). Próbuje zoptymalizować niektóre parametry na określonych typach gramatycznych, generując zestaw wszystkich permutacji, w szczególności form normalnych Chomsky'ego i Greibacha.
Jednak do tej pory nie udało mi się znaleźć żadnego papieru, który próbowałby udowodnić powiązanie Wielkości CFG generującej .
Czy istnieją artykuły określające dolne granice wielkości gramatyk bezkontekstowych dla określonych języków skończonych?
W odpowiedzi na kilka pytań na tej stronie, a także na stronie math.stackexchange, opracowałem prostą metodę, która jest w stanie udowodnić wykładnicze dolne granice CFG dla określonych języków, na przykład . Czy te wyniki są nowe? Trudno mi w to uwierzyć i chętnie zdobędę wskazówki dotyczące literatury.