Введение
1. Основные определения и понятия, связанные со стохастическими КС-языками 16
2. Соотношение между стоимостью оптимального кодирования и энтропией стохастического языка 25
2.1. Основные определения, относящиеся к кодированию языков 26
2.2. Соотношение между стоимостью оптимального кодирования и энтропией для произвольного стохастического языка 27
2.3. Связь энтропии стохастического КС-языка с матрицей первых моментов порождающей грамматики 34
3. Закономерности в деревьях вывода слов стохастического КС-языка. Докритический случай 44
3.1. Некоторые предварительные результаты для стохастических КС-языков 45
3.2. Моменты 50
3.3. Закономерности применения правил грамматики в докритическом случае 54
4. Нижняя оценка стоимости кодирования и асимптотически оптимальное кодирование. Докритический случай 81
4.1. Определение стоимости кодирования 81
4.2. Нижняя оценка стоимости кодирования 82
4.3. Неулучшаемость нижней оценки стоимости кодирования и асимптотически оптимальное кодирование 86
5. Закономерности в деревьях вывода слов стохастического КС-языка. Критический случай 96
5.1. Предварительные результаты, основанные на результатах теории ветвящихся процессов 96
5.2. Закономерности в деревьях вывода в критическом случае 104
6. Нижняя оценка стоимости кодирования и асимптотически оптимальное кодирование. Критический случай 128
6.1. Нижняя оценка стоимости кодирования 128
6.2. Неулучшаемость нижней оценки стоимости кодирования и асимптотически оптимальное кодирование 134
Литература 138
