Изменения

Пусть <tex dpi="150">L</tex> {{- --}} некоторый регулярный язык. , <tex dpi="150">a_n = |L \cap \Sigma^n| = a_n</tex> {{- --}} количество слов длины <tex dpi="150">n </tex> в языке <texdpi="150">L</tex>. Тогда <texdpi="150">L(t)=a_0 + a_1t + a_2t^2 + ...</tex> - — это '''производящая функция для регулярного языка''' <tex dpi="150">L</tex> (англ. ''generating function of a regular language'') .}}{{Теорема|id=th1.  |about=Производящая функция регулярного языка|statement=Пусть <texdpi="150">L</tex>{{---}} регулярный язык над алфавитом <tex dpi="150">\Sigma</tex>, распознающийся [[Детерминированные конечные автоматы | детерминированным конечным автоматом]] <tex dpi="150">A</tex>. <tex dpi="150">Q</tex> {{---}} множество состояний автомата <tex dpi="150">A</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}</tex>, у которого единицы стоят на позициях, соответствующих номерам состояний множества <tex dpi="150">T</tex>. <tex dpi="150">D = (d_{ij})</tex> {{---}} матрица переходов автомата <tex dpi="150">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>. |proof=доказательство (необязательно)