О ВЕРОЯТНОСТЯХ ПРОДОЛЖЕНИЯ ДЕРЕВЬЕВ ВЫВОДА В РАЗЛОЖИМЫХ СТОХАСТИЧЕСКИХ КС-ГРАММАТИКАХ. ДОКРИТИЧЕСКИЙ СЛУЧАЙ |
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. |