1632
правки
Изменения
м
rollbackEdits.php mass rollback
{{Определение
|definition=
[[Основные определения, связанные со строками#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>L</tex> обладает следующими свойствами:
:1) пустое слово входит в язык <tex>L</tex>
:2) начало всякого неразложимого слова не совпадает с концом другого или того же самого неразложимого слова
:3) если между любыми двумя буквами любого слова языка <tex>L</tex> вставить слово языка <tex>L</tex>, то получится слово языка <tex>L</tex>
:4) если из любого слова языка <tex>L</tex> выкинуть подслово, входящее в язык <tex>L</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> .
{{Теорема
|statement=
Производящая функция для языка <tex>L</tex>, удовлетворяющего свойствам 1) — 4), и производящая функция для подъязыка неразложимых слов в нем связаны между собой уравнением Лагранжа <tex>l(s) = n(sl(s))</tex>.
|proof=
Каждому неразложимому слову <tex>\alpha_{i_1} \ldots \alpha_{i_m}</tex> в языке <tex>L</tex> сопоставим правило вывода
<tex>r \longrightarrow \alpha_{i_1}\, r\, \alpha_{i_2} \ldots \alpha_{i_m}\, r</tex>.
Ясно, что каждое слово языка допускает вывод по этим правилам. Такой вывод однозначен. Действительно, пусть <tex>\beta_1 \ldots \beta_k</tex> — произвольное слово языка <tex>L</tex>. если оно неразложимо, то оно представляется в виде правой части правила вывода
<tex>r \longrightarrow \beta_{1} r \beta_{2} \ldots \beta_{k} r,</tex>
где каждое вхождение символа <tex>r</tex> следует заменить на пустое слово. Из определения неразложимого слова вытекает, что такое представление единственно.
Предположим, что есть разложимые слова, допускающие различное представление. Рассмотрим самое короткое такое слово <tex>w</tex>. В нем содержится неразложимое подслово. Выберем из всех неразложимых подслов слова <tex>w</tex> самое правое (это возможно, так как неразложимые подслова не могут пересекаться) и выкинем его из слова <tex>w</tex>. Получим новое слово <tex>w'</tex>. Это слово имеет те же самые представления в виде правых частей правил вывода, что и слово <tex>w</tex>. Поэтому <tex>w'</tex> — более короткое слово, допускающее несколько различных представлений. Полученное противоречие доказывает единственность представления.
Таким образом, некоммутативная производящая функция для языка <tex>L</tex> удовлетворяет уравнению
<tex> \mathcal{L} (a_1, \ldots , a_m) = \lambda + \alpha_{11}\, \mathcal{L}\, (a_1, \ldots , a_m)\, \alpha_{12}\, \mathcal{L} (a_1, \ldots , a_m) \ldots + \ldots</tex>
Делая подстановку <tex> \lambda = 1,\, a_i = t</tex> и учитывая, что <tex>l(t) = \mathcal{L}(t, t, \ldots, t),</tex> получаем заключение теоремы.
}}
{{Теорема
|statement=
Пусть '''Γ''' — [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора#Однозначные грамматики | грамматика с однозначным выводом]].
Обозначим через <tex>r_i(s)</tex> производящую функцию для числа слов в языке <tex>L_i,</tex> выводимого из символа <tex>r_i</tex>. Тогда производящие функции <tex>r_i</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>.
}}
'''Замечание'''
Если коэффициенты функции <tex>n</tex> —целые неотрицательные числа, то и коэффициенты функции <tex>\tilde{l}</tex> будут целыми и неотрицательными. Если коэффициенты функции <tex>\tilde{l}</tex> целые и неотрицательные, причем <tex>\tilde{l}_1 = 1,</tex> то и коэффициенты функции <tex>n</tex> оказываются целыми. Однако при этом среди них могут оказаться и отрицательные числа.
== См. также ==
*[[Производящая функция]]
*[[Язык Дика]]
*[[Асимптотика коэффициентов функций, связанных между собой уравнением Лагранжа]]
== Источники информации ==
* С. А. Ландо: Лекции о производящих функциях
* Гросс М., Лантен А.: Теория формальных грамматик
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Производящая функция]]
