Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
{ambn I 1, n^l}, соответствующего состоянию S2, н языка
{apb"ar I 1, <7^1, г>1}, соответствующего состоянию S3.
Итак, мы показали, что для всякой свободной полугруппы существуют язык L и отношение эквивалентности SЯ, такие, что
1. SЯ совместимо вправо (соответственно влево) с конкатенацией.
2. L представляет собой объединение классов эквивалентности по СІ.
3. St имеет конечный индекс.
Мы знаем, однако, что отношение эквивалентности по допустимым концам относительно L (п. 13.2.3) обладает свойствами 1 и 2, а также что эта эквивалентность — наименее тонкая из всех экви-валентностей, обладающих этими свойствами (п. 13.2.4); поэтому индекс эквивалентности по допустимым концам — наименьший среди индексов эквивалентностей, обладающих указанными свойствами. Отсюда сразу вытекает
Следствие. Отношение эквивалентности по допустимым концам относительно А-языка L имеет конечный индекс. 222
Часть III. Алгебраический подход
14.3.3. Автомат с минимальным числом состояний
Докажем теперь обратное утверждение.
Допустим, что индекс отношения Зі, (эквивалентности по допустимым концам относительно L) конечен. Покажем, что в таком случае L обязательно является А-языком. Фактормножество 91 VSi, конечно; построим автомат, обладающий тем свойством, что между его состояниями и классами, образующими множество 9l*/3i,, можно установить взаимно однозначное соответствие.
Пусть А є 91*; обозначим через A класс цепочки А и через [A] — состояние, отвечающее Л. Пустой цепочке E соответствует класс E и состояние [?], которое мы объявим начальным; цепочкам MeL будут соответствовать заключительные состояния.
Функция переходов f определяется условием
f(at, [М]) =[Ш(].
Легко видеть, что все цепочки языка L, и только они, могут быть прочтены автоматом так, что в начале чтения он находится в состоянии [Ё], а в конце — в одном из состояний [М], таких, что Af є L; иначе говоря, автомат допускает язык L. Таким образом, L есть А-язык. Кроме того, поскольку число состояний построенного автомата равно индексу отношения Зі., этот автомат минимален ').
Итак, доказана
Теорема. Если индекс отношения эквивалентности по допустимым концам конечен, то соответствующий язык является автоматным. Существует канонический способ построения такого автомата с минимальным числом состояний, который допускает данный язык.
14.3.4. Конгруэнция, определяемая конечным автоматом
Пусть имеется конечный автомат с алфавитом 91. Определим на 91* отношение ©, как в п. 14.3.2. Там же было показано, что это отношение является эквивалентностью, совместимой вправо с кон-
') Минимальность понимается здесь в следующем смысле: никакой (детерминированный) конечный автомат, допускающий тот же язык L, не может иметь меньше состояний, мрм данный Чтобы убедиться в этом, достаточно показать, что, каковы бы ни были автомат А, допускающий язык L1 и цепочки M и N, принадлежащие разным классам по отношению Ql, автомат А не может, начав чтение M и N в начальном состоянии S0, заканчивать его в одном и том же состоянии. Но если бы чтение M и N, начатое в состоянии S0, заканчивалось в одном и том же состоянии Sj, то (поскольку автомат в силу его детерминированности может прочесть цепочку, начиная с S0, только одним способом) допустимыми концами и для М, и для N были бы те и только те цепочки, которые автомат может прочесть, начиная чтение в состоянии Sj и заканчивая его в одном из заключительных состояний, так что M и N принадлежали бы одному классу по 3 L- — Прим ред. Гл. XIV. Дополнительные сведения об автоматных языках 223
катенацией. Однако оно совместимо с конкатенацией также и влево, поскольку из А®В следует, что
fg(CA, St) = fg(A, f(C, Si)) = fg(B, ЦС, Si)) = fg(CB, Si).
Таким образом, © есть конгруэнция.
Если данный автомат допускает язык L, то отношение © в силу теоремы п. 13.2.2 является не менее тонким, чем отношение =L. Однако число классов по © конечно, и тем более это верно для =l. Итак, получена
Теорема. Для всякого А-языка конгруэнция по допустимым контекстам имеет конечный индекс.
14.3.5. Обратная теорема
Возникает следующая проблема.
Пусть L — такой язык, что отношение =L имеет конечный индекс и при этом L есть объединение некоторых классов эквивалентности по =Z,. Можно ли построить конечный автомат, допускающий L? Другими словами, является ли L А-языком?
Эта проблема немедленно сводится к другой, решенной в п. 14.3.3. Действительно, конгруэнция по допустимым контекстам, будучи совместимой с конкатенацией вправо, является эквивалентностью, не менее тонкой, чем эквивалентность по допустимым концам. А поскольку индекс отношения =L конечен, то индекс отношения Sl также оказывается конечным. Стало быть, к 3l применима теорема пункта 14.3.3. Мы получаем следующую теорему:
Теорема. Для того чтобы язык L был автоматным, необходимо и достаточно, чтобы конгруэнция по допустимым контекстам относительно L имела конечный индекс.
Мы видели, однако, что отношение =L есть наименее тонкая из всех конгруэнций, относительно которых L является объединением классов. Поэтому для того, чтобы индекс отношения =l был конечным, достаточно, чтобы был конечен индекс хотя бы одной из таких конгруэнций. Это позволяет нам сформулировать
