Изменения

[[Основные определения, связанные со строками#string | Слово]] <tex>w = \beta_1 \ldots \beta_m</tex> [[Основные определения, связанные со строками#deflanguage | языка]] <tex>L</tex> называется '''неразложимым''' (англ. ''indecomposable word'') в этом языке, если никакое его непустое подслово <tex> \beta_i \beta_{i+1} \ldots \beta_{i+l},\, 1 \leqslant i,\, i + l \leqslant m,\, l \geqslant 0,</tex> отличное от самого слова <tex>w,</tex> не принадлежит языку <tex>L</tex>.

Обозначим через <tex>n(t) = n_0 + n_1 t + n_2 t^2 + \ldots</tex> [[Производящая функция | '''производящую функцию ''']] '''для числа неразложимых слов языка''' <tex>L</tex>, через <tex>L(s) = l_0 + l_1 s + l_2 s^2 + \ldots</tex> — [[Язык Дика#def3 | '''производящую функцию для языка''' ]] <tex>L</tex> .

Пусть '''Γ''' — [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора#Однозначные грамматики | грамматика с однозначным выводом]].

<tex>r_i(s) = \sum_{j}^{} s^{\nu ij} \, \prod_{k} r_k^{\eta kj} (s) </tex>|proof=доказательство Поступим, как и в ситуации с одним порождающим символом, — введем некоммутативные производящие степенные ряды для каждого из языков <tex>L_i</tex>. Ввиду однозначности представления каждого слова в виде правой части правила вывода получаем систему уравнений на некоммутативные ряды.  Делая подстановку <tex>\lambda = s^0 = 1, \, a_i = s </tex> при <tex> i = 1, \ldots, m,</tex> получаем систему уравнений на производящие функции для числа слов.}} == Уравнение Лагранжа и теорема Лагранжа ==Часто для нахождения числа слов определенной длины в заданном языке выгодно найти производящую функцию этого языка. Посмотрим на равенство <tex>l(s) = n(sl(s))</tex>. Это функциональное уравнение, связывающее между собой производящие функции для числа слов в языке и числа неразложимых слов в нем. Хотелось бы уметь находить одну из этих функций, зная другую, то есть уметь решать это уравнение, если одна из функций задана. Это всегда возможно.  Рассмотрим уравнение <tex>l(s) = n(sl(s))</tex>. Чтобы привести к классическому виду, домножим обе части на <tex>s</tex> и положим <tex>sl(s) = \tilde{l} (s) </tex>. Тогда уравнение примет вид <tex> \tilde{l} (s) = sn(\tilde{l} (s)) </tex> — '''уравнение Лагранжа''' (англ. ''Lagrange equation''). {{Теорема|author=Лагранж|about=(англ. ''the Lagrange theorem'')|statement=Пусть в уравнении <tex> \tilde{l} (s) = sn(\tilde{l} (s)) </tex> задана одна из производящих функций <tex> \tilde{l} (s) \, (\tilde{l_0} = 0,\, \tilde{l_1} \neq 0) </tex> или <tex>n(t) \,(n_0 \neq 0)</tex>. Тогда вторая производящая функция однозначно восстанавливается по ней. |proof= Уравнение <tex> \tilde{l} (s) = sn(\tilde{l} (s)) </tex> можно переписать в следующем виде: <tex> \tilde{l_1}s + \tilde{l_2}s^2 + \ldots = n_0 s + n_1 s (\tilde{l_1}s + \tilde{l_2}s^2 + \tilde{l_3}s^3 + \ldots) +n_2 s({\tilde{l_1^2}}s^2 + 2\tilde{l_1}\tilde{l_2}s^3 + \ldots) +n_3s(необязательно{\tilde{l_1^3}}s + \ldots)+ \ldots </tex> Докажем сначала, что если функция <tex> \tilde{l} (s)</tex> задана, то <tex>n(t)</tex> однозначно восстанавливается по ней. Доказательство проведем по индукции, приравнивая последовательно коэффициенты при одинаковых степенях <tex>s</tex> в левой и правой частях. Коэффицент <tex>n_0</tex> определяется равенством <tex>n_0 = \tilde{l_1}</tex>. Предположим теперь, что коэффициенты <tex>n_0, n_1, \ldots, n_{k-1}</tex> уже определены. Тогда коэффициент <tex>n_k</tex> определяется из уравнения, составленного приравниванием коэффициентов при <tex>s^{k+1}</tex>: <tex> n_k\, \tilde{l}_1^k + n_{k-1}\, \lambda_{k-1} + \ldots + n_1\, \lambda_1 = \tilde{l}_k. </tex> Здесь через <tex>\lambda_i, \, i = 2, \ldots, k-1, </tex> обозначены коэффиценты при <tex>s^{k}</tex> в производящих функциях <tex> \tilde{l}^i (s) </tex>. Уравнение  <tex> n_k\, \tilde{l}_1^k + n_{k-1}\, \lambda_{k-1} + \ldots + n_1\, \lambda_1 = \tilde{l}_k. </tex> — линейное уравнение относительно <tex> n_k </tex>. Коэффициент при <tex> n_k </tex> в нем равен <tex>\tilde{l}_1^k </tex> и, поусловию теоремы, отличен от нуля. Поэтому <tex>n_k</tex> однозначно определяется из уравнения <tex> n_k\, \tilde{l}_1^k + n_{k-1}\, \lambda_{k-1} + \ldots + n_1\, \lambda_1 = \tilde{l}_k. </tex> С другой стороны, если задана функция <tex>n(t)</tex>, то мы должны положить <tex>\tilde{l}_1 = n_0</tex>. Коэффициенты <tex>\tilde{l}_k </tex> определяются теперь равенством <tex> n_k\, \tilde{l}_1^k + n_{k-1}\, \lambda_{k-1} + \ldots + n_1\, \lambda_1 = \tilde{l}_k, </tex> так как все оэффициенты <tex>\lambda_i</tex> являются многочленами от <tex> \tilde{l}_1, \ldots, \tilde{l}_{k-1} </tex>.