Dolne granice wielkości CFG dla określonych języków skończonych

Rozważ następujące naturalne pytanie: Biorąc pod uwagę skończony język , jaka jest najmniejsza bezkontekstowa gramatyka generująca ?$L$$L$

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.$L_n$$L_n$$\{1,\ldots,n\}$$L_n$$\Omega(n!)$

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 .$\Omega(n!)$$L_n$

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.$L_n$

Miły recenzent przysłał mi artykuł, który dowodzi dokładnie tej samej dolnej granicy, co ja, dokładnie w ten sam sposób. Papier jest

K. Ellul, B. Krawetz, J. Shallit, M.-w. Wang, Wyrażenia regularne: nowe wyniki i otwarte problemy , J. Autom. Lang. Grzebień. 10 (2005), 407–432.

Wynikiem jest Twierdzenie 30 w artykule.