Изменения

|id=идентификатор (необязательно), пример: def1. |neat = 1 - параметр нужен для того, чтобы определение не растягивалось на всю страницу(не обязательно)def2|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> называется '''длиной слова'''. '''Языком'Dyck language'' ) — множество [[Правильные скобочные последовательности#Определения |правильных скобочных структур]] вместе с пустой структурой, образующее [[Основные определения, связанные со строками#deflanguage | язык]] над [[Основные определения, связанные со строками#alphabet | алфавитом ]] <tex>A</tex> называется произвольное (конечное или бесконечное) множество слов в алфавите <tex>A\{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>.}} __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>D(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> записана сумма всех слов языка Дика. Равенство означает справедливость утверждения: Всякое слово в языке Дика есть либо:1) пустое слово,:2) слово, в котором внутри самой левой пары соответственных скобок стоит некоторое слово языка Дика и после этой пары стоит слово языка Дика.При этом такое представление единственно.}} Чтобы перейти от '''некоммутативного''' производящего ряда к '''обычному''', сделаем подстановку <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>: мы перечисляем слова по числу скобок, а не ''пар'' скобок. == См. также ==*[[Производящая функция]]*[[Числа Каталана]]*[[Правильные скобочные последовательности]]*[[Уравнение Лагранжа и может входить или не входить в языктеорема Лагранжа]] == Источники информации == * С. А. Ландо: Лекции о производящих функциях* Гросс М., Лантен А.: Теория формальных грамматик [[Категория: Дискретная математика и алгоритмы]][[Категория: Производящая функция]]