Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
A = abaaaabbababbbaab.
Один возможный для этого слова ряд последовательных сокращений отвечает следующей схеме:
A — abaaaabbababbbaab,
2 2 1 1 6 6 4 4
3 3 5 5
А ~ a b a b а.
Имеются и другие способы сократить это слово, например:
А ~ abaaaabbababbbaab,
Il 3 3 4 4 5 5
2 2 6 6
А ~ a b a b а.
Интуитивно ясно, что результат не зависит от того, в каком порядке мы выполняем сокращения. Это видно из примера; доказательство же этого факта мы предоставляем читателю в качестве упражнения. Таким образом, в каждом классе эквивалентности существует ровно одно несократимое слово, которое естественно считать каноническим представителем этого класса.
Поэтому для данного ассоциативного исчисления проблема эквивалентности разрешима: любые два слова эквивалентны тогда и только тогда, когда они обладают одним и тем же каноническим представителем, т. е. когда они эквивалентны одному и тому же несократимому слову, которое нетрудно найти с помощью механизируемого процесса (процесса сокращения). Гл. I. Слова (цепочки). Полугруппы. Языки
21
Однако далеко не всегда ситуация бывает столь благоприятной. Рассмотрим, например, тот же алфавит {а, b} и соотношения
ааа~аа, aba~aa, bab~bb, bbb~bb.
Из слова ababa можно получить или слово ааа, а затем аа, или abba. Слова аа и abba эквивалентны, несократимы и различны.
Проблема эквивалентности разрешима, когда в классах эквивалентности существуют инварианты.
«Универсальный» метод решения проблемы эквивалентности, который прежде всего приходит в голову, состоит в следующем: взяв произвольную пару слов SnT, последовательно образовать все слова, смежные с S, потом все слова, смежные с каждым из слов, полученных на первом шаге, и т. д., т. е., короче говоря, перечислить все слова, эквивалентные слову S, применяя сначала одно, потом два, потом три преобразования и т. д., пока мы не дойдем до Т. Однако сколько бы преобразований ни было выполнено, тот факт, что T не найдено, еще ничего не означает: оно может быть получено после очередных преобразований. Таким образом, наш наивный «универсальный» метод не гарантирует нахождения решения.
Возникает вопрос: существует ли настоящий универсальный метод, позволяющий решать проблему эквивалентности слов? После того как мы уточним представление о методе решения вообще — точнее, введем понятие алгоритма, — можно будет показать, что ответ на этот вопрос является отрицательным.
1.2.4. Полугруппа классов
Пусть в некотором ассоциативном исчислении имеют место соотношения S »5 S' и T as T'. Тогда (в силу теоремы, сформулированной в п. 1.2.1) мы имеем
ST « ST ~ ST,
откуда
ST « ST.
Таким образом, доказана следующая
Лемма. Отношение эквивалентности в смысле Туэ сохраняется при операции конкатенации слов.
Если отношение эквивалентности совместимо влево и вправо с полугрупповой операцией, его называют конгруэнцией1). Предыдущая лемма может быть сформулирована еще и так:
Эквивалентность в смысле Туэ есть конгруэнция на свободной полугруппе.
В алгебре широко используется следующая
') Отношение эквивалентности ~ называется совместимым влево (вправо) с операцией если из А ~ В следует С -А ~ С -В (Л • С ~ B-C).- Прим. ред. 22
Часть /. Предварительные сведения из логики и алгебры
Теорема. Конгруэнция Ш, определенная на множестве М, снабженном ассоциативной бинарной операцией, определяет множество классов эквивалентности, или фактормножество M/ffi, которое в свою очередь снабжено индуцированной бинарной ассоциативной операцией. (Определение этой операции см. ниже в упр. 1.4.4.)
Если при этом исходная операция обладает единичным элементом, то класс этого элемента будет единичным элементом для индуцированной операции.
Доказательство этой фундаментальной теоремы намечено в упр. 1.4.4.
Для интересующего нас случая — эквивалентности Туэ на свободной полугруппе — только что сформулированное утверждение имеет следующий вид:
Теорема. Классы, определяемые на свободной полугруппе эквивалентностью Туэ, образуют полугруппу относительно операции, индуцированной конкатенацией.
Пример. % ={а, ?>}; аа ~ Е, bb ~ Е. Этот пример уже рассматривался в п. 1.2.3.
Здесь классы можно представлять в канонической форме с помощью сокращенных слов, в которых любые два последовательных вхождения обязательно являются вхождениями разных букв. Упорядочив эти сокращенные слова по возрастанию длин, — причем слова одинаковой длины упорядочиваются лексикографически,— мы получаем следующие классы:
Е, а, b, ab, ba, aba, bab, abab, ....
Пусть нам даны в некотором фиксированном порядке два класса; тогда для нахождения представителя композиции этих классов необходимо действовать в соответствии со следующими правилами:
1. Выполнить конкатенацию канонических представителей исходных классов в заданном порядке.
2. Рассмотреть вхождения «на стыке».
3. Если буквы «на стыке» различны, операция закончена.
В противном случае: стереть два соседних вхождения одной и той же буквы.
4. Если результат равен Е, операция закончена. В противном случае: перейти к правилу 2.
