Изменения

Пусть <tex dpi="150">L </tex> {{-- -}} некоторый регулярный язык. , <texdpi="150">a_n = |L \mid cap \midSigma^n|</tex> {{---}} количество слов длины <tex dpi="150">n</tex> в языке <tex dpi="150">L</tex>. Тогда <tex dpi="150">L(t) = a_0 + a_1t + a_2t^2 + ... </tex> — это '''Производящая производящая функция для регулярных языковрегулярного языка''' <tex dpi="150">L</tex> (англ. ''generating function for of a regular languageslanguage'') — это формальный степенной ряд вида .}}{{Теорема|id=th1.  |about=Производящая функция регулярного языка|statement=Пусть <tex dpi="150">L</tex>G(z){{---}} регулярный язык над алфавитом <tex dpi="150">\sumSigma</tex>, распознающийся [[Детерминированные конечные автоматы | детерминированным конечным автоматом]] <tex dpi="150">A</tex>. <tex dpi="150">Q</tex> {{---}} множество состояний автомата <tex dpi="150">A</tex> размера $n$ со стартовым состоянием $s$. <tex dpi="150">T \limits_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">\infty a_n z^nvec{v}</tex>, порождающий у которого единицы стоят на позициях, соответствующих номерам состояний множества <tex dpi="150">T</tex>. <tex dpi="150">D = (производящийd_{ij}) последовательность </tex> {{---}} матрица переходов автомата <tex dpi="150">A</tex>(a_0, a_1, a_2где <tex dpi="150">d_{ij}</tex> {{---}} количество символов, которые переводят автомат из состояния <tex dpi="150">i</tex> в состояние <tex dpi="150">j</tex>. Тогда производящая функция для количества слов над языком $L$ равна <tex dpi="150">L(t) = \ldotsvec{u}^T (I - tD)^{-1}\vec{v}</tex>.  |proof=доказательство (необязательно)