Изменения

Пусть <tex dpi="130150">A=\L</tex> {a_{1---},a_{2}некоторый регулярный язык, <tex dpi="150">a_n = |L \ldots ,a_cap \Sigma^n|</tex> {{z---}\}количество слов длины <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="130150">BL</tex> (англ. ''generating function of a regular language'').}}{{Теорема|id=th1.  |about=\Производящая функция регулярного языка|statement=Пусть <tex dpi="150">L</tex> {b_{1---},b_{2}, регулярный язык над алфавитом <tex dpi="150">\ldots Sigma</tex>,b_распознающийся [[Детерминированные конечные автоматы | детерминированным конечным автоматом]] <tex dpi="150">A</tex>. <tex dpi="150">Q</tex> {z_{1---}}множество состояний автомата <tex dpi="150">A</tex> размера $n$ со стартовым состоянием $s$. <tex dpi="150">T \}subset Q</tex> {{---}} множества из различных объектовмножество терминальных состояний автомата. Рассмотрим следующие вектора длины <tex dpi="130150">Wn</tex>: вектор <tex dpi="150">\vec{w_{u} = (0, \dots, 0, 1},w_{2}0, \ldots dots,w_{l}\}0)^T</tex> {{---}} количество объектов веса от , содержащий единственную единицу на позиции <tex dpi="130150">1s</tex> до и вектор <tex dpi="130150">l\vec{v}</tex> из , у которого единицы стоят на позициях, соответствующих номерам состояний множества <tex dpi="130150">AT</tex>, а . <tex dpi="130150">UD =\(d_{ij})</tex> {u_{1---},u_{2}матрица переходов автомата <tex dpi="150">A</tex>, \ldots ,u_где <tex dpi="150">d_{l}\ij}</tex> {{---}} соответственно количество символов, которые переводят автомат из состояния <tex dpi="150">i</tex> в состояние <tex dpi="150">j</tex>. Тогда производящая функция для количества слов над языком $L$ равна <tex dpi="130150">BL(t) = \vec{u}^T (I - tD)^{-1}\vec{v}</tex>.  |proof=доказательство (необязательно)