Том 12, серия 1, номер 3, 2005 г., Стр. 3-31
УДК 519.713
А. Е. Борисов
О свойствах стохастического КС-языка, порождённого грамматикой с двумя классами нетерминальных символов
Аннотация:
Рассматривается стохастический контекстно-свободный язык, порождённый грамматикой с двумя классами нетерминальных символов. Исследуется случай, когда перронов корень матрицы первых моментов меньше 1. Найдены асимптотические формулы для математического ожидания числа применений правила грамматики в дереве вывода фиксированной высоты. Получена асимптотика для энтропии множества слов, имеющих деревья вывода заданной высоты. Найдена нижняя оценка стоимости двоичного кодирования рассматриваемого языка.
Борисов А. Е. 1
1. ул. Лопатина, д. 3, кв. 199,
603163 Нижний Новгород, Россия
е-mail: abor1@rambler.ru, alexander.borisov@intel.com
Статья поступила 8 декабря 2003 г.
Исправленный вариант — 28 июня 2005 г.
