Том 10, серия 1, номер 3, 2003 г., Стр. 23-53
УДК 519.713
Л. П. Жильцова
Закономерности в деревьях вывода слов стохастического контекстно-свободного языка и нижняя оценка стоимости кодирования. Критический случай
Аннотация:
Рассматривается язык, порожденный стохастической контекстно-свободной грамматикой, матрица первых моментов которой неразложима, непериодична и ее перронов корень равен 1. Для такого языка установлены закономерности в деревьях вывода фиксированной высоты$t$ при$t\to\infty$ . На основе этих закономерностей получена точная нижняя оценка стоимости двоичного кодирования.
Жильцова Л. П. 1
1. Нижегородский государственный педагогический университет,
ул. Ульянова, 1, 603005 Нижний Новгород, Россия
Статья поступила 29 апреля 2003 г.
