Участник:Wasteed

Определение:

Пусть [math]L[/math] — некоторый регулярный язык, [math]a_n = |L \cap \Sigma^n|[/math] — количество слов длины [math]n[/math] в языке [math]L[/math]. Тогда [math]L(t) = a_0 + a_1t + a_2t^2 + ... [/math] — это производящая функция для регулярного языка [math]L[/math] (англ. generating function of a regular language).

Теорема (Производящая функция регулярного языка):

Пусть [math]L[/math] — регулярный язык над алфавитом [math]\Sigma[/math], распознающийся детерминированным конечным автоматом [math]A[/math]. [math]Q[/math] — множество состояний автомата [math]A[/math] размера $n$ со стартовым состоянием $s$. [math]T \subset Q[/math] — множество терминальных состояний автомата. Рассмотрим следующие вектора длины [math]n[/math]: вектор [math]\vec{u} = (0, \dots, 0, 1, 0, \dots, 0)^T[/math], содержащий единственную единицу на позиции [math]s[/math] и вектор [math]\vec{v}[/math], у которого единицы стоят на позициях, соответствующих номерам состояний множества [math]T[/math]. [math]D = (d_{ij})[/math] — матрица переходов автомата [math]A[/math], где [math]d_{ij}[/math] — количество символов, которые переводят автомат из состояния [math]i[/math] в состояние [math]j[/math]. Тогда производящая функция для количества слов над языком $L$ равна [math]L(t) = \vec{u}^T (I - tD)^{-1}\vec{v}[/math].

Доказательство:

[math]\triangleright[/math]

доказательство (необязательно)

[math]\triangleleft[/math]