Разичимость слов и сверхслов

Условимся о следующих обозначениях: множество всех отображений внутреннего алфавита Q в себя обозначим через Q. Далее, состояние, в которое входное слово a переводит состояние q, будем записывать в виде произведения q a. Рассмотрим, например, конечный автомат, задаваемый Таблицей 4:

1 2 3 4

----------------------

a 2 3 4 1

b 2 1 3 4

c 2 2 3 4

на рис. 13 изображена соответствующая диаграмма.

Рис. 13.

Каждому входному слову a естественным образом соответствует некоторый элемент из Q, а именно то самое отображение Q в Q, которое задаёт произведение q a при фиксированном a и при q, пробегающим Q.

В частности, строка матрицы переходов, соответствующая некоторой входной букве x. задаёт отображение, индуцируемое однобуквенным словом x = x. Так, например, из таблицы 4 видно, что a и b индуцируют одно-однозначные отображения множества {1, 2, 3, 4} на себя (a — циклическую перестановку, b — транспозицию пары (1, 2)); при отображении же, индуцируемым буквой c, происходит склеивание пары (1, 2), т.е. оба эти состояния отображаются в одно то тоже состояние.

Пусть слова x, y индуцируют одно и то же отображение. Тогда мы будем говорить, что они неразличимы (данным автоматом M), и обозначим это так: x » y (M). Там, где это не вызывает недоразумений, M будем опускать.

Ясно, что » является отношением эквивалентности, следовательно, оно разбивает множество всех входных, включая пустое, слов в алфавите X (т.е. всеобщий язык X* ^) на классы эквивалентности (так называемые классы неразличимости).

Ранг этого разбиения в случае, когда M является конечным автоматом с n состояниями, конечен.

Действительно, поскольку число всевозможных отображений множества Q из n элементов в себя равно n ⁿ, то имеется лишь конечное число (не более n ⁿ) классов неразличимости.

В случае бесконечного автомата число классов неразличимости может оказаться как конечным, так и бесконечным.

Если a — какое-нибудь входное сверхслово, то сохраним обозначение q a для того макросостояния, в которое a переводит состояние q.

Каждое входное сверхслово индуцирует некоторое отображение множества состояний Q во множество всех макросостояний. Если два сверхслова x и y индуцируют одно и то же отображение, мы будем говорить, что они неразличимы, и означим это (как и в случае обычных слов) через x » y (M).

Ясно, что » является отношением эквивалентности; если M — конечный автомат с k состояниями, то число классов эквивалентности (так называемых классов неразличимых сверхслов) не больше чем (2 ^k -1) ^k.

Рассмотрим, например, конечный автомат с диаграммой, изображённой на рис. 14.

Рис.14.

Существует два класса неразличимых слов, а именно: 1) язык A ₁ из слов с нечётным числом единиц и 2) язык A ₂ с чётным числом единиц. Соответствующие отображения Q в Q:

1 2

1 2

и

1 2

2 1

Существуют три класса неразличимых сверхслов, а именно: сверхъязык B _¥ из сверхслов с бесчисленным множеством единиц, сверхъязык B ₁ из сверхъслов с конечным и притом нечётным числом единиц, сверхъязык B ₂ из сверхъслов с конечным и чётным числом единиц.

Для

a Î B _¥ 1 a = 2 a = {1, 2}

a Î B ₁ 1 a = 2; 2 a = 1,

a Î B ₂ 1 a = 1; 2 a = 2.

Из определений непосредственно вытекает, что w (M, q ₀, Q ¢) (W (M, q ₀,C)) является, вообще говоря, объединением некоторого множества неразличимых в M слов (сверхъслов).

Отметим связь между понятиями неразличимости слов (относительно автомата M) и взаимозамещаемости.

Пусть слова p, r неразличимы автоматом M; тогда они взаимозамещаемы относительно любого из классов неразличимости. Иначе говоря, если K — произвольный класс неразличимоти, то для всех x, y

xpy Î K

тогда и только тогда, когда

xry Î K,

т.е. слова xpy и xry индуцируют одно и то же отображение Q в Q. Поэтому p, r взаимозамещаемы относительно любого из языков, представимых при той или иной настройке автомата W.

Верно и обратное утверждение: пусть p и r взаимозамещаемы относительно любого из языков, представимых в M; тогда они неразличимы автоматом M.

В самом деле, пусть q p = q ¢, т.е. p Î w (M, q, q ¢); тогда по условию и r Î w (M, q, q ¢), т.е. q r = q ¢.

Итак, неразличимость двух слов относительно какого-нибудь автомата M есть не что иное, как их взимозамещаемость относительно любого из языков, представимых (при подходящей настройке) в автомате M.

[1] Предположим обратное. Пусть p »_л r (B), но ô p ô ¹ô r ô. Без потери общности мы можем полагать, что ô p ô> ô r ô(иначе, мы просто поменяем местами p и r). Тогда для некоторого слова x ₀ и некоторых натуральных k ₀ и l ₀выполняются соотношения:

ô p ô + ô x ₀ ô = k ₀²; (1)

ô r ô + ô x ₀ ô = l ₀ ²; (2)

k ₀> l ₀. (3)

Вычтем (2) из (1):

ô p ô-ô r ô = k ₀² - l ₀ ². (4)

Для данных слов p и r разность ô p ô-ô r ô является постоянной целочисленной величиной, которую обозначим через a. Тогда (4) перепишется в виде:

a = (k ₀ + l ₀)(k ₀ - l ₀ ). (5)

При этом заведомо k ₀ - l ₀ ³ 1, и, следовательно,

k ₀ + l ₀ £ a. (6)

С другой стороны, по определению p »_л r (B) и нашему предположению ô p ô>ô r ô, для любого натурального k > k ₀ найдутся слово x и натуральное число l такие, что для них будет выполнены условия (1) - (6) с заменой: x ₀ на x; k ₀ на k; l ₀ на l. Но тогда неравенство

k + l £ a (6)*

должно выполняться для сколь угодно больших k, что невозможно, ибо a — константа. Противоречие. Доказательство завершено.