КОДИРОВАНИЕ СЛОВ СТОХАСТИЧЕСКОГО КС-ЯЗЫКА, ПОРОЖДЕННОГО РАЗЛОЖИМОЙ ГРАММАТИКОЙ С ДВУМЯ НЕТЕРМИНАЛАМИ |
| 1 | |
| 2004 |
| научная статья | 519.713 | ||
| 18-27 |
| Рассматривается КС-язык, порожденный разложимой КС-грамматикой с двумя нетерминалами, перронов корень матрицы первых моментов которой меньше 1. Найдены асимптотические формулы для частот применения правил грамматики в дереве вывода на каждом ярусе и во всем дереве. Получена асимптотика энтропии множества слов, имеющих деревья вывода заданной высоты. Найдена стоимость оптимального кодирования рассмотренного языка. Получены общие оценки для стоимости кодирования произвольного стохастического языка. |
 |
| 1 . Борисов А.Е. Закономерности в деревьях вывода для стохастической разложимой КС-грамматики // Труды V Международной конференции "Дискретные модели в теории управляющих систем". М.: Издательский отдел ВМиК МГУ, 2003. С. 15-17. 2 . Жильцова Л.П. О нижней оценке стоимости кодирования и асимптотически оптимальном кодировании стохастического контекстно-свободного языка // Дискретный анализ и исследование операций. Сер. 1. 2001. Т.8. N3. С. 26-45. 3 . Севастьянов В.А. Ветвящиеся процессы. М.: Наука, 1971. 4 . Гантмахер Ф.Р. Теория матриц. М.: Наука, 1967. |