344
правки
Изменения
Нет описания правки
{{Определение
|id=def1def2|neat definition= 1'''Язык Дика''' (англ. ''Dyck language'') — множество [[Правильные скобочные последовательности#Определения |правильных скобочных структур]] вместе с пустой структурой, образующее [[Основные определения, связанные со строками#deflanguage | язык]] над [[Основные определения, связанные со строками#alphabet |definition=Пусть алфавитом]] <tex>A = \{a_1, a_2a, \ldots , a_kb\}</tex> — произвольный конечный набор различных букв. }} {{Определение|id=def3|definition='''Производящей функцией''' (англ. generating function) '''Словомязыка''' в алфавите <tex>AL</tex> называется произвольная конечная последовательность буквa [[Производящая функция | производящая функция]] <tex>a_1 a_2 L(s) = l_0 + l_1 s + l_2 s^2 + \ldots a_m,</tex> где <tex>a_i \in A , i = 1, \ldots , ml_k</tex>. Число есть число [[Основные определения, связанные со строками#string | слов]] длины <tex>mk</tex> называется '''длиной слова'''. '''Языком''' над алфавитом <tex>A</tex> называется произвольное (конечное или бесконечное) множество слов в алфавите языке <tex>AL</tex>.
}}
__TOC__ == Правила вывода в языке Дика == Язык Дика является [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора#lang | контекстно-свободным языком]]. Рассмотрим два ''правила вывода в языке Дика:'':1) <tex>r \longrightarrow \lambda</tex>:2) <tex>r \longrightarrow arbr,</tex>где <tex>r</tex> — буква, не входящая в алфавит <tex>\{a, b\}</tex>, стрелка <tex>\longrightarrow</tex> заменяет фразу: ''Пустое если в слове есть буква <tex>r</tex>, то эту букву можно заменить на слово, стоящее справа от стрелки.'' Правила вывода можно понимать следующим образом: Всякое слово в языке Дика есть либо:1) пустое слово,:2) слово, в котором внутри самой левой пары соответственных скобок стоит некоторое словоязыка Дика и после этой пары стоит слово языка Дика. Ясно, что для каждого слова такое представление единственно. == Производящая функция для языка Дика == Вычислим с помощью правил вывода производящую функцию для языка Дика. Для этой цели выпишем '''некоммутативный производящий ряд''' , перечисляющий слова языка. Этот ряд представляет собой формальную сумму всех слов языка, выписанных в порядке возрастания длины: <tex>D(a, b) = \lambda+ ab + aabb + abab + aaabbb + aababb + \ldots</tex> имеет длину {{Теорема|id=th1 |author=|about=|statement=Ряд <tex>0D(a, b) = \lambda + ab + aabb + abab + aaabbb + aababb + \ldots</tex> и может входить или не входить удовлетворяет уравнению <tex>D(a, b) = \lambda + aD(a, b)bD(a, b)</tex>.|proof=Действительно, в языклевой части равенства <tex>D(a, b) = \lambda + aD(a, b)bD(a, b)</tex> записана сумма всех слов языка Дика.Равенство означает справедливость утверждения:
}}
Чтобы перейти от '''некоммутативного''' производящего ряда к '''обычному''', сделаем подстановку <tex>a = s,\,b = s,\, \lambda = s^0 = 1</tex>. Уравнение <tex>D(a, b) = \lambda + aD(a, b)bD(a, b)</tex> примет вид <tex>D(s, s) = 1 + s^2D(s, s)</tex>.
Отсюда, обозначив <tex>D(s, s)</tex> через <tex>d(s),</tex> получим <tex>d(s) = 1 + s^2d(s)^2</tex>
Решение <tex>d(s) = \dfrac{1 - \sqrt{1 - 4s^2}}{2s^2}</tex>
этого уравнения совпадает с производящей функцией для [[Числа Каталана#Вычисление производящей функции чисел Каталана | чисел Каталана]]. Необходимость подстановки <tex>s^2</tex> вместо <tex>s</tex> объясняется тем, что в языке Дика длина слова, составленного из <tex>n</tex> пар скобок, равна <tex>2n</tex>: мы перечисляем слова по числу скобок, а не ''пар'' скобок.
== См. также ==
*[[Производящая функция]]
*[[Числа Каталана]]
*[[Правильные скобочные последовательности]]
*[[Уравнение Лагранжа и теорема Лагранжа]]
== Источники информации ==
* С. А. Ландо: Лекции о производящих функциях
* Гросс М., Лантен А.: Теория формальных грамматик
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Производящая функция]]
