Изменения

Пусть <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">nv = (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">sj</tex>.