Введение
2 Оценка средней длины кода для стохастического языка 17
3 Закономерности в деревьях вывода слов и оптимальное кодирование. Докритический случай 21
3.1 Основные определения и обозначения 21
3.2 Вероятности продолжения 23
3.3 Закономерности в деревьях вывода слов. Случай простого перронова корня 33
3.4 Закономерности в деревьях вывода слов. Случай кратного перронова корня 35
3.5 Оценки моментов второго и более высоких порядков для кратного перронова корня 37
3.6 Дисперсия числа применений правил в деревьях вывода 47
3.7 Пример грамматики с двумя классами нетерминалов . 53
3.8 Оценка стоимости оптимального кодирования 54
3.9 Алгоритм асимптотически оптимального кодирования . 57
4 Закономерности в деревьях вывода слов и оптимальное кодирование. Критический случай 61
4.1 Случай кратного перронова корня 62
4.1.1 Вероятности продолжения 62
4.1.2 Математические ожидания числа применений правил в деревьях вывода 71
4.1.3 Энтропия и стоимость оптимального кодирования 82
4.1.4 Алгоритм оптимального кодирования 84
4.2 Случай простого перронова корня 86
4.2.1 Вероятности продолжения и вероятности деревьев вывода фиксированной высоты 86
4.2.2 Распределение нетерминалов на фиксированном ярусе дерева вывода 88
4.2.3 Математические ожидания числа применений правил в деревьях вывода 91
4.2.4 Алгоритм оптимального кодирования 95
5 Заключение 96
