Задача о наименьшей грамматике
 | Для улучшения этой статьи по информационным технологиям желательно:
|
В теории формальных языков задачей о наименьшей грамматике называется задача нахождения наименьшей контекстно-свободной грамматики, которая порождает уникальную последовательность символов. Размер грамматики частью авторов определяется числом символов в правой части правил вывода.[1] Но иногда включается и число правил.[2]
Примечания
- 9 августа 2017 года.
Литература
- Charikar, Moses; Lehman, Eric; Liu, Ding; Panigrahy, Rina; Prabhakaran, Manoj; Rasala, April; Sahai, Amit; Shelat, Abhi. Approximating the Smallest Grammar: Kolmogorov Complexity in Natural Models // Proceedings of the thirty-fourth annual ACM symposium on theory of computing (STOC 2002), Montreal, Quebec, Canada, May 19–21, 2002 (англ.). — New York, NY: .