ВУЗ:
Составители:
Рубрика:
76 Глава 4. Теория автоматов
бы два слова, которые конгруэнтны и, значит, неразличимы относи-
тельно L. Следовательно, rk L ≤ m.
Теперь пусть rk L = n. Моноид минимального автомата состоит
из некоторых преобразований n-элементного множества состояний.
Всего таких преобразований n
n
. Отсюда и из теоремы 1 и следует
верхняя граница для мощности синтаксического моноида. ¤
Синтаксический моноид языка можно задать с помощью графа.
Впрочем, технически удобнее описывать изоморфный ему граф мо-
ноида автомата.
Предположим, что минимальный автомат, распознающий язык L,
построен. Рассмотрим орграф, вершины которого — различные авто-
матные операторы δ(p), причём из вершины δ(p) в вершину δ(px)
ведёт дуга с меткой x. Тогда путь с началом δ(e) в этом графе, по-
меченный словом p, ведёт в вершину δ(p). Так мы получаем удобный
способ находить δ(p) для любого слова p, прослеживая путь в гра-
фе моноида, отвечающий этому слову. Для наглядного представле-
ния оператора упорядочим состояния автомата: s
1
, . . . , s
n
. Тогда опе-
ратор δ(p) полностью определяется списком s
1
δ(p), . . . , s
n
δ(p). Этот
список и будем использовать в качестве обозначения оператора δ(p).
Рекомендуем читателю убедиться в том, что на рис. 7 изображён
граф моноида автомата из примера 1 §2 (квадратные скобки в обо-
значениях состояний опущены).
Рис. 7
Описанный способ представления синтаксического моноида удо-
бен, если язык конечно распознаваем. Но и в противном случае
устройство синтаксического моноида может быть прозрачным, как
в следующей задаче.
76 Глава 4. Теория автоматов
бы два слова, которые конгруэнтны и, значит, неразличимы относи-
тельно L. Следовательно, rk L ≤ m.
Теперь пусть rk L = n. Моноид минимального автомата состоит
из некоторых преобразований n-элементного множества состояний.
Всего таких преобразований nn . Отсюда и из теоремы 1 и следует
верхняя граница для мощности синтаксического моноида. ¤
Синтаксический моноид языка можно задать с помощью графа.
Впрочем, технически удобнее описывать изоморфный ему граф мо-
ноида автомата.
Предположим, что минимальный автомат, распознающий язык L,
построен. Рассмотрим орграф, вершины которого — различные авто-
матные операторы δ(p), причём из вершины δ(p) в вершину δ(px)
ведёт дуга с меткой x. Тогда путь с началом δ(e) в этом графе, по-
меченный словом p, ведёт в вершину δ(p). Так мы получаем удобный
способ находить δ(p) для любого слова p, прослеживая путь в гра-
фе моноида, отвечающий этому слову. Для наглядного представле-
ния оператора упорядочим состояния автомата: s1 , . . . , sn . Тогда опе-
ратор δ(p) полностью определяется списком s1 δ(p), . . . , sn δ(p). Этот
список и будем использовать в качестве обозначения оператора δ(p).
Рекомендуем читателю убедиться в том, что на рис. 7 изображён
граф моноида автомата из примера 1 §2 (квадратные скобки в обо-
значениях состояний опущены).
Рис. 7
Описанный способ представления синтаксического моноида удо-
бен, если язык конечно распознаваем. Но и в противном случае
устройство синтаксического моноида может быть прозрачным, как
в следующей задаче.
