344
правки
Изменения
Нет описания правки
== Определения ==
{{Определение
|id=def1
|definition='''Язык Дика''' (англ. ''Dyck language'') — множество [[Правильные скобочные последовательности#Определения |правильных скобочных структур]] вместе с пустой структурой, образующее язык над алфавитом <tex>\{a, b\}</tex>.
}}
{{Определение
|id=def3
|neat = 1
|definition='''Производящей функцией''' (англ. generating function) '''языка''' <tex>L</tex> называется производящая функция <tex>L(s) = l_0 + l_1 s + l_2 s^2 + \ldots,</tex> где <tex>l_k</tex> есть число слов длины <tex>k</tex> в языке <tex>L</tex>.
}}
== Правила вывода в языке Дика ==
Рассмотрим два ''правила вывода в языке Дика:''
: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>, то эту букву можно заменить на слово, стоящее справа от стрелки.''
