Уравнение Лагранжа и теорема Лагранжа — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Формальные грамматики с однозначным выводом)
(Метки: правка с мобильного устройства, правка из мобильной версии)
(См. также)
(не показаны 32 промежуточные версии этого же участника)
Строка 2: Строка 2:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
[[Основные определения, связанные со строками#string | Слово]] <tex>w = \beta_1 \ldots \beta_m</tex> [[Основные определения, связанные со строками#deflanguage | языка]] <tex>L</tex> называется '''неразложимым''' в этом языке, если никакое его непустое подслово <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>.
+
[[Основные определения, связанные со строками#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>.
 
}}
 
}}
  
Строка 13: Строка 13:
 
:4) если из любого слова языка <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> — '''производящую функцию для языка''' <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> оказываются целыми. Однако при этом среди них могут оказаться и отрицательные числа.
 +
 
 +
== См. также ==
 +
*[[Производящая функция]]
 +
*[[Язык Дика]]
 +
*[[Асимптотика коэффициентов функций, связанных между собой уравнением Лагранжа]]
 +
 
 +
== Источники информации ==
 +
* С. А. Ландо: Лекции о производящих функциях
 +
* Гросс М., Лантен А.: Теория формальных грамматик
 +
 
 +
 
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Производящая функция]]

Версия 12:29, 24 июня 2018

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

Определение:
Слово [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] оказываются целыми. Однако при этом среди них могут оказаться и отрицательные числа.

См. также

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

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