Структуры данных и модели вычислений

         

Решение уравнений в словах


Рассмотрим уравнение вида , где и — формальные языки над некоторым алфавитом .

Теорема.

Если , то уравнение

имеет единственное решение . Если , то

будет решением уравнения при любом .

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

Пусть и — решение, тогда, подставляя его в уравнение, получим

Продолжая выполнять подстановки, видим, что при любом

выполняется равенство

(1)

Покажем сначала, что . Действительно, пусть , тогда при некотором значении получим и из (1) при таком значении

получаем .

Осталось показать, что . Действительно, пусть , тогда при любом

Но так как , то при достаточно больших значениях

каждое слово в множестве будет длиннее слова

и, следовательно, , но тогда при таких

Следовательно, . Итак, мы показали, что если — решение, то оно задается формулой , то есть является единственным. Тот факт, что

на самом деле — решение, проверяется простой подстановкой. Второе утверждение теоремы предоставляем доказать читателю.

Замечание.

Если в уравнении под и

понимать регулярные выражения, то в случае

его единственным решением будет регулярное выражение .

В случае, когда содержит , уравнение имеет бесконечно много решений вида , но здесь под можно понимать не только регулярные выражения, но и выражения в каком-либо формализме, задающие произвольный язык. Часто в таком случае интересуются наименьшим по включению решением, так называемой "наименьшей неподвижной точкой".

Системы линейных уравнений с регулярными коэффициентми.

Под стандартной системой понимают систему вида

где , — регулярные выражения, — переменные ().

Решением системы называется набор формальных языков, которые при подстановке вместо соответствующих переменных в уравнения обращают их в равенства. Удобно на решение смотреть как на отображение , которое каждой переменной ставит в соответствие язык . Решение называется наименьшей неподвижной точкой системы, если для любого другого решения выполняются соотношения при .

Теорема.

Каждая стандартная система уравнений имеет единственную неподвижную точку.

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

Действительно, нетрудно видеть, что отображение , определяемое по формулам , где пересечение берется по всем решениям (, является искомой неподвижной точкой системы.

Решаются такие системы уравнений методом исключения неизвестных. Если, например, , то первое уравнение можно представить в виде , где , записать его решение описанным выше способом в виде и подставить в остальные уравнения. Получим систему с меньшим числом неизвестных и так далее.



Содержание  Назад  Вперед