Участник: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, |Q| = n, s \in Q[/math] — стартовое состояние, [math]T \subset Q[/math] — множество терминальных состояний. Рассмотрим вектор [math]u = (0, 0,...1, 0,...0)[/math] длины [math]n[/math], содержащий единственную единицу на позиции [math]s[/math].

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]