Изменения

Пусть <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> {{---}} стартовое состояние, размера $n$ со стартовым состоянием $s$. <tex dpi="150">T \subset Q</tex> {{---}} множество терминальных состоянийавтомата. Рассмотрим такие следующие вектора длины <tex dpi="150">n</tex>: вектор <tex dpi="150">\vec{u} = (0, \dots, 0,...1, 0,...\dots, 0)^T</tex>, содержащий единственную единицу на позиции <tex dpi="150">s</tex> и вектор <tex dpi="150">\vec{v} = (1, 0,...1, 0,...1)^T</tex>, у которого единицы стоят на позициях, соответствующих номерам состояний множества <tex dpi="150">T</tex>. Матрица переходов автомата <tex dpi="150">AD = (d_{ij})</tex>: {{---}} матрица переходов автомата <tex dpi="150">D = (d_{ij})A</tex>, где <tex dpi="150">d_{ij}</tex> {{---}} количество символов, которые переводят автомат из состояния <tex dpi="150">i</tex> в состояние <tex dpi="150">j</tex>. Тогда утверждается, что производящая функция для количества слов над языком $L$ равна <tex dpi="150">L(t) = \vec{u} ^T (I - tD)^{-1}\vec{v}</tex>.