Изменения

Пусть <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">j</tex> в состояние <tex dpi="150">j</tex>. Тогда утверждается, что <tex dpi="150">L(t) = \vectvec(U)(I - tD)^{-1}\vectvec(v)</tex>.