Уравнение Лагранжа и теорема Лагранжа

Формальные грамматики с однозначным выводом

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

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

В частности, пустое слово в любом языке неразложимо.

Предположим, что язык [math]L[/math] обладает следующими свойствами:

1) пустое слово входит в язык [math]L[/math]

2) начало всякого неразложимого слова не совпадает с концом другого или того же самого неразложимого слова

3) если между любыми двумя буквами любого слова языка [math]L[/math] вставить слово языка [math]L[/math], то получится слово языка [math]L[/math]

4) если из любого слова языка [math]L[/math] выкинуть подслово, входящее в язык [math]L[/math], то получится слово языка [math]L[/math]

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

Теорема:

Производящая функция для языка [math]L[/math], удовлетворяющего свойствам 1) — 4), и производящая функция для подъязыка неразложимых слов в нем связаны между собой уравнением Лагранжа [math]l(s) = n(sl(s))[/math].

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

[math]\triangleright[/math]

Каждому неразложимому слову [math]\alpha_{i_1} \ldots \alpha_{i_m}[/math] в языке [math]L[/math] сопоставим правило вывода [math]r \longrightarrow \alpha_{i_1}\, r\, \alpha_{i_2} \ldots \alpha_{i_m}\, r[/math]. Ясно, что каждое слово языка допускает вывод по этим правилам. Такой вывод однозначен. Действительно, пусть [math]\beta_1 \ldots \beta_k[/math] — произвольное слово языка [math]L[/math]. если оно неразложимо, то оно представляется в виде правой части правила вывода [math]r \longrightarrow \beta_{1} r \beta_{2} \ldots \beta_{k} r,[/math] где каждое вхождение символа [math]r[/math] следует заменить на пустое слово. Из определения неразложимого слова вытекает, что такое представление единственно. Предположим, что есть разложимые слова, допускающие различное представление. Рассмотрим самое короткое такое слово [math]w[/math]. В нем содержится неразложимое подслово. Выберем из всех неразложимых подслов слова [math]w[/math] самое правое (это возможно, так как неразложимые подслова не могут пересекаться) и выкинем его из слова [math]w[/math]. Получим новое слово [math]w'[/math]. Это слово имеет те же самые представления в виде правых частей правил вывода, что и слово [math]w[/math]. Поэтому [math]w'[/math] — более короткое слово, допускающее несколько различных представлений. Полученное противоречие доказывает единственность представления. Таким образом, некоммутативная производящая функция для языка [math]L[/math] удовлетворяет уравнению [math] \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[/math] Делая подстановку [math] \lambda = 1,\, a_i = t[/math] и учитывая, что [math]l(t) = \mathcal{L}(t, t, \ldots, t),[/math] получаем заключение теоремы.

[math]\triangleleft[/math]

Теорема:

Пусть Γ — грамматика с однозначным выводом. Обозначим через [math]r_i(s)[/math] производящую функцию для числа слов в языке [math]L_i,[/math] выводимого из символа [math]r_i[/math]. Тогда производящие функции [math]r_i[/math] удовлетворяют системе уравнений [math]r_i(s) = \sum_{j}^{} s^{\nu ij} \, \prod_{k} r_k^{\eta kj} (s) [/math]

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

[math]\triangleright[/math]

Поступим, как и в ситуации с одним порождающим символом, — введем некоммутативные производящие степенные ряды для каждого из языков [math]L_i[/math]. Ввиду однозначности представления каждого слова в виде правой части правила вывода получаем систему уравнений на некоммутативные ряды. Делая подстановку [math]\lambda = s^0 = 1, \, a_i = s [/math] при [math] i = 1, \ldots, m,[/math] получаем систему уравнений на производящие функции для числа слов.

[math]\triangleleft[/math]

Уравнение Лагранжа и теорема Лагранжа

Часто для нахождения числа слов определенной длины в заданном языке выгодно найти производящую функцию этого языка. Посмотрим на равенство [math]l(s) = n(sl(s))[/math]. Это функциональное уравнение, связывающее между собой производящие функции для числа слов в языке и числа неразложимых слов в нем. Хотелось бы уметь находить одну из этих функций, зная другую, то есть уметь решать это уравнение, если одна из функций задана. Это всегда возможно.

Рассмотрим уравнение [math]l(s) = n(sl(s))[/math]. Чтобы привести к классическому виду, домножим обе части на [math]s[/math] и положим [math]sl(s) = \tilde{l} (s) [/math]. Тогда уравнение примет вид [math] \tilde{l} (s) = sn(\tilde{l} (s)) [/math] — уравнение Лагранжа (англ. Lagrange equation).

Теорема (Лагранж, (англ. the Lagrange theorem)):

Пусть в уравнении [math] \tilde{l} (s) = sn(\tilde{l} (s)) [/math] задана одна из производящих функций [math] \tilde{l} (s) \, (\tilde{l_0} = 0,\, \tilde{l_1} \neq 0) [/math] или [math]n(t) \,(n_0 \neq 0)[/math]. Тогда вторая производящая функция однозначно восстанавливается по ней.

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

[math]\triangleright[/math]

Уравнение [math] \tilde{l} (s) = sn(\tilde{l} (s)) [/math] можно переписать в следующем виде: [math] \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 [/math] Докажем сначала, что если функция [math] \tilde{l} (s)[/math] задана, то [math]n(t)[/math] однозначно восстанавливается по ней. Доказательство проведем по индукции, приравнивая последовательно коэффициенты при одинаковых степенях [math]s[/math] в левой и правой частях. Коэффицент [math]n_0[/math] определяется равенством [math]n_0 = \tilde{l_1}[/math]. Предположим теперь, что коэффициенты [math]n_0, n_1, \ldots, n_{k-1}[/math] уже определены. Тогда коэффициент [math]n_k[/math] определяется из уравнения, составленного приравниванием коэффициентов при [math]s^{k+1}[/math]: [math] n_k\, \tilde{l}_1^k + n_{k-1}\, \lambda_{k-1} + \ldots + n_1\, \lambda_1 = \tilde{l}_k. [/math] Здесь через [math]\lambda_i, \, i = 2, \ldots, k-1, [/math] обозначены коэффиценты при [math]s^{k}[/math] в производящих функциях [math] \tilde{l}^i (s) [/math]. Уравнение [math] n_k\, \tilde{l}_1^k + n_{k-1}\, \lambda_{k-1} + \ldots + n_1\, \lambda_1 = \tilde{l}_k. [/math] — линейное уравнение относительно [math] n_k [/math]. Коэффициент при [math] n_k [/math] в нем равен [math]\tilde{l}_1^k [/math] и, по условию теоремы, отличен от нуля. Поэтому [math]n_k[/math] однозначно определяется из уравнения [math] n_k\, \tilde{l}_1^k + n_{k-1}\, \lambda_{k-1} + \ldots + n_1\, \lambda_1 = \tilde{l}_k. [/math] С другой стороны, если задана функция [math]n(t)[/math], то мы должны положить [math]\tilde{l}_1 = n_0[/math]. Коэффициенты [math]\tilde{l}_k [/math] определяются теперь равенством [math] n_k\, \tilde{l}_1^k + n_{k-1}\, \lambda_{k-1} + \ldots + n_1\, \lambda_1 = \tilde{l}_k, [/math] так как все оэффициенты [math]\lambda_i[/math] являются многочленами от [math] \tilde{l}_1, \ldots, \tilde{l}_{k-1} [/math].

[math]\triangleleft[/math]

Замечание

Если коэффициенты функции [math]n[/math] —целые неотрицательные числа, то и коэффициенты функции [math]\tilde{l}[/math] будут целыми и неотрицательными. Если коэффициенты функции [math]\tilde{l}[/math] целые и неотрицательные, причем [math]\tilde{l}_1 = 1,[/math] то и коэффициенты функции [math]n[/math] оказываются целыми. Однако при этом среди них могут оказаться и отрицательные числа.

См. также

• Производящая функция
• Язык Дика
• Асимптотика коэффициентов функций, связанных между собой уравнением Лагранжа

Источники информации

• С. А. Ландо: Лекции о производящих функциях
• Гросс М., Лантен А.: Теория формальных грамматик