Уравнение Лагранжа и теорема Лагранжа

Формальные грамматики с однозначным выводом

Определение:

Слово [math]w = \beta_1 \ldots \beta_m[/math] языка [math]L[/math] называется неразложимым в этом языке, если никакое его непустое подслово [math] \beta_i \beta_{i+1} \ldots \beta_{i+l},\, 1 \leqslant i,\, i + l \leqslant m,\, l \geqslant 0,[/math] отличное от самого слова [math]w,[/math] не принадлежит языку [math]L[/math].

В частности, пустое слово в любом языке неразложимо.

Предположим, что язык [math]L[/math] обладает следующими свойствами:

1) пустое слово входит в язык [math]L[/math]

2) начало всякого неразложимого слова не совпадает с концом другого или того же самого неразложимого слова

3) если между любыми двумя буквами любого слова языка [math]L[/math] вставить слово языка [math]L[/math], то получится слово языка [math]L[/math]

4) если из любого слова языка [math]L[/math] выкинуть подслово, входящее в язык [math]L[/math], то получится слово языка [math]L[/math]

Обозначим через [math]n(t) = n_0 + n_1 t + n_2 t^2 + \ldots,[/math] производящую функцию для числа неразложимых слов языка [math]L[/math], через [math]L(s) = l_0 + l_1 s + l_2 s^2 + \ldots,[/math] — производящую функцию для языка [math]L[/math] .