Изменения

Перейти к: навигация, поиск

Участник:Wasteed

1 байт добавлено, 02:49, 21 мая 2021
Нет описания правки
|about=(Производящая функция регулярного языка)
|statement=
Пусть <tex dpi="150">L</tex> {{---}} регулярный язык над алфавитом <tex dpi="150">\Sigma</tex>, распознающийся [[Детерминированные конечные автоматы | детерминированным конечным автоматом]] <tex dpi="150">A</tex>, <tex dpi="150">Q</tex> {{---}} множество состояний <tex dpi="150">A, |Q| = n, s \in Q</tex> {{---}} стартовое состояние, <tex dpi="150">T \subset Q</tex> {{---}} множество терминальных состояний. Рассмотрим такие вектора длины <tex dpi="150">n</tex>: <tex dpi="150">u = (0, 0,...1, 0,...0)</tex>, содержащий единственную единицу на позиции <tex dpi="150">s</tex> и вектор <tex dpi="150">v = (1, 0,...1, 0,...1)^T</tex>, у которого единицы стоят на позициях, соответствующих номерам состояний множества <tex dpi="150">T</tex>. Матрица переходов автомата <tex dpi="150">A</tex>: <tex dpi="150">D = (d_{ij})</tex>, где <tex dpi="150">d_{ij}</tex> {{---}} количество символов, которые переводят автомат из состояния <tex dpi="150">ji</tex> в состояние <tex dpi="150">j</tex>. Тогда утверждается, что <tex dpi="150">L(t) = \vec{u}(I - tD)^{-1}\vec{v}</tex>.
|proof=доказательство (необязательно)
}}
Анонимный участник

Навигация