Главная страница
russian   english
16+
<< назад

Название статьи

О ВЕРОЯТНОСТЯХ ПРОДОЛЖЕНИЯ ДЕРЕВЬЕВ ВЫВОДА В РАЗЛОЖИМЫХ СТОХАСТИЧЕСКИХ КС-ГРАММАТИКАХ. ДОКРИТИЧЕСКИЙ СЛУЧАЙ


Номер журнала
4
Дата выпуска
2012

Тип статьи
научная статья
Коды УДК
519.713
Страницы
217-224
Ключевые слова
контекстно-свободный язык, стохастическая КС-грамматика, случайный процесс, вероятность, дерево вывода, матрица первых моментов, перронов корень

Авторы
Жильцова Лариса Павловна

Место работы
Жильцова Лариса Павловна
Нижегородский госуниверситет им. Н.И. Лобачевского


Аннотация
Рассматривается стохастическая контекстно-свободная грамматика с произвольным числом классов нетерминальных символов без ограничений на порядок следования классов. Соответствующая ей матрица A первых моментов является разложимой. В случае, когда перронов корень матрицы A строго меньше единицы, получена асимптотика для вероятностей продолжения деревьев вывода слов контекстно-свободного языка, высота которых больше t, при t ? ?.

Загрузить статью

Библиографический список
1 . Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Том 1. М.: Мир, 1978.
2 . Гантмахер Ф.Р. Теория матриц. М.: Наука, 1967.
3 . Жильцова Л.П. Закономерности применения правил грамматики в выводах слов стохастического контекстно-свободного языка // Математические вопросы кибернетики. М.: Наука. 2000. Вып.9. С. 101- 126.
4 . Жильцова Л.П. О нижней оценке стоимости кодирования и асимптотически оптимальном кодировании стохастического контекстно-свободного языка // Дискретный анализ и исследование операций. 2001. Серия 1. Т. 8. № 3. Новосибирск: Издательство Института математики СО РАН. С. 26-45.
5 . Жильцова Л.П. О матрице первых моментов разложимой стохастической КС-грамматики // Ученые записки Казанского государственного университета. Физико-математические науки. 2009. Том 151. Книга 2. С. 80-89.
6 . Севастьянов В.А. Ветвящиеся процессы. М.: Наука, 1971.
7 . Фу К. Структурные методы в распознавании образов. М.: Мир, 1977.