344
правки
Изменения
→Формальные грамматики с однозначным выводом
[[Основные определения, связанные со строками#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>.
}}
В частности, пустое слово в любом языке неразложимо.
Предположим, что язык <tex>L</tex> обладает следующими свойствами:
:1) пустое слово входит в язык <tex>L</tex>
:2) начало всякого неразложимого слова не совпадает с концом другого или того же самого неразложимого слова
:3) если между любыми двумя буквами любого слова языка <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> .
