Дискретная математика: графы и автоматы. Альпин Ю.А - 66 стр.

66                                            Глава 4. Теория автоматов




                                Рис. 3

   Теорема 2. Пусть множество W попарно различимых отно-
сительно L слов обладает свойствами:
   1) e ∈ W ,
   2) ∀p ∈ W ∀x ∈ X ∃q ∈ W px ∼ q(L).
   Тогда W — базис отношения ∼ (L).
     Д о к а з а т е л ь с т в о. Достаточно показать, что любое слово
эквивалентно некоторому слову из W . Применим индукцию по длине
слов. Для слов длины 0, то есть, для e, утверждение верно в силу 1).
Пусть оно верно для слов длины k. Рассмотрим произвольное слово p
длины k+1. Представим его в виде p = p0 x, x ∈ X. По предположению
индукции p0 ∼ q для некоторого q ∈ W . Из леммы 2 выводим p =
p0 x ∼ qx. Для слова qx ввиду 2) найдется слово r ∈ W такое, что
qx ∼ r. Поскольку отношение ∼ транзитивно, то
                   p ∼ qx, qx ∼ r ⇒ p ∼ r ∈ W,
что и завершает доказательство. ¤
    Если базис вычислен и каждому базисному слову p и каждой бук-
ве x ∈ X сопоставлено базисное слово q, где q ∼ px, то тем самым
                                   e = [px] = [q].
определена функция перехода: [p]δ(x)
    Метод нахождения базиса и одновременного построения таблицы
функции перехода автомата A(L)e    заключается в следующем.
    Строки таблицы соответствуют базисным словам, столбцы — бук-
вам алфавита. Вначале имеется одно базисное слово e и таблица имеет
одну строку (незаполненную). Опишем общий шаг заполнения табли-
цы. Находим первую, считая сверху, незаполненную строку и в ней —
первую, считая слева, пустую клетку. Пусть строка соответствует сло-
ву p, а клетка стоит в столбце, соответствующем букве x. Проверяем,
есть ли среди слов, уже зачисленных в базис, слово, эквивалентное
px. Если есть – вписываем его в указанную пустую клетку, а если
нет – вписываем в неё px. Объявляем слово px базисным и добавляем
соответствующую ему строку к таблице.