344
правки
Изменения
→Формальные грамматики с однозначным выводом
Обозначим через <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> .
{{Теорема
|statement=
Производящая функция для языка <tex>L</tex>, удовлетворяющего свойствам 1) — 4), и производящая функция для подъязыка неразложимых слов в нем связаны между собой уравнением Лагранжа <tex>l(s) = n(sl(s))</tex>.
|proof=
Каждому неразложимому слову <tex>\alpha_{i_1} \ldots \alpha_{i_m}</tex> в языке <tex>L</tex> сопоставим правило вывода
<tex>r \longrightarrow \alpha_{i_1}\, r\, \alpha_{i_2} \ldots \alpha_{i_m}\, r</tex>.
Ясно, что каждое слово языка допускает вывод по этим правилам. Такой вывод однозначен. Действительно, пусть <tex>\beta_1 \ldots \beta_k</tex> — произвольное слово языка <tex>L</tex>. если оно неразложимо, то оно представляется в виде правой части правила вывода
<tex>r \longrightarrow \beta_{1} r \beta_{2} \ldots \beta_{k} r,</tex>
где каждое вхождение символа <tex>r</tex> следует заменить на пустое слово. Из определения неразложимого слова вытекает, что такое представление единственно.
Предположим, что есть разложимые слова, допускающие различное представление. Рассмотрим самое короткое такое слово <tex>w</tex>. В нем содержится неразложимое подслово. Выберем из всех неразложимых подслов слова <tex>w</tex> самое правое (это возможно, так как неразложимые подслова не могут пересекаться) и выкинем его из слова <tex>w</tex>. Получим новое слово <tex>w'</tex>. Это слово имеет те же самые представления в виде правых частей правил вывода, что и слово <tex>w</tex>. Поэтому <tex>w'</tex> — более короткое слово, допускающее несколько различных представлений. Полученное противоречие доказывает единственность представления.
Таким образом, некоммутативная производящая функция для языка <tex>L</tex> удовлетворяет уравнению
<tex> \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</tex>
Делая подстановку <tex> \lambda = 1,\, a_i = t</tex> и учитывая, что <tex>l(t) = \mathcal{L}(t, t, \ldots, t),</tex> получаем заключение теоремы.
}}
