Уравнение Лагранжа и теорема Лагранжа — различия между версиями
Senya (обсуждение | вклад) (→Уравнение Лагранжа и теорема Лагранжа) (Метки: правка с мобильного устройства, правка из мобильной версии) |
м (rollbackEdits.php mass rollback) |
||
(не показано 16 промежуточных версий 2 участников) | |||
Строка 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> . |
{{Теорема | {{Теорема | ||
Строка 48: | Строка 48: | ||
}} | }} | ||
+ | == Уравнение Лагранжа и теорема Лагранжа == | ||
+ | Часто для нахождения числа слов определенной длины в заданном языке выгодно найти производящую функцию этого языка. | ||
+ | Посмотрим на равенство <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''). | Рассмотрим уравнение <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''). | ||
Строка 55: | Строка 57: | ||
{{Теорема | {{Теорема | ||
|author=Лагранж | |author=Лагранж | ||
+ | |about=(англ. ''the Lagrange theorem'') | ||
|statement= | |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>. Тогда вторая производящая функция однозначно восстанавливается по ней. | Пусть в уравнении <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>. Тогда вторая производящая функция однозначно восстанавливается по ней. | ||
Строка 68: | Строка 71: | ||
Коэффицент <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_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{ | + | <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 | + | Здесь через <tex>\lambda_i, \, i = 2, \ldots, k-1, </tex> обозначены коэффиценты при <tex>s^{k}</tex> в производящих функциях <tex> \tilde{l}^i (s) </tex>. Уравнение |
− | <tex> n_k\, \tilde{ | + | <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{ | + | — линейное уравнение относительно <tex> n_k </tex>. Коэффициент при <tex> n_k </tex> в нем равен <tex>\tilde{l}_1^k </tex> и, по |
− | условию теоремы, отличен от нуля. Поэтому <tex> n_k </tex> однозначно определяется из уравнения | + | условию теоремы, отличен от нуля. Поэтому <tex>n_k</tex> однозначно определяется из уравнения |
− | <tex> n_k\, \tilde{ | + | <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{ | + | С другой стороны, если задана функция <tex>n(t)</tex>, то мы должны положить <tex>\tilde{l}_1 = n_0</tex>. Коэффициенты <tex>\tilde{l}_k </tex> определяются теперь равенством |
− | <tex> n_k\, \tilde{ | + | <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> оказываются целыми. Однако при этом среди них могут оказаться и отрицательные числа. | ||
+ | |||
+ | == См. также == | ||
+ | *[[Производящая функция]] | ||
+ | *[[Язык Дика]] | ||
+ | *[[Асимптотика коэффициентов функций, связанных между собой уравнением Лагранжа]] | ||
+ | |||
+ | == Источники информации == | ||
+ | * С. А. Ландо: Лекции о производящих функциях | ||
+ | * Гросс М., Лантен А.: Теория формальных грамматик | ||
+ | |||
+ | |||
+ | [[Категория: Дискретная математика и алгоритмы]] | ||
+ | [[Категория: Производящая функция]] |
Текущая версия на 19:42, 4 сентября 2022
Формальные грамматики с однозначным выводом
Определение: |
Слово языка называется неразложимым (англ. indecomposable word) в этом языке, если никакое его непустое подслово отличное от самого слова не принадлежит языку . |
В частности, пустое слово в любом языке неразложимо.
Предположим, что язык
обладает следующими свойствами:- 1) пустое слово входит в язык
- 2) начало всякого неразложимого слова не совпадает с концом другого или того же самого неразложимого слова
- 3) если между любыми двумя буквами любого слова языка вставить слово языка , то получится слово языка
- 4) если из любого слова языка выкинуть подслово, входящее в язык , то получится слово языка
Обозначим через производящую функцию для числа неразложимых слов языка , через — производящую функцию для языка .
Теорема: |
Производящая функция для языка , удовлетворяющего свойствам 1) — 4), и производящая функция для подъязыка неразложимых слов в нем связаны между собой уравнением Лагранжа . |
Доказательство: |
Каждому неразложимому слову в языке сопоставим правило вывода. Ясно, что каждое слово языка допускает вывод по этим правилам. Такой вывод однозначен. Действительно, пусть — произвольное слово языка . если оно неразложимо, то оно представляется в виде правой части правила вывода
где каждое вхождение символа следует заменить на пустое слово. Из определения неразложимого слова вытекает, что такое представление единственно.Предположим, что есть разложимые слова, допускающие различное представление. Рассмотрим самое короткое такое слово . В нем содержится неразложимое подслово. Выберем из всех неразложимых подслов слова самое правое (это возможно, так как неразложимые подслова не могут пересекаться) и выкинем его из слова . Получим новое слово . Это слово имеет те же самые представления в виде правых частей правил вывода, что и слово . Поэтому — более короткое слово, допускающее несколько различных представлений. Полученное противоречие доказывает единственность представления.Таким образом, некоммутативная производящая функция для языка Делая подстановку удовлетворяет уравнению и учитывая, что получаем заключение теоремы. |
Теорема: |
Пусть Γ — грамматика с однозначным выводом.
Обозначим через производящую функцию для числа слов в языке выводимого из символа . Тогда производящие функции удовлетворяют системе уравнений |
Доказательство: |
Поступим, как и в ситуации с одним порождающим символом, — введем некоммутативные производящие степенные ряды для каждого из языков Делая подстановку . Ввиду однозначности представления каждого слова в виде правой части правила вывода получаем систему уравнений на некоммутативные ряды. при получаем систему уравнений на производящие функции для числа слов. |
Уравнение Лагранжа и теорема Лагранжа
Часто для нахождения числа слов определенной длины в заданном языке выгодно найти производящую функцию этого языка. Посмотрим на равенство
. Это функциональное уравнение, связывающее между собой производящие функции для числа слов в языке и числа неразложимых слов в нем. Хотелось бы уметь находить одну из этих функций, зная другую, то есть уметь решать это уравнение, если одна из функций задана. Это всегда возможно.
Рассмотрим уравнение . Чтобы привести к классическому виду, домножим обе части на и положим . Тогда уравнение примет вид — уравнение Лагранжа (англ. Lagrange equation).
Теорема (Лагранж, (англ. the Lagrange theorem)): |
Пусть в уравнении задана одна из производящих функций или . Тогда вторая производящая функция однозначно восстанавливается по ней. |
Доказательство: |
Уравнение можно переписать в следующем виде:
Докажем сначала, что если функция задана, то однозначно восстанавливается по ней. Доказательство проведем по индукции, приравнивая последовательно коэффициенты при одинаковых степенях в левой и правой частях.Коэффицент определяется равенством . Предположим теперь, что коэффициенты уже определены. Тогда коэффициент определяется из уравнения, составленного приравниванием коэффициентов при :
Здесь через обозначены коэффиценты при в производящих функциях . Уравнение
— линейное уравнение относительно . Коэффициент при в нем равен и, по условию теоремы, отличен от нуля. Поэтому однозначно определяется из уравнения
С другой стороны, если задана функция , то мы должны положить . Коэффициенты определяются теперь равенством так как все оэффициенты являются многочленами от . |
Замечание
Если коэффициенты функции
—целые неотрицательные числа, то и коэффициенты функции будут целыми и неотрицательными. Если коэффициенты функции целые и неотрицательные, причем то и коэффициенты функции оказываются целыми. Однако при этом среди них могут оказаться и отрицательные числа.См. также
Источники информации
- С. А. Ландо: Лекции о производящих функциях
- Гросс М., Лантен А.: Теория формальных грамматик