Структуры данных и модели вычислений
формальные языки над некоторым алфавитом
Рассмотрим уравнение вида , где и — формальные языки над некоторым алфавитом .
Теорема.
Если , то уравнение
имеет единственное решение . Если , то
будет решением уравнения при любом .
Доказательство.
Пусть и — решение, тогда, подставляя его в уравнение, получим
Продолжая выполнять подстановки, видим, что при любом
выполняется равенство
(1) |
Покажем сначала, что . Действительно, пусть , тогда при некотором значении получим и из (1) при таком значении
получаем .
Осталось показать, что . Действительно, пусть , тогда при любом
Но так как , то при достаточно больших значениях
каждое слово в множестве будет длиннее слова
и, следовательно, , но тогда при таких
Следовательно, . Итак, мы показали, что если — решение, то оно задается формулой , то есть является единственным. Тот факт, что
на самом деле — решение, проверяется простой подстановкой. Второе утверждение теоремы предоставляем доказать читателю.
Замечание.
Если в уравнении под и
понимать регулярные выражения, то в случае
его единственным решением будет регулярное выражение .
В случае, когда содержит , уравнение имеет бесконечно много решений вида , но здесь под можно понимать не только регулярные выражения, но и выражения в каком-либо формализме, задающие произвольный язык. Часто в таком случае интересуются наименьшим по включению решением, так называемой "наименьшей неподвижной точкой".
Системы линейных уравнений с регулярными коэффициентми.
Под стандартной системой понимают систему вида
где , — регулярные выражения, — переменные ().
Решением системы называется набор формальных языков, которые при подстановке вместо соответствующих переменных в уравнения обращают их в равенства. Удобно на решение смотреть как на отображение , которое каждой переменной ставит в соответствие язык . Решение называется наименьшей неподвижной точкой системы, если для любого другого решения выполняются соотношения при .
Теорема.
Каждая стандартная система уравнений имеет единственную неподвижную точку.
Доказательство.
Действительно, нетрудно видеть, что отображение , определяемое по формулам , где пересечение берется по всем решениям (, является искомой неподвижной точкой системы.
Решаются такие системы уравнений методом исключения неизвестных. Если, например, , то первое уравнение можно представить в виде , где , записать его решение описанным выше способом в виде и подставить в остальные уравнения. Получим систему с меньшим числом неизвестных и так далее.
