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

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

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

Слово [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] .

Теорема:

Производящая функция для языка [math]L[/math], удовлетворяющего свойствам 1) — 4), и производящая функция для подъязыка неразложимых слов в нем связаны между собой уравнением Лагранжа [math]l(s) = n(sl(s))[/math].

Доказательство:

[math]\triangleright[/math]

Каждому неразложимому слову [math]\alpha_{i_1} \ldots \alpha_{i_m}[/math] в языке [math]L[/math] сопоставим правило вывода [math]r \longrightarrow \alpha_{i_1}\, r\, \alpha_{i_2} \ldots \alpha_{i_m}\, r[/math]. Ясно, что каждое слово языка допускает вывод по этим правилам. Такой вывод однозначен. Действительно, пусть [math]\beta_1 \ldots \beta_k[/math] — произвольное слово языка [math]L[/math]. если оно неразложимо, то оно представляется в виде правой части правила вывода [math]r \longrightarrow \beta_{1} r \beta_{2} \ldots \beta_{k} r,[/math] где каждое вхождение символа [math]r[/math] следует заменить на пустое слово. Из определения неразложимого слова вытекает, что такое представление единственно. Предположим, что есть разложимые слова, допускающие различное представление. Рассмотрим самое короткое такое слово [math]w[/math]. В нем содержится неразложимое подслово. Выберем из всех неразложимых подслов слова [math]w[/math] самое правое (это возможно, так как неразложимые подслова не могут пересекаться) и выкинем его из слова [math]w[/math]. Получим новое слово [math]w'[/math]. Это слово имеет те же самые представления в виде правых частей правил вывода, что и слово [math]w[/math]. Поэтому [math]w'[/math] — более короткое слово, допускающее несколько различных представлений. Полученное противоречие доказывает единственность представления. Таким образом, некоммутативная производящая функция для языка [math]L[/math] удовлетворяет уравнению [math] \mathcal{L} (a_1, \ldots , a_m) = \lambda + \alpha_{11}\, \mathcal{L}\, (a_1, \ldots , a_m)\, \alpha_{12}\, \mathcal{L} (a_1, \ldots , a_m) \ldots + \ldots[/math] Делая подстановку [math] \lambda = 1,\, a_i = t[/math] и учитывая, что [math]l(t) = \mathcal{L}(t, t, \ldots, t),[/math] получаем заключение теоремы.

[math]\triangleleft[/math]

Теорема:

Пусть Γ — грамматика с однозначным выводом. Обозначим через [math]r_i(s)[/math] производящую функцию для числа слов в языке [math]L_i,[/math] выводимого из символа [math]r_i[/math]. Тогда производящие функции [math]r_i[/math] удовлетворяют системе уравнений [math]r_i(s) = \sum_{j} s^{\nu ij} \, \prod_{k} r_k^{\eta kj} (s) [/math]

Доказательство:

[math]\triangleright[/math]

доказательство (необязательно)

[math]\triangleleft[/math]