1632
правки
Изменения
м
{{Определение
|id=def1
|definition=Пусть <tex>A = \{a_1, a_2, \ldots , a_k\}</tex> — произвольный конечный набор различных букв. '''Словом''' в алфавите <tex>A</tex> называется произвольная конечная последовательность буквa <tex>a_1 a_2 \ldots a_m,</tex> где <tex>a_i \in A , i = 1, \ldots , m</tex>. Число <tex>m</tex> называется '''длиной слова'''. '''Языком''' над алфавитом <tex>A</tex> называется произвольное (конечное или бесконечное) множество слов в алфавите <tex>A</tex>.
}}
'''Пустое слово''' <tex>\lambda</tex> имеет длину <tex>0</tex> и может входить или не входить в язык.
rollbackEdits.php mass rollback
{{Определение
|id=def2
|definition='''Язык Дика''' (англ. ''Dyck language'') — множество [[Правильные скобочные последовательности#Определения |правильных скобочных структур]] вместе с пустой структурой, образующее [[Основные определения, связанные со строками#deflanguage | язык ]] над [[Основные определения, связанные со строками#alphabet | алфавитом ]] <tex>\{a, b\}</tex>.
}}
{{Определение
|id=def3
|definition='''Производящей функцией''' (англ. generating function) '''языка''' <tex>L</tex> называется [[Производящая функция | производящая функция ]] <tex>L(s) = l_0 + l_1 s + l_2 s^2 + \ldots,</tex> где <tex>l_k</tex> есть число [[Основные определения, связанные со строками#string | слов ]] длины <tex>k</tex> в языке <tex>L</tex>.
}}
== Правила вывода в языке Дика ==
Язык Дика является [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора#lang | контекстно-свободным языком]].
Рассмотрим два ''правила вывода в языке Дика:''
:1) <tex>r \longrightarrow \lambda</tex>
|proof=
Действительно, в левой части равенства <tex>D(a, b) = \lambda + aD(a, b)bD(a, b)</tex> записана сумма всех слов языка Дика. Равенство означает справедливость утверждения:
Всякое слово в языке Дика есть либо
:1) пустое слово,
}}
Чтобы перейти от '''некоммутативного ''' производящего ряда к '''обычному''', сделаем подстановку <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>: мы перечисляем слова по числу скобок, а не ''пар'' скобок.
== См. также ==
*[[Производящая функция]]
*[[Числа Каталана]]
*[[Правильные скобочные последовательности]]
*[[Уравнение Лагранжа и теорема Лагранжа]]
== Источники информации ==
* С. А. Ландо: Лекции о производящих функциях
* Гросс М., Лантен А.: Теория формальных грамматик
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Производящая функция]]
