Переходные явления в неразложимых стохастических КС-грамматиках

С. 74–75.

Дурандин О. В., Жильцова Л. П.

В работе исследуются переходные явления, возникающие в неразложимых стохастических КС-грамматиках. Переходные явления возникают в случае, когда перронов корень r матрицы первых моментов грамматики стремится слева к единице, т.е. происходит переход от докритического случая (r < 1) к критическому (r = 1) [1]. Для рассматриваемого случая получена асимптоти- ка условного математического ожидания M(t, τ ) числа вершин, помеченных нетерминальными символами на ярусе τ, в деревьях вывода высоты t. Опреде- лен интервал для ярусов дерева вывода, на которых величина M(t, τ ) близка к асимптотическому значению. Установлена зависимость полученных харак- теристик от величины ε = 1 − r, определяющей близость к критическому случаю.

Ключевые слова: формальные грамматики, переходные вероятности, automata theory, Формальные языки и грамматики, formal grammar

В книге

Дискретные модели в теории управляющих систем : IX Международная конференция, Москва и Подмосковье, 20-22 мая 2015 г.: Труды

М.: МАКС Пресс, 2015.