Основные понятия теории автоматов. Подавтоматы автоматов. Связные и сильно связные автоматы

4 Глава 1. Основные понятия теории автоматов. §1.1 Основные определения. Примеры. Начнем изложение материала с определения автомата. Определение 1.1 Конечным автоматом назовем упорядоченный набор (X, S, Y, h, f ), где X, S, Y — конечные непустые множества, называемые соответственно входным алфавитом, алфавитом состояний и выходным алфавитом, h — отображение из множества S × X в множество S, называемое функцией переходов, а f — отображение из множества S × X в множество Y , называемое функцией выходов. Как правило, автомат будем обозначать буквой A, добавляя, если необходимо, различные индексы. Содержательная модель автомата имеет вид: xt - вход - yt st корпус выход Она состоит из входа, корпуса и выхода. В начальный момент времени t = 1 корпус модели автомата находится в состоянии s1 ∈ S. На вход автомата поступает символ x1 ∈ X. Автомат вырабатывает выходной символ y1 = f (s1 , x1 ) и переходит в следующее состояние s2 = h(s1 , x1 ). В каждый момент времени t = 2, 3, . . . на вход автомата подается входной сигнал xt ∈ X. Пусть st ∈ S состояние, в котором находится автомат в этот момент времени t. Тогда с выхода модели снимается сигнал yt = f (st , xt ) и вырабатывается следующее состояние корпуса модели st+1 = h(st , xt ). Итак, если на вход автомата поступает последовательность x̄ = x1 x2 . . . xl , то автомат вырабатывает выходную последовательность ȳ = y1 y2 . . . yl и проходит последовательность состояний s1 s2 . . . sl+1 . Таким образом, действие функций переходов и выходов автомата можно распространить на любую последовательность x̄ входных символов. В дальнейшем будем использовать следующие обозначения: h∗ (s1 , x̄) = s1 s2 . . . sl+1 , h(s1 , x̄) = sl+1 , f ∗ (s1 , x̄) = As (x̄) = y1 y2 . . . yl , ∗ f (s1 , x̄) = yl . (1.1) l ∪∞ l=1 X — ∗ ∗ Если X = X ∪ X ∪ . . . = множество всех слов в алфавите X, то определены ∗ ∗ отображения h : S × X → S , f : S × X ∗ → Y ∗ . Состояние s1 называется начальным состоянием, а состояние sl+1 конечным при подаче на состояние s1 входной последовательности x̄. 2 Определение 1.2 Для каждого s ∈ S отображение As : X ∗ → Y ∗ , определенное равенством (1.1), называется автоматным отображением автомата A. Ясно, что As (X l ) ⊂ Y l , для всех l ∈ N, то есть автоматное отображение сохраняет длины слов. Приведем теперь примеры автоматов и укажем их некоторые виды. Пусть задан произвольный автомат A = (X, S, Y, h, f ). Определение 1.3 Если функции h(s, x) и f (s, x) автомата A не зависят от входной переменной x, то есть для всех состояний s ∈ S выполнены равенства h(s, x) = h(s, x′ ), f (s, x) = f (s, x′ ) при любых входных символах x, x′ ∈ X, то автомат A называется автономным. 5 Как правило считают, что входной алфавит автономного автомата состоит из одного символа, а функции переходов и выходов отображают элементы множества S соответственно в множества S и Y (зависят только от переменной s). Автономный автомат A будем обозначать A = (S, Y, h, f ). Определение 1.4 Если функция выходов автомата не зависит от входной переменной, то автомат называется автоматом Мура, а если функция переходов не зависит от входной переменной, то автомат называется внутренне автономным. Из приведенных определений следует, что внутренне автономный автомат Мура — это автономный автомат. Определение 1.5 Если функции h(s, x) и f (s, x) автомата A не зависят от переменной s, то есть для всех входных символов x ∈ X выполнены равенства h(s, x) = h(s′ , x), f (s, x) = f (s′ , x) при любых состояниях s, s′ ∈ S, то автомат A называется автоматом без памяти. Как правило, считают, что в автомате без памяти множество состояний является одноэлементным. Такой автомат будем обозначать A = (X, Y, f ). Автомат без памяти можно рассматривать как отображение f : X → Y . Определение 1.6 Если функция выходов f (s, x) автомата A не зависит от переменных s и x, то есть для всех входных символов x, x′ ∈ X и для всех состояний s, s′ ∈ S выполняется равенство f (s, x) = f (s′ , x′ ), то автомат A называется автоматом без выходов. В этом случае считают, что выходной алфавит автомата A состоит из одного символа. Автомат без выходов обозначают A = (X, S, h). Пусть φ : X1 × X2 × · · · × Xn → Y —произвольное отображение, i ∈ {1, 2, . . . , n}. Определение 1.7 Частичной функцией по i-ой переменной отображения φ, соответствующей x̄ = x1 . . . xi−1 xi+1 . . . xn ∈ X1 × · · · × Xi−1 × Xi+1 × · · · × Xn называется отображение φx̄ : Xi → Y , осуществляемое по правилу φx̄ (xi ) = φ(x1 , . . . , xi−1 , xi , xi+1 , . . . , xn ), xi ∈ Xi . Определение 1.8 Говорят, что отображение φ инъективно (сюръективно, биективно) по i-ой переменной, если для всех x̄ ∈ X1 × · · · × Xi−1 × Xi+1 × · · · × Xn отображение φx̄ инъективно (сюръективно, биективно). Читателю предлагается самостоятельно доказать следующий факт. Утверждение 1.9 Булева функция φ(x1 , . . . , xn ) биективна по i-ой переменной тогда и только тогда, когда φ линейна по i-ой переменной, то есть она представима в виде φ(x1 , . . . , xn ) = xi ⊕ φ′ (x1 , . . . , xi−1 , xi+1 , . . . , xn ), где φ′ — некоторая булева функция от n − 1 переменных. Определение 1.10 Пусть A = (X, S, Y, h, f ). Для каждого x ∈ X отображение hx : S → S называется частичной функцией переходов автомата A. Определение 1.11 Автомат A называется регулярным, если каждая его частичная функция переходов является подстановкой на множестве S. 6 Пусть l ∈ N, x̄ = x1 x2 . . . xl ∈ X l . Введем обозначение hx̄ = hx1 hx2 · · · hxl . Определение 1.12 Полугруппу G(A), порожденную множеством преобразований {hx : x ∈ X}, называют полугруппой автомата A. Таким образом G(A) = {hx̄ : x̄ ∈ X ∗ }. Если автомат A регулярен, то G(A) является группой. Приведем теперь некоторые примеры автоматов. 1. Задержка на один такт. Это автомат A = (X, X, X, h, f ), у которого функции переходов и выходов задаются равенствами h(s, x) = x, f (s, x) = s для всех s ∈ S, x ∈ X. Нетрудно проверить, что при любом начальном состоянии s1 и входной последовательности x̄ = x1 x2 . . . xl для этого автомата выполняются равенства h∗ (s1 , x̄) = s1 x1 x2 . . . xl , f ∗ (s1 , x̄) = s1 x1 x2 . . . xl−1 . Другими словами, выходной символ в момент времени t равен входному символу xt−1 в предыдущий момент времени t − 1 для всех t ≥ 2. Задержка на один такт является автоматом Мура. В случае, когда X = {0, 1}, задержку на один такт будем называть двоичной. Ее изображают, как правило, следующим образом: - △- 2. Автомат Кэли. Пусть (G, ∗) — произвольная полугруппа. Автоматом Кэли полугруппы G называется автомат A = (G, G, G, h, f ) у которого h(s, x) = s ∗ x, f (s, x) = s для всех s, x ∈ G. 3. Триггер. Это автомат A = ({0, 1, λ}, {0, 1}, {0, 1, }, h, f ) у которого h(s, λ) = s, h(s, i) = i, f (s, λ) = f (s, i) = s для всех s, i ∈ {0, 1}. 4. Автономный линейный регистр сдвига. Пусть n — натуральное число, (Z, +, ·) — произвольное кольцо, a1 , a2 , . . ., an — элементы этого кольца. Автономным линейным регистром сдвига длины n называется автономный автомат (Z n , Z, h, f ), у которого для любого состояния (z1 , z2 , . . . , zn ) ∈ Z n функции переходов и выходов определяются равенствами h((z1 , z2 , . . . , zn )) = (z2 , z3 , . . . , zn , a1 z1 + a2 z2 + . . . + an zn ), f ((z1 , z2 , . . . , zn )) = z1 . Всюду в дальнейшем, автономный линейный регистр сдвига будем обозначать R(a1 , a2 , . . . , an ). Схематично его можно изобразить следующим образом: +i- +i6 6 an · 1 an 2  6 6 z1 z2 · · · · · - +i 6 n an 6 zn  5. Регистр сдвига. Регистр сдвига является более общей конструкцией по сравнению с автономным линейным регистром сдвига. Регистром сдвига длины n называют автомат R(ψ, φ) = (X, Z n , X, h, f ), где ψ : Z n × X → Y , φ : Z n × X → Z, а функции h и f определены равенствами h((z1 , z2 , . . . , zn ), x) = (z2 , z3 , . . . , zn , φ(z1 , z2 , . . . , zn , x)), 7 f ((z1 , z2 , . . . , zn ), x) = ψ(z1 , z2 , . . . , zn , x), для всех состояний (z1 , z2 , . . . , zn ) ∈ Z n и для всех x ∈ X. Отображение φ называют функцией обратной связи регистра R(ψ, φ). Регистр сдвига схематично изображают в следующем виде:  - z1 · · ψ  φ ·  zn -  6  x Если у регистра сдвига X = Z = Y = {0, 1}, то регистр сдвига называется двоичным. Пусть регистр сдвига R(ψ, φ) имеет алфавиты X = Z = Y , где (Z, +, ·) — кольцо, а отображения ψ и φ задаются равенствами φ(z1 , z2 , . . . , zn , x) = a1 z1 + a2 z2 + . . . + an zn , ψ(z1 , z2 , . . . , zn , x) = z1 , для всех z1 , z2 , . . ., zn , x ∈ Z и фиксированных элементов a1 , a2 , . . ., an из кольца Z. Такой регистр сдвига можно рассматривать как автономный автомат, и в этом случае он будет являться автономным линейным регистром сдвига. 6. Линейный автомат. Пусть Z — кольцо, A, B, C, D — матрицы над кольцом Z, имеющие размеры n×n, m× n, n×r, m×r соответственно. Линейным автоматом называется автомат (Z m , Z n , Z r , h, f ), у которого функции переходов и выходов задаются следующими равенствами: h(⃗s, ⃗x) = ⃗sA + ⃗xB, f (⃗s, ⃗x) = ⃗sC + ⃗xD, для всех векторов-строк ⃗s ∈ Z n , ⃗x ∈ Z m . Такой автомат будем обозначать L(A, B, C, D). У внутренне автономного линейного автомата считают, что матрица B равна нулевой матрице Om×n размеров m × n, у линейного автомата без выходов C = On×r и D = Om×r , а у автономного линейного автомата B = Om×n и D = Om×r . Заметим, что автономный линейный регистр сдвига является автономным линейным автоматом. Читателю предлагается самостоятельно выписать матрицы A и C, соответствующие автономному линейному регистру сдвига. Получим критерий регулярности регистра сдвига. Теорема 1.13 Автомат R(ψ, φ) регулярен тогда и только тогда, когда функция φ биективна по первой переменной. Доказательство. Пусть регистр сдвига R(ψ, φ) регулярен. Рассмотрим произвольные состояния (z1 , z2 , . . . , zn ), (z1′ , z2 , . . . , zn ) ∈ Z n , где z1 ̸= z1′ . Для каждого x ∈ X в силу инъективности hx hx (z1 , . . . , zn ) = (z2 , . . . , zn , φ(z1 , . . . , zn , x)) ̸= hx (z1′ , . . . , zn ) = (z2 , . . . , zn , φ(z1′ , . . . , zn , x)). Значит φ(z1 , . . . , zn , x) ̸= φ(z1′ , . . . , zn , x) для всех z1 , z1′ , z2 , . . ., zn ∈ Z, x ∈ X таких, что z1 ̸= z1′ . Таким образом φ биективна по первой переменной. Пусть теперь φ биективна по первой переменной. Рассмотрим произвольные состояния (z1 , z2 , . . . , zn ), (z1′ , z2′ , . . . , zn′ ) ∈ Z n . 8 Покажем, что для всех x ∈ X выполнено неравенство hx (z1 , z2 , . . . , zn ) ̸= hx (z1′ , z2′ , . . . , zn′ ). Если найдется i ∈ {2, 3, . . . , n} такое, что zi ̸= zi′ , то hx (z1 , . . . , zn ) = (z2 , . . . , zn , φ(z1 , . . . , zn , x)) ̸= (z2′ , . . . , zn′ , φ(z1′ , . . . , zn′ , x)) = hx (z1′ , . . . , zn′ ). Пусть теперь z2 = z2′ , . . ., zn = zn′ , тогда в силу биективности φ по первой переменной hx (z1 , . . . , zn ) = (z2 , . . . , zn , φ(z1 , . . . , zn , x)) = (z2 , . . . , zn , φz2 ,...,zn ,x (z1 )) ̸= ̸= (z2 , . . . , zn , φz2 ,...,zn ,x (z1′ )) = (z2′ , . . . , zn′ , φ(z1′ , . . . , zn′ , x)) = hx (z1′ , . . . , zn′ ). Таким образом для всех x ∈ X частичная функция hx инъективна, а так как hx — преобразование конечного множества S, то hx является подстановкой.  Непосредственно из теоремы 1.13 и утверждения 1.9 получим важный факт. Следствие 1.14 Двоичный регистр сдвига R(ψ, φ) регулярен тогда и только тогда, когда φ линейна по первой переменной. Рассмотрим способы задания автоматов. Для того, чтобы задать автомат необходимо задать алфавиты автомата, а также функции переходов и выходов. Существует два основных способа задания конечных автоматов. 1. Табличный способ задания. В этом случае, функции переходов и выходов задаются в виде таблиц. В этих таблицах строки занумерованы состояниями автомата, а столбцы входными символами автомата. Функция переходов h автомата задается так называемой таблицей переходов, в которой на пересечении строки, занумерованной состоянием s и столбца, занумерованного входным символом x, стоит состояние h(s, x). Изображают таблицу переходов следующим образом: X ··· x ··· S · · · · · · s · · · h(s, x) · · · · · · · · · Функция выходов f автомата задается аналогичной таблицей, которая называется таблицей выходов. В ней на пересечении строки, занумерованной состоянием s и столбца, занумерованного входным символом x, стоит выходной символ f (s, x). Как правило, таблицы переходов и выходов совмещают в одну таблицу, которая носит название переходно-выходная таблица автомата. В ней на пересечении строки, занумерованной состоянием s и столбца, занумерованного входным символом x, стоит пара (h(s, x), f (s, x)). Такую таблицу изображают в следующем виде: 9 X S · · · s · · · ··· ··· x · · · · · · h(s, x), f (s, x) · · · · · · Ясно, что переходно-выходная таблица однозначно задает автомат. 2. Графический способ задания автомата. В этом случае, автомату A = (X, S, Y, h, f ) сопоставляется помеченный ориентированный граф, в котором вершины занумерованы состояниями автомата. При этом, две вершины s1 , s2 ∈ S соединяются ребром с меткой (x, y) тогда и только тогда, когда h(s1 , x) = s2 , а f (s1 , x) = y. Схематично будем изображать эту зависимость следующим образом: (x, y) sn sn 1 2 Таким образом, будет построен граф, который однозначно задает автомат A. Этот граф будем называть графом автомата A и обозначать ΓA . Очевидно, что в этом графе из каждой вершины будет исходить ровно |X| ребер. В дальнейшем для удобства ребра вида sn 1 (x1 , y1 ) sn 2 - (x2 , y2 ) будем заменять на одно ребро с двумя метками: (x1 , y1 ),-(x2 , y2 ) n sn s2 1 Приведем теперь примеры задания автоматов. Пример 1.15 Двоичная задержка на один такт имеет алфавиты X = S = Y = {0, 1} и функции переходов и выходов, задаваемые равенствами h(s, x) = x, f (s, x) = s для всех s, x ∈ {0, 1}. Переходно-выходная таблица двоичной задержки на один такт имеет вид X S 1 1 0, 0 1, 0 0, 1 1, 1 а граф будет следующего вида:  ? 0n  (0, 0) (1, -0)  (0, 1)  n ? 1  (1, 1) Пример 1.16 Рассмотрим двоичный регистр сдвига длины 2, у которого отображения φ и ψ определены равенствами φ(z1 , z2 , x) = z1 ⊕ x, ψ(z1 , z2 , x) = z2 ⊕ x, 10 для всех z1 , z2 , x ∈ {0, 1}. Функции переходов и выходов этого регистра задаются равенствами h((z1 , z2 ), x) = (z2 , φ(z1 , z2 , x)) = (z2 , z1 ⊕ x), f ((z1 , z2 ), x) = ψ(z1 , z2 , x) = z2 ⊕ x. Изобразим схематично регистр сдвига R(ψ, φ) z1 z2  +? i 6 ? +i x Переходно-выходная таблица этого автомата имеет вид X S (00) (01) (10) (11) 1 (00), 0 (10), 1 (01), 0 (11), 1 (01), 1 (11), 0 (00), 1 (10), 0 а граф следующий вид: 01n @ R @ (1, 0)  @  @  (0, 0) n ? ? 00 11n 6 ?   (0, 1) (0, 0) @@ (0, 1) (1, 1) @ (1, 0) I @ 10n (1, 1) Пример 1.17 Построим автоматную модель программы, у которой входными данными служат английские тексты, в которых все слова разделены пробелами. При этом, программа выдает "1 если обрабатываемое слово начинается с "un"и заканчивается "d и выдает "0"во всех остальных случаях. Алфавит X будет состоять из символов u, n, d, λ (соответствует пробелу) и δ (соответствует буквам, отличным от u, n и d). Алфавит S будет содержать состояния s1 (соответствует новому слову), s2 (соответствует ожиданию нового слова), s3 (соответствует появлению u), s4 (соответствует появлению un), s5 (соответствует появлению un . . . d). Выходной алфавит будет совпадать с множеством {0, 1}. Переходновыходная таблица этого автомата имеет следующий вид: X S s1 s2 s3 s4 s5 u n d λ δ s3 , 0 s2 , 0 s2 , 0 s4 , 0 s4 , 0 s2 , 0 s2 , 0 s4 , 0 s4 , 0 s4 , 0 s2 , 0 s2 , 0 s2 , 0 s5 , 0 s5 , 0 s1 , 0 s1 , 0 s1 , 0 s1 , 0 s1 , 1 s2 , 0 s2 , 0 s2 , 0 s4 , 0 s4 , 0 В качестве начального состояния этого автомата выбирается состояние s1 . Читателю предлагается самостоятельно, в качестве упражнения, построить граф автомата из примера 1.17. 11 §1.2 Подавтоматы автоматов. Связные и сильно связные автоматы. Пусть A = (X, S, Y, h, f ) — произвольный автомат. Определение 1.18 Подавтоматом автомата A называется автомат A′ = (X ′ , S ′ , Y ′ , h′ , f ′ ), у которого X ′ ⊂ X, S ′ ⊂ S, Y ′ ⊂ Y а отображения h′ и f ′ являются соответственно ограничениями отображений h и f на множество S ′ × X ′ , то есть h′ (s′ , x′ ) = h(s′ , x′ ) ∈ S ′ , f ′ (s′ , x′ ) = f (s′ , x′ ) ∈ Y ′ для всех s′ ∈ S ′ , x′ ∈ X ′ . В дальнейшем для подавтоматов будем использовать обозначение A′ ⊂ A. Если X ′ = X и Y ′ = Y , то подавтомат A′ ⊂ A называется внутренним. Из определения следует, что сам автомат A является подавтоматом автомата A. Этот подавтомат называется несобственным подавтоматом, а все остальные подавтоматы автомата A называются собственными. Заметим, что не любое непустое подмножество множества состояний S автомата A является множеством состояний некоторого подавтомата автомата A. Рассмотрим следующий пример. Пример 1.19 Укажем все собственные внутренние подавтоматы Ai автомата A, заданного следующим графом: (0, 0) (0, 1), (1, 1)  ? ?   - sn  sn 1 2 (1, 1) (0, 1), (1, 0) (0, 0) (0, 1), (1, 1)  sn 4   ?  sn 5 (0, 1) (1, 0) (0, 0) (0, 1), (1, 1) (0, 1), (1, 1)    ? ?   A1 sn - sn  1 2 (1, 1) sn 3 (0, 1), - (1, 1) (0, 1), (1, 0) ? ? ?    A2 sn - sn A3 sn  sn 1 2 2 3 (1, 1) (0, 1), (1, 0) (0, 1), (1, 1) ?  A4 sn sn 2 3 (0, 0) (0, 1), (1, 1)  A5 sn 4 (0, 1), - (1, 1)  (0, 1) ? ? (0, 1),   - (1, 1)   A n n n n n 6 s1 ? ? s2 s5 s4 s5  (1, 1)   (1, 0) (0, 1), (1, 1) (0, 1) (1, 0) (0, 1), (1, 1) ? ? (0, 1),  - (1, 1)  A7 sn  ?A8 sn sn sn sn 2 4 5 2 3  (0, 1), (1, 0)  (0, 1) (1, 0) sn 4 (0, 1), - (1, 1)  (0, 1)  n ? s5  (1, 0) В этом примере автоматы A2 , A3 , A4 являются собственными подавтоматами автомата A1 , а автомат A5 вообще не имеет собственных внутренних подавтоматов. Определение 1.20 Состояния s и s′ автомата A называются соседними, если существует входной символ x ∈ X такой, что h(s, x) = s′ либо h(s′ , x) = s. По определению считают, что любое состояние является соседним с самим собой. 12 Определение 1.21 Состояния s и s′ автомата A называются связными, если существует последовательность состояний s = s1 , s2 , s3 , . . ., sl = s′ автомата A, в которой состояния si и si+1 являются соседними при всех i ∈ 1, l − 1. Нетрудно проверить, что бинарное отношение связности состояний автомата A является отношением эквивалентности на множестве S состояний автомата A. Поэтому множество состояний автомата A разбивается на непересекающиеся классы S1 , S2 , . . ., Sr связных состояний. Определение 1.22 Автомат A называется связным, если любые состояния s и s′ автомата A являются связными. Другими словами, автомат A является связным, тогда и только тогда, когда число r классов связных состояний равно 1. Автомат A и его подавтоматы A6 , A7 , A8 из примера 1.19 содержат два класса связных состояний и поэтому не являются связными, а автоматы A1 , A2 , A3 , A4 , A5 являются связными. Несложно проверить, что для каждого класса Si связных состояний автомата A и для всех входных символов x ∈ X справедливо соотношение h(Si , x) ⊂ Si , где i ∈ 1, r. Поэтому корректно следующее определение: Определение 1.23 Пусть Si — класс связных состояний автомата A, тогда автомат Ai = (X, Si , Y, hi , fi ), где hi и fi — ограничения отображений h и f на множество Si × X соответственно, является подавтоматом автомата A, который называется компонентой связности автомата A для всех i ∈ 1, r. Заметим, что каждая компонента связности автомата является связным автоматом. В примере 1.19 компонентами связности автомата A являются автоматы A1 и A5 . Определение 1.24 Состояния s и s′ автомата A называются сильно связными, если s = s′ либо существуют две последовательности x̄ = x1 x2 . . . xk и x̄′ = x′1 x′2 . . . x′l входных символов автомата A такие, что h(s, x̄) = s′ и h(s′ , x̄′ ) = s, то есть из состояния s можно перейти в состояние s′ и наоборот. Определение 1.25 Автомат A называется сильно связным, если любые состояния s и s′ автомата A являются сильно связными. Очевидно, что сильно связный автомат является связным. Обратное утверждение, вообще говоря, не верно. В примере 1.19 связные автоматы A1 , A2 и A3 не являются сильно связными и только автоматы A4 и A5 являются сильно связными. Следующее утверждение показывает, что в регулярном автомате понятие связности и сильной связности совпадают. Утверждение 1.26 Любая компонента связности Ai , i = 1, . . . , d регулярного автомата A является сильно связной. Доказательство. Достаточно доказать, что для любых двух связных состояний s, s′ ∈ S следует, что s и s′ сильно связные. Так как состояния связны, то найдется цепочка s = s1 , s2 , s3 , . . ., sl = s′ из попарно соседних состояний. Утверждение будет доказано, если показать, что для всех i ∈ {1, . . . , l − 1} состояния si и si+1 сильно связны. Так как они соседние, то найдется x ∈ X такой, что h(si , x) = si+1 или h(si+1 , x) = si . Пусть без ограничения общности h(si , x) = si+1 . Тогда hx (si ) = si+1 и hx — подстановка на множестве 13 S. Найдется натуральное число k такое, что hkx = ε — тождественная подстановка на множестве S. Тогда hk−1 = h−1 x x и справедливы равенства −1 k−1 si = h−1 · · x}). x (hx (si )) = hx (si+1 ) = hx (si+1 ) = h(si+1 , x | ·{z k−1 Таким образом si и si+1 сильно связны.  В заключении этого параграфа отметим некоторое достаточное условие сильной связности регистра сдвига. Утверждение 1.27 Пусть функция φ(z1 , z2 , . . . , zn , x) сюръективна по последней переменной, тогда регистр сдвига R(ψ, φ) = (X, Z n , Y, h, f ) будет сильно связным автоматом. Доказательство. Пусть s̄1 = (z1 , z2 , . . . , zn ) и s̄2 = (z1′ , z2′ , . . . , zn′ ) — произвольные состояния регистра сдвига. Покажем, что в условиях утверждения существует входная последовательность x̄ = x1 x2 . . . xn такая, что h(s̄1 , x̄) = s̄2 . В силу произвольности состояний s̄1 и s̄2 , отсюда будет следовать сильная связность регистра сдвига. Входной символ x1 выберем таким образом, чтобы выполнялось равенство φz1 ,z2 ,...,zn (x1 ) = z1′ . Такой символ есть, так как отображение φz1 ,z2 ,...,zn сюръективно. Тогда, при подаче на вход регистра сдвига символа x1 , он перейдет в состояние h((z1 , z2 , . . . , zn ), x1 ) = (z2 , z3 , . . . , zn , z1′ ). Входной символ x2 выберем таким, чтобы выполнялось равенство φz2 ,z3 ,...,zn ,z1′ (x2 ) = z2′ . Такой символ есть, так как отображение φz2 ,z3 ,...,zn ,z1′ сюръективно. Тогда, при подаче на вход регистра сдвига последовательности x1 x2 , он перейдет в состояние h((z1 , z2 , . . . , zn ), x1 x2 ) = (z3 , z4 , . . . , zn , z1′ , z2′ ). Аналогично подберутся символы x3 , x4 , . . . , xn такие, что после подачи входной последовательности x̄ = x1 x2 . . . xn регистр сдвига перейдет в состояние s̄2 = (z1′ , z2′ , . . . , zn′ ).  Заметим, что в условиях утверждения 1.27 регистр сдвига R(ψ, φ) не просто сильно связен, но из каждого его состояния можно попасть в любое не более, чем за n шагов. Следствие 1.28 Пусть булева функция φ линейна по последней переменной, тогда двоичный регистр сдвига R(ψ, φ) будет сильно связным автоматом. Пример 1.16 служит иллюстрацией к следствию 1.28. Заметим, что условие теоремы 1.27 не является необходимым для сильной связности регистра сдвига (см. задачу 1.9). §1.3 Гомоморфизмы автоматов. Пусть A1 = (X1 , S1 , Y1 , h1 , f1 ) и A2 = (X2 , S2 , Y2 , h2 , f2 ) — произвольные автоматы. Определение 1.29 Гомоморфизмом автомата A1 в автомат A2 называется тройка отображений α : X1 → X2 , β : S1 → S2 , γ : Y1 → Y2 , удовлетворяющих условиям: β(h1 (s, x)) = h2 (β(s), α(x)), для всех x ∈ X1 и s ∈ S1 . γ(f1 (s, x)) = f2 (β(s), α(x)), 14 Гомоморфизм будем обозначать (α, β, γ) : A1 → A2 . Определение 1.30 Гомоморфизм (α, β, γ) автомата A1 в автомат A2 называется инъективным (сюръективным), если каждое из отображений α, β, γ инъективно (сюръективно). Если каждое из этих отображений биективно, то гомоморфизм (α, β, γ) называется изоморфизмом автомата A1 в автомат A2 . Определение 1.31 Гомоморфизм (α, β, γ) автомата A1 в автомат A2 , в котором отображения α и γ являются тождественными отображениями на множествах X1 = X2 и Y1 = Y2 соответственно, называется внутренним гомоморфизмом. Установим теперь связь функционирования автоматов при наличии гомоморфизма одного автомата в другой автомат. Утверждение 1.32 Пусть (α, β, γ) — гомоморфизм автомата A1 в автомат A2 , s1 — произвольное начальное состояние автомата A1 , n — произвольное натуральное число, а x1 , x2 , . . ., xn — любые символы из входного алфавита X1 автомата A1 . Тогда, если h∗1 (s1 , x1 x2 . . . xn ) = s1 s2 . . . sn+1 , f1∗ (s1 , x1 x2 . . . xn ) = y1 y2 . . . yn , то для автомата A2 справедливы равенства h∗2 (β(s1 ), α(x1 )α(x2 ) . . . α(xn )) = β(s1 )β(s2 ) . . . β(sn+1 ), f2∗ (β(s1 ), α(x1 )α(x2 ) . . . α(xn )) = γ(y1 )γ(y2 ) . . . γ(yn ). Доказательство. Докажем утверждение методом математической индукции по параметру n. При n = 1 утверждение выполнено согласно определению гомоморфизма. Допустим утверждение верно при любом начальном состоянии s1 автомата A1 и при любой входной последовательности автомата A1 , имеющей длину n = m, где m — некоторое натуральное число. Докажем утверждение при n = m + 1. Пусть h∗1 (s1 , x1 x2 . . . xm+1 ) = s1 s2 . . . sm+2 , f1∗ (s1 , x1 x2 . . . xm+1 ) = y1 y2 . . . ym+1 . Тогда, по предположению индукции, выполняются соотношения h∗2 (β(s1 ), α(x1 )α(x2 ) . . . α(xm )) = β(s1 )β(s2 ) . . . β(sm+1 ), f2∗ (β(s1 ), α(x1 )α(x2 ) . . . α(xm )) = γ(y1 )γ(y2 ) . . . γ(ym ). Так как h1 (sm+1 , xm+1 ) = sm+2 , а f1 (sm+1 , xm+1 ) = ym+1 , то по определению гомоморфизма автоматов получим, что справедливы следующие равенства: h2 (β(sm+1 ), α(xm+1 )) = β(sm+2 ), f2 (β(sm+1 ), α(xm+1 ) = γ(ym+1 ). Значит h∗2 (β(s1 ), α(x1 )α(x2 ) . . . α(xm+1 )) = β(s1 )β(s2 ) . . . β(sm+2 ), f2∗ (β(s1 ), α(x1 )α(x2 ) . . . α(xm+1 )) = γ(y1 )γ(y2 ) . . . γ(ym+1 ). 15 Из утверждения 1.32 следует, что при наличии гомоморфизма автомата A1 в автомат A2 эти автоматы, находясь в начальных состояниях s1 и β(s1 ) соответственно, функционируют одинаково с точностью до переобозначения входных символов, состояний и выходных символов с использованием соответственно отображений α, β и γ. Если при этом гомоморфизм (α, β, γ) является внутренним, то автоматы A1 и A2 , находясь в начальных состояниях s1 и β(s1 ) соответственно, вообще одинаково перерабатывают любые входные последовательности в выходные последовательности. В случае, когда существует изоморфизм автомата A1 в автомат A2 , их переходно-выходные таблицы и графы отличаются друг от друга переименованием входных символов, состояний и выходных символов с использованием соответствующих биективных отображений. Читателю предлагается самостоятельно доказать следующие свойства гомоморфизмов автоматов: Утверждение 1.33 Пусть (α1 , β1 , γ1 ) — гомоморфизм автомата A1 в автомат A2 , (α2 , β2 , γ2 ) — гомоморфизм автомата A2 в автомат A3 , тогда 1) (α1 · α2 , β1 · β2 , γ1 · γ2 ) — гомоморфизм автомата A1 в автомат A3 , 2) если (α1 , β1 , γ1 ) — изоморфизм автомата A1 в автомат A2 , то (α1−1 , β1−1 , γ1−1 ) является изоморфизмом автомата A2 в автомат A1 ; 3) если (α1 , β1 , γ1 ) и (α2 , β2 , γ2 ) — изоморфизмы, то (α1 · α2 , β1 · β2 , γ1 · γ2 ) — изоморфизм. Учитывая пункт 2 утверждения 1.33, при существовании изоморфизма автомата A1 в автомат A2 , автоматы A1 и A2 называют изоморфными. Пример 1.34 Пусть автоматы A1 и A2 заданы следующими переходно-выходными таблицами: X 1 2 S X a b s1 s4 , 0 s3 , 0 s2 , 1 S A1 A2 s2 s1 s3 , 0 s3 , 0 s1 , 2 s2 , c s1 , d s3 s2 s3 , 2 s4 , 1 s1 , 2 s2 , d s1 , d s4 s4 , 1 s4 , 1 s1 , 2 Рассмотрим тройку отображений (α, β, γ), которые задаются таблицами: ( ) ( ) ( ) 0 1 2 s1 s2 s3 s4 0 1 2 α= ,β = ,γ = . a a b s1 s1 s2 s2 c d d Покажем, что она задает сюръективный гомоморфизм автомата A1 в автомат A2 . Для обоснования этого переобозначим входные символы, состояния и выходные символы в переходно-выходной таблице автомата A1 при действии соответственно отображений α, β и γ. Получим таблицу X a a b S s1 s2 , c s2 , c s1 , d s1 s2 , c s2 , c s1 , d s2 s2 , d s2 , d s1 , d s2 s2 , d s2 , d s1 , d которая соответствует автомату A2 . 16 Покажем, что в примере 1.34 не существует сюръективного гомоморфизма (α, β, γ) автомата A1 в автомат A2 c условием β(s1 ) = s2 . Допустим противное, такой гомоморфизм существует. Тогда, согласно определению гомоморфизма, получим γ(f1 (s1 , 0)) = γ(0) = f2 (β(s1 ), α(0)) = d, γ(f1 (s1 , 2)) = γ(1) = f2 (β(s1 ), α(2)) = d. Так как отображение γ сюръективно, то γ(2) = c. Выходной символ c в автомате A2 можно получить только в состоянии s1 , кроме того для всех i ∈ {2, 3, 4} справедливы равенства γ(f1 (si , 2)) = γ(2) = c = f2 (β(si ), α(2)), значит β(s2 ) = β(s3 ) = β(s4 ) = s1 . Из равенств γ(f1 (s3 , 0)) = γ(2) = c = f2 (β(s3 ), α(0)) = f2 (s1 , α(0)), получим, что α(0) = a. Тогда, по теореме 1.32, фрагмент графа автомата A1  (0, 0) - n n ? s2 s3  (0, 2) при действии отображений α, β и γ перейдет в следующий фрагмент графа автомата A2 :  (a, d) - n ? s1  (a, c) который не может соответствовать никакому автомату. Таким образом, сюръективного гомоморфизма с выбранным требованием не существует. sn 1 §1.4 Конгруэнции автоматов. Пусть A = (X, S, Y, h, f ) — произвольный автомат. Определение 1.35 Конгруэнцией автомата A называют тройку κ = (ε1 , ε2 , ε3 ) отношений эквивалентности ε1 , ε2 , ε3 , заданных на множествах X, S, Y соответственно, которая удовлетворяет для всех x, x′ ∈ X, s, s′ ∈ S следующим условиям: если xε1 x′ и sε2 s′ , то h(s, x)ε2 h(s′ , x′ ) и f (s, x)ε3 f (s′ , x′ ). Определение 1.36 Конгруэнция κ = (ε1 , ε2 , ε3 ) в которой отношения ε1 и ε3 являются отношениями равенства на множествах X и Y соответственно, называется внутренней. Рассмотрим новые множества X̃, S̃, Ỹ , состоящие из классов эквивалентности по отношениям эквивалентности ε1 , ε2 , ε3 соответственно. Зададим отображения h̃ : S̃ × X̃ → S̃, f˜ : S̃ × X̃ → Ỹ по правилу h̃([s]ε2 , [x]ε1 ) = [h(s, x)]ε2 , f˜([s]ε2 , [x]ε1 ) = [f (s, x)]ε3 для всех x ∈ X, s ∈ S. Читателю предлагается самостоятельно проверить корректность задания функций h̃ и f˜. Определение 1.37 Автомат à = A/κ = (X̃, S̃, Ỹ , h̃, f˜) называется факторавтоматом автомата A по конгруэнции κ = (ε1 , ε2 , ε3 ). 17 Построим отображения ακ : X → X̃, βκ : S → S̃, γκ : Y → Ỹ по правилу ακ (x) = [x]ε1 , βκ (s) = [s]ε2 , γκ (y) = [y]ε3 для всех x ∈ X, s ∈ S, y ∈ Y . Читателю предлагается самостоятельно проверить, что тройка φκ = (ακ , βκ , γκ ) является сюръективным гомоморфизмом автомата A в автомат Ã. Определение 1.38 Гомоморфизм φκ называется естественным гомоморфизмом автомата A в автомат Ã. Таким образом каждой конгруэнции автомата соответствует гомоморфизм автоматов. Пусть теперь ψ = (α, β, γ) — гомоморфизм автомата A в автомат A′ . Зададим бинарные отношения ε1 , ε2 , ε3 по правилу xε1 x′ тогда и только тогда, когда α(x) = α(x′ ); sε2 s′ тогда и только тогда, когда β(s) = β(s′ ); yε3 y ′ тогда и только тогда, когда γ(y) = γ(y ′ ) для всех x, x′ ∈ X, s, s′ ∈ S, y, y ′ ∈ Y . Несложно показать, что ε1 , ε2 , ε3 — отношения эквивалентности и (ε1 , ε2 , ε3 ) —конгруэнция автомата A. Таким образом каждому гомоморфизму автомата соответствует некоторая конгруэнция. Определение 1.39 Построенная конгруэнция называется ядром гоморфизма ψ и обозначается Kerψ = (ε1 , ε2 , ε3 ). Теорема 1.40 Пусть ψ : A → A′ — сюръективный гомоморфизм автоматов, φKerψ — естественный гомоморфизм A → A/Kerψ . Тогда найдется единственный изоморфизм ψ0 : A/Kerψ → A′ такой, что φKerψ · ψ0 = ψ, то есть коммутативна следующая диаграмма A @@ R - A′  A/Kerψ Доказательство. Пусть ψ = (α, β, γ), κ = Kerψ = (ε1 , ε2 , ε3 ). Зададим тройку отображений ψ0 = (α0 , β0 , γ0 ) по правилу α0 ([x]ε1 ) = α(x), β0 ([s]ε2 ) = β(s), γ0 ([y]ε3 ) = γ(y) для всех x ∈ X, s ∈ S, y ∈ Y . Проверим корректность задания отображения α0 . Допустим [x]ε1 = [x′ ]ε1 , тогда xε1 x′ , что по определению ядра гомоморфизма влечет α(x) = α(x′ ). Аналогично доказывается корректность задания отображений β0 и γ0 . В силу того, что гомоморфизм ψ сюръективный получим, что α0 , β0 и γ0 — сюръективные отображения. Покажем, что α0 —инъективное отображение. Действительно, если [x]ε1 ̸= [x′ ]ε1 , то x не находится в отношении ε1 с x′ , это влечет α(x) ̸= α(x′ ), а значит α0 ([x]ε1 ̸= α0 ([x′ ]ε1 . Аналогично доказывается инъективность отображений β0 и γ0 . Таким образом ψ0 — тройка биективных отображений. Покажем, что ψ0 гомоморфизм. Пусть A/Kerψ = (X̃, S̃, Ỹ , h̃, f˜), тогда по определению факторавтомата h̃([s]ε2 , [x]ε1 ) = [h(s, x)]ε2 , f˜([s]ε2 , [x]ε1 ) = [f (s, x)]ε3 для всех x ∈ X, s ∈ S. Подействуем на обе части первого равенства отображением β0 , а на обе части второго равенства отображением γ0 , тогда получим β0 (h̃([s]ε2 , [x]ε1 )) = β0 ([h(s, x)]ε2 ), γ0 (f˜([s]ε2 , [x]ε1 )) = γ0 ([f (s, x)]ε3 ). Преобразуем правые части полученных равенств учитывая, что ψ — гомоморфизм автоматов: β0 (h̃([s]ε2 , [x]ε1 )) = β(h(s, x)) = h′ (β(s), α(x)) = h′ (β0 ([s]ε2 ), α0 ([x]ε1 )); 18 γ0 (f˜([s]ε2 , [x]ε1 )) = γ0 ([f (s, x)]ε3 ) = γ(f (s, x)) = f ′ (β0 ([s]ε2 ), α0 ([x]ε1 )). Таким образом ψ0 — изоморфизм автоматов. Пусть теперь ψ0′ = (α0′ , β0′ , γ0′ ) удовлетворяет равенству φKerψ · ψ0′ = ψ, тогда рассматривая первые отображения из троек получим (ακ ·α0′ )(x) = α(x), следовательно α0′ ([x]ε1 ) = α0 ([x]ε1 ) и α0′ = α0 . Аналогично доказываются равенства β0′ = β0 , γ0′ = γ0 . Таким образом ψ0′ = ψ0 .  ЗАДАЧИ 1.1 Найти число всех автоматов с фиксированными алфавитами X, S, Y , где |X| = m, |S| = n, |Y | = k. Сколько из них автоматов Мура; автономных; регулярных автоматов? 1.2 Задайте переходно-выходной таблицей и графом следующие автоматы: (а) двоичную задержку на один такт в алфавите X = {a, b, c}; (б) автомат Кэли группы (GF (2), +); (в) триггер; (г) двоичный регистр сдвига следующего вида: z1 z2 ?  ·i 6 ? +i x (д) линейный автомат над полем GF (2) с матрицами ( ) ( ) ( ) ( ) 1 1 0 1 1 1 A= ,B = ,C = ,D = . 1 0 0 1 1 Какие из этих автоматов являются регулярными? 1.3 Построить автомат, который в некотором начальном состоянии осуществляет следующее отображение двоичных последовательностей: (а) yi = 1 ⇔ x1 ⊕ x2 ⊕ · · · ⊕ xi = 0 ; (б) yi = 1 ⇔ x1 + x2 + · · · + xi < i; (в) yi = 1 ⇔ xi−3 = xi−2 = xi−1 = xi . 1.4 Докажите, что не существует конечного автомата с алфавитами X = Y = {0, 1}, который при некотором фиксированном начальном состоянии осуществляет отображение yi = 1 ⇔ x1 + x2 + · · · + xi < i/2. Постройте автомат с бесконечным числом состояний, удовлетворяющий требуемым условиям. 1.5 Укажите все внутренние подавтоматы автомата A = (X, S, Y, h, f ). (а)  ?   sn 1 (б) sn 2   ? ?   - sn  sn 1 2 - sn 3   ?  sn 4   sn 3 s4n 1.6 Найдите компоненты связности автомата, заданного переходно-выходной таблицей. Для каждой компоненты связности выяснить является ли она сильно связным, внутренне 19 (внешне) автономным автоматом, регулярным автоматом? (а) X S 1 2 3 4 5 6 7 8 x1 x2 5, 0 3, 1 3, 1 8, 1 1, 1 4, 1 7, 0 6, 0 5, 0 7, 0 7, 1 8, 1 5, 0 4, 1 7, 0 6, 0 X S 1 2 3 4 5 6 7 8 (б) x1 x2 7, 1 8, 1 2, 0 5, 1 4, 0 3, 0 1, 0 6, 1 1, 1 2, 1 6, 1 1, 1 7, 0 3, 0 1, 0 8, 1 1.7 Приведите пример связного автомата, но не являющегося сильно связным. Всегда ли является связным подавтомат связного автомата? Приведите пример сильно связного, но нерегулярного автомата. Всегда ли является регулярным подавтомат регулярного автомата? 1.8 Построить граф двоичного регистра сдвига R(ψ, φ) длины 3 без выхода, если (а) φ(z1 , z2 , z3 , x) = z1 ⊕ z2 z3 ⊕ x, (б) φ(z1 , z2 , z3 , x) = z1 z2 ⊕ z3 x, (в) φ(z1 , z2 , z3 , x) = z1 ⊕ z̄2 z3 x. Выяснить, является ли автомат связным, сильно связным, регулярным? 1.9 Докажите утверждение 1.9. Приведите примеры сильно связных автономных двоичных регистров сдвига длины 2 и 3, показывающие, что условие утверждения 1.27 не является необходимым. 1.10 Пусть Z — коммутативное кольцо с единицей. (а) Докажите, что линейный автомат L(A, B, C, D) над кольцом Z регулярен тогда и только тогда, когда матрица A обратима над кольцом Z. (б) Покажите, что автономный линейный регистр сдвига R(a1 , . . . , an ) является линейным автоматом и укажите критерий его регулярности. 1.11 Укажите переходно-выходные таблицы автоматов, изоморфных автоматам из задачи 1.6, при действии внутреннего изоморфизма (εX , β, εY ), где ( ) 1 2 3 4 5 6 7 8 . β= 2 3 7 6 1 8 5 4 1.12 (а) Построить сюръективный внутренний гомоморфизм автомата A1 в автомат A2 . X S 1 2 3 A1 a b 2, 0 3, 1 1, 0 3, 1 3, 1 1, 0 X S s1 s2 A2 a b s1 , 0 s2 , 1 s2 , 1 s1 , 0 (б) Построить сюръективный гомоморфизм автомата A1 в автомат A2 . A1 X S s1 s2 s3 s4 1 2 s4 , 0 s3 , 0 s3 , 2 s4 , 1 s3 , 0 s3 , 0 s4 , 1 s4 , 1 s2 , 1 s1 , 2 s1 , 2 s1 , 2 A2 X S s1 s2 a b s2 , c s1 , d s2 , d s1 , d 20 1.13 Построить сюръективный гомоморфизм автономного автомата (1, 7, {0, 1, 2}, h1 , f1 ) в автономный автомат (1, 4, {0, 1}, h2 , f2 ), если их функции переходов и выходов заданы следующими таблицами: ( ( ) ) 1 2 3 4 5 6 7 1 2 3 4 h1 = , h2 = , 2 4 4 5 6 7 4 2 3 4 3 ( ) ( ) 1 2 3 4 5 6 7 1 2 3 4 f1 = , f2 = . 0 0 0 0 1 0 2 1 1 1 0 1.14 Докажите утверждение 1.33. 1.15 Пусть Li = L(Ai , Bi , Ci , Di ), i = 1, 2 — линейные автоматы над коммутативным кольцом Z с единицей. Назовем автомат L2 подобным линейному автомату L1 , если найдется обратимая матрица Q над кольцом Z такая, что A2 = Q−1 A1 Q, B2 = B1 Q, C2 = Q−1 C1 , D2 = D1 . Докажите, что (а) отношение подобия является отношением эквивалентности на множестве всех линейных автоматов; (б) подобные линейные автоматы внутренне изоморфны; (в) существуют внутренне изоморфные, но не подобные линейные автоматы. 1.16 Будут ли изоморфны автономные автоматы A1 и A2 , заданные следующими графами: A2 -1 A1 -0 0 n 0 n    sn sn s2  sn sn sn s1 sn 2 4 4 1 3 3   1 1.17 Докажите, что автоматы являются внутренне изоморфными. Укажите этот изоморфизм. (a) X S 1 2 3 4 5 a b 1, 0 4, 0 1, 0 3, 1 2, 1 5, 1 1, 1 4, 1 4, 1 5, 1 X S 1 2 3 4 5 a b 3, 0 4, 1 3, 0 5, 0 1, 1 5, 1 2, 1 2, 1 3, 1 5, 1 (б) X S 1 2 3 4 5 a b 2, 0 4, 1 5, 1 3, 0 1, 1 5, 0 3, 0 2, 0 1, 0 4, 0 X S 1 2 3 4 5 a b 3, 1 1, 0 5, 1 2, 1 4, 0 4, 0 5, 0 2, 0 1, 0 3, 0 1.18 Разбейте семейство автоматов {A1 , . . . , A6 } на классы изоморфных автоматов A1 X S 1 2 3 A4 X S 1 2 3 1, 0 3, 0 2, 1 3, 0 2, 1 3, 0 A2 X S 1 2 3 A5 X S 1 2 3 1 1 1, 0 3, 0 2, 1 3, 1 1, 0 3, 0 2, 0 1, 0 2, 1 3, 1 2, 1 3, 1 A3 X S 1 2 3 A6 X S 1 2 3 1 1 3, 0 1, 1 2, 1 1, 1 3, 0 1, 1 1 1, 0 3, 1 2, 1 3, 1 2, 0 3, 1 1 3, 1 1, 1 3, 1 1, 0 3, 1 3, 0 21 1.19 Пусть (α, β, γ) — сюръективный гомоморфизм автомата A1 в автомат A2 . Докажите, что: (а) если A1 — связен, то A2 — связен; (б) если A1 — сильно связен, то A2 — сильно связен; (в) если A1 — автомат Мура, то и A2 — автомат Мура; (г) если A1 — регулярен, то A2 — регулярен. Глава 2. Операции с автоматами. Проблема полноты. В этом параграфе будут рассмотрены основные операции с автоматами, позволяющие получать из исходных автоматов новые автоматы. Пусть A1 = (X1 , S1 , Y1 , h1 , f1 ) и A2 = (X2 , S2 , Y2 , h2 , f2 ) — произвольные автоматы. 1. Сумма автоматов. Пусть в автоматах A1 и A2 совпадают входные алфавиты X1 = X2 = X, а множества состояний S1 и S2 не имеют общих элементов. Тогда суммой автоматов A1 и A2 называется автомат A1 +A2 = (X, S1 ∪S2 , Y1 ∪Y2 , h, f ), у которого функции переходов и выходов заданы соотношениями: h(s, x) = hi (s, x), f (s, x) = fi (s, x), для всех s ∈ Si , i ∈ {1, 2} и для всех x ∈ X. Заметим, что автоматы A1 и A2 являются подавтоматами автомата A1 + A2 . Кроме того, автомат A1 + A2 , находясь в начальном состоянии s ∈ Si функционирует одинаково с автоматом Ai , находящимся в этом же начальном состоянии. Аналогично определению суммы двух автоматов определяется сумма произвольного числа автоматов. Несложно показать, что если S = S1 ∪S2 ∪. . .∪Sr — разбиение множества состояний автомата A на классы связных состояний, то A = A1 + A2 + . . . + Ar , где Ai — компонента связности автомата A, i ∈ 1, r. 2. Произведение автоматов. Произведением автоматов A1 и A2 называется автомат A1 × A2 = (X1 × X2 , S1 × S2 , Y1 × Y2 , h, f ), у которого функции переходов и выходов заданы соотношениями: h((s1 , s2 ), (x1 , x2 )) = (h1 (s1 , x1 ), h2 (s2 , x2 )), f ((s1 , s2 ), (x1 , x2 )) = (f1 (s1 , x1 ), f2 (s2 , x2 )), для всех si ∈ Si и для всех xi ∈ Xi , где i ∈ {1, 2}. Произведение автоматов изображают следующим образом: - A1 - - A2 - Зададим отображения αi : X1 × X2 → Xi , βi : S1 × S2 → Si и γi : Y1 × Y2 → Yi на соответствующих множествах равенствами αi (x1 , x2 ) = xi , βi (s1 , s2 ) = si , γi (y1 , y2 ) = yi , 22 где i ∈ {1, 2}. Несложно показать, что (αi , βi , γi ) является сюръективным гомоморфизмом автомата A1 × A2 в автомат Ai . 3. Параллельное соединение автоматов. Пусть у автоматов A1 и A2 совпадают входные алфавиты X1 = X2 = X. Тогда параллельным соединением автоматов A1 и A2 называется автомат A1 ||A2 = (X, S1 × S2 , Y1 × Y2 , h, f ), у которого функции переходов и выходов заданы соотношениями: h((s1 , s2 ), x) = (h1 (s1 , x), h2 (s2 , x)), f ((s1 , s2 ), x) = (f1 (s1 , x), f2 (s2 , x)), для всех si ∈ Si , i ∈ {1, 2} и для всех x ∈ X. В отличие от произведения автоматов, в параллельном соединении автоматов подается общий вход. Пусть βi и γi такие же отображения, как и при рассмотрении произведения автоматов. Несложно показать, что тройка (εX , βi , γi ) является сюръективным гомоморфизмом автомата A1 ||A2 в автомат Ai , где εX — тождественное отображение на множестве X. Параллельное соединение автоматов изображают следующим образом: - A1 - - A2 - - 4. Последовательное соединение автоматов. Пусть выходной алфавит Y1 автомата A1 является подмножеством входного алфавита X2 автомата A2 . Тогда, последовательным соединением автоматов A1 и A2 называется автомат A1 → A2 = (X1 , S1 × S2 , Y2 , h, f ), у которого функции переходов и выходов заданы соотношениями: h((s1 , s2 ), x) = (h1 (s1 , x), h2 (s2 , f1 (s1 , x))), f ((s1 , s2 ), x) = f2 (s2 , f1 (s1 , x)), для всех si ∈ Si , i ∈ {1, 2} и для всех x ∈ X1 . Последовательное соединение автоматов изображают следующим образом: - - A1 A2 - Аналогично определению произведения, параллельного и последовательного соединения двух автоматов определяется произведение, параллельное и последовательное соединение произвольного числа автоматов. 5. Введение обратной связи. Определим операцию введения обратной связи в автомате A = (X, S, Y, h, f ). Пусть X = X1 × X2 × . . . × Xm , Y = Y1 × Y2 × . . . × Yr . В этом случае автомат A изображают следующим образом: x1 xi xm ..... .- A ..- y1 .- y j .. .- y r 23 и говорят, что A имеет m входов и r выходов. Пусть отображение f имеет координатные функции f1 , . . ., fr , т. е. для всех (x1 , . . . , xm ) ∈ X, s ∈ S f (s, (x1 , . . . , xm )) = (f1 (s, (x1 , . . . , xm )), . . . , fr (s, (x1 , . . . , xm ))). Пусть также Yj ⊂ Xi и координатная функция fj имеет фиктивную переменную xi . Построим новый автомат A′ = (X ′ , S, Y, h′ , f ′ ) с алфавитом X ′ = X1 × . . . × Xi−1 × Xi+1 × . . . × Xm , и функциями, которые при всех (x1 , . . . , xi−1 , xi+1 , . . . , xm ) ∈ X ′ , s ∈ S заданы по правилу: h′ (s, (x1 , . . . , xi−1 , xi+1 , . . . , xm )) = h(s, (x1 , . . . , xi−1 , yj′ , xi+1 , . . . , xm )), f ′ (s, (x1 , . . . , xi−1 , xi+1 , . . . , xm )) = f (s, (x1 , . . . , xi−1 , yj′ , xi+1 , . . . , xm )), где yj′ = fj (s, x1 , . . . , xi−1 , x, xi+1 , . . . , xm ), а x — произвольный элемент множества Xi . В этом случае говорят, что автомат A′ получен из A введением обратной связи по i-ому входу и j-ому выходу. Его изображают следующим образом: x1 . .. .. . xm - A′ .. - y1 .- y j .. .- y r Зачастую автомат представляется с использованием, так называемой, сети из более простых автоматов. При построении сети автоматов используются все описанные выше операции с автоматами. Кроме того, допускается присоединение выходов одного автомата к некоторым входам других автоматов, но не допускается присоединение нескольких различных выходов к одному входу. Возникает вопрос: каким должно быть множество M автоматов, чтобы с их использованием можно было представить в виде сети любой автомат (при этом каждый автомат из множества M можно использовать в сети сколь угодное количество раз)? Эту задачу называют проблемой полноты в теории автоматов. Утверждение 2.1 Каждый автомат A = (X, S, Y, h, f ) представляется в виде следующей сети, построенной с использованием автоматов без памяти H = (S × X, S, h), F = (S × X, Y, f ) и задержки D = (S, S, S, h̃, f˜) на один такт: - H - D - F - Доказательство. Пусть в момент времени t = 1, 2, . . . на вход сети подается входной символ xt , а задержка D на один такт находится в состоянии st . На вход автомата F поступает пара (st , xt ) и вырабатывается выход f (st , xt ). Автомат H выработает выходной символ h(st , xt ) и задержка D перейдет в следующее состояние h(st , xt ). Таким образом данная сеть реализует автомат A.  Реализуем автомат A = (X, S, Y, h, f ) с использованием автоматов, у которых входные, выходные символы и состояния являются двоичными векторами. Пусть числа m, 24 n, r ∈ N подобраны так, что |X| ≤ 2m , |S| ≤ 2n , |Y | ≤ 2r . Зададим произвольно инъективные отображения α : X → {0, 1}m , β : S → {0, 1}n , γ : Y → {0, 1}r . Пусть A′ = (α(X), β(S), γ(Y ), h′ , f ′ ), где для всех (x1 , . . . , xm ) ∈ α(X), (s1 , . . . , sn ) ∈ β(S) h′ ((s1 , . . . , sn ), (x1 , . . . , xm )) = β(h(β −1 (s1 , . . . , sn ), α−1 (x1 , . . . , xm ))), f ′ ((s1 , . . . , sn ), (x1 , . . . , xm )) = γ(f (β −1 (s1 , . . . , sn ), α−1 (x1 , . . . , xm ))). Отображение (α, β, γ) является изоморфизмом автомата A в автомат A′ . Пусть A′′ = ({0, 1}m , {0, 1}n , {0, 1}r , h′′ , f ′′ ), где h′′ и f ′′ выбраны так, что их ограничения на множество β(S) × α(X) совпадают с h′ и f ′ соответственно. С использованием утверждения 2.1 получим Теорема 2.2 Автомат A изоморфен подавтомату A′ автомата A′′ , при этом автомат A′′ реализуется с использованием двух автоматов без памяти и n двоичных задержек следующим образом: - .. . - x1 xm ′′ - h - △ .. . - △ - .. . - ′′ - f .. . .. . - - - y1 .. . - yr Для каждой булевой функции φ(x1 , . . . , xk ) обозначим через A(φ) автомат без памяти ({0, 1}k , {0, 1}, φ). Пусть {φ1 , . . . , φs } — полное семейство булевых функций, т. е. замыкание этого класса совпадает с множеством всех булевых функций. Каждая координатная функция отображений h′′ и f ′′ является суперпозицией функций φ1 , . . ., φs . Отсюда с использованием теоремы 2.2 получим следующий результат. Следствие 2.3 Произвольный автомат A изоморфен подавтомату автомата A′′ , при этом A′′ может быть построен с использованием автоматов без памяти A(φ1 ), . . ., A(φs ) и n = ] log2 |S|[ двоичных задержек. Примером полного множества M автоматов является множество M = {A(φ1 ), A(φ2 ), D}, где φ1 (x1 , x2 ) = x1 x2 , φ2 (x1 ) = x̄1 , а D — двоичная задержка на один такт. ЗАДАЧИ 2.1 Пусть G1 = (GF (2), ⊕), G2 = (GF (2), ·), K(Gi ) — автомат Кэли полугруппы Gi , i = 1, 2. Постройте переходно-выходные таблицы следующих автоматов: (а) K(G1 ) + K(G2 ); (б) K(G1 ) × K(G2 ); (в) K(G1 ) ∥ K(G2 ); (г) K(G1 ) → K(G2 ); 25 (д) K(G2 ) → K(G1 ); (е) полученного из K(G1 ) введением обратной связи; (ж) полученного из K(G2 ) введением обратной связи. 2.2 Выписать функции переходов и выходов следующего последовательного соединения автоматов: A1 z1 z2  6 z3 A2 - ·? i ? z4 - +i ? 6 +i ? ·i 2.3 (а) Будет ли связным автоматом сумма, произведение и последовательное соединение связных автоматов? (б) Показать, что если автомат A1 → A2 — связен, то связны автоматы A1 и A2 . 2.4 Пусть Ai = (Xi , Si , Yi , hi , fi ), i = 1, 2 — произвольные автоматы. (а) Докажите, что если ∗ ∈ {+, ∥, ×}, то A1 ∗ A2 регулярен тогда и только тогда, когда A1 и A2 регулярны. (б) Если автоматы A1 и A2 регулярны, то автомат A1 → A2 регулярен, а если f1 (S1 ×X1 ) = X2 , то верно и обратное утверждение. 2.5 Построить внутренний изоморфизм следующих двоичных автоматов: (a)   ? +i  ?  + i ?  + i (б) - +i 6 +i 6      ? -+ i 2.6 Пусть автомат A = ({0, 1}2 , {0, 1}, {0, 1}2 , h, f ) имеет вид: x1 - x2 - - y1 A - y2 Выписать функции переходов и выходов автомата A′ , полученного из A введением обратной связи по входу xi и выходу yj , если (а) h(s, (x1 , x2 )) = sx1 ∨ x2 , f (s, (x1 , x2 )) = (s̄, sx1 ), i = j = 1; (б) h, f из пункта (a), i = 2, j = 1; (в) h, f из пункта (a), i = 2, j = 2; (г) h(s, (x1 , x2 )) = s ∨ x1 x2 , f (s, (x1 , x2 )) = (s ⊕ x2 , sx1 x2 ), i = j = 1; (д) h(s, (x1 , x2 )) = s ⊕ x1 x2 , f (s, (x1 , x2 )) = (sx1 ∨ x2 , s̄x̄2 ), i = 1, j = 2; (e) h(s, (x1 , x2 )) = s̄ ∨ x2 , f (s, (x1 , x2 )) = (s ⊕ x1 , s̄x1 ⊕ s̄x2 ), i = 2, j = 1; (ж) h(s, (x1 , x2 )) = s ⊕ x1 ⊕ x2 , f (s, (x1 , x2 )) = (sx2 , s̄x1 ), i = 2, j = 2. 2.7 Заданы автоматы без памяти A1 = ({0, 1}, {0, 1}, f1 ), Ai = ({0, 1}2 , {0, 1}, fi ), i = 2, 3, где f1 (x1 ) = x̄1 , f2 (x1 , x2 ) = x1 ∨ x2 , f3 (x1 , x2 ) = x1 x2 . Выписать функции переходов и 26 выходов следующих автоматов: (a)   △ A2   A1  (б)  A3  △ (в) △    A3   A2  A3  A1  △ (г) △    A2    A3  A2  A1  △ 2.8 Представить автомат A = ({0, 1}, {0, 1}2 , {0, 1}, h, f ) в виде сети, построенной с использованием двоичных задержек и автоматов A1 , A2 , A3 из задачи 2.7, если (а) h(s1 , s2 , x) = (s1 s̄2 , x), f (s1 , s2 , x) = s1 s̄2 ∨ x; (б) h(s1 , s2 , x) = (x, s̄1 ∨ s2 x), f (s1 , s2 , x) = s2 ; (в) h(s1 , s2 , x) = (s2 , s1 ∨ x), f (s1 , s2 , x) = s2 x̄ ∨ s1 ; (г) h(s1 , s2 , x) = (s2 x̄, s̄1 s̄2 ∨ s̄1 x̄), f (s1 , s2 , x) = s1 ∨ s2 x. 2.9 Представить автомат A в виде сети, построенной с использованием двоичных задержек и автоматов A1 , A2 , A3 из задачи 2.7. (a) X S 1 2 3 4 1 1, 0 2, 1 2, 1 2, 1 3, 0 3, 0 3, 0 3, 0 (б) X S 1 2 3 4 1 2, 0 2, 1 2, 1 2, 1 1, 0 3, 1 3, 1 3, 1 27 (в) X S 1 2 3 4 1 2 3 4 1, 0 1, 0 2, 0 2, 1 2, 1 2, 1 2, 1 2, 1 1, 0 1, 0 2, 0 2, 1 4, 1 4, 1 4, 1 4, 1 (г) X S 1 2 3 4 1 2 3 4 1, 1 1, 0 1, 1 1, 0 1, 1 1, 1 1, 1 1, 1 3, 1 4, 0 3, 1 4, 0 3, 1 4, 1 4, 1 4, 1 2.10 Пусть P = GF (3). Представить следующие автоматы в виде сети, построенной с использованием двоичных задержек и автоматов A1 , A2 , A3 из задачи 2.7: (а) автомат Кэли полугруппы (P, ·); (б) автомат Кэли группы (P, +); (в) регистр сдвига R(ψ, φ), n = 2, X = Z = P , φ(z1 , z2 , x) = z1 + 2x, ψ(z1 , z2 , x) = z1 z2 + x; (г) линейный автомат L(A, B, C, D) с матрицами     ( ( ) ) 0 0 1 1 0 0 1 A =  1 0 0 ,B = ,C =  1 ,D = . 0 2 0 1 0 1 0 2 2.11 Докажите, что с использованием следующих автоматов можно реализовать произвольный автомат: (а) двоичной задержки, A1 , A2 ; (б) двоичной задержки, A1 , A3 ; (в) двоичной задержки и автомата A4 = ({0, 1}2 , {0, 1}, f4 ), где f4 (x1 , x2 ) = x1 x2 ; (г) автомата Кэли K(G) группы G = (GF (2), +) и автомата A4 из пункта (в). Здесь автоматы A1 , A2 , A3 такие как в условии задачи 2.7. Глава 3. Эквивалентность в автоматах. §3.1 Свойства эквивалентных состояний. Пусть A = (X, S, Y, h, f ) — произвольный автомат. Определение 3.1 Состояния s и s′ автомата A называются k-эквивалентными, если для всех входных последовательностей x̄ ∈ X k выполнено As (x̄) = As′ (x̄). Другими словами, состояния являются k-эквивалентными, если автомат A, находясь в начальных состояниях s и s′ соответственно, одинаково перерабатывает любые входные последовательности длины k. Для k-эквивалентных состояний будем использовать обознаk чение s ∼ s′ . Состояния s и s′ , которые не являются k-эквивалентными, будем называть k-различимыми состояниями. k Определение 3.2 Состояния s и s′ автомата A называются эквивалентными, если s ∼ s′ для всех натуральных чисел k. Если состояния s и s′ являются эквивалентными, то автомат A, находясь в начальных состояниях s и s′ , одинаково перерабатывает любые входные последовательности. Для эквивалентных состояний будем использовать обозначение s ∼ s′ . Неэквивалентные состояния будем называть различимыми состояниями. k Нетрудно видеть, что бинарные отношения ∼ и ∼ являются отношениями эквивалентности на множестве состояний S автомата A. Таким образом, множество S разбивается на непересекающиеся классы k-эквивалентных состояний и на непересекающиеся 28 классы эквивалентных состояний. Обозначим [s]∼k — множество всех состояний автомата A, k-эквивалентных состоянию s и [s]∼ — множество всех состояний, эквивалентных состоянию s. Из определений следует, что множество [s]∼ является подмножеством множества [s]∼k . Определим также на множестве S отношение ∼, положив s∼s′ для всех s, s′ ∈ S. Установим отношений k-эквивалентности и эквивалентности состояний в автомате. Теорема 3.3 Пусть k- целое неотрицательное число, s и s′ — произвольные состояния автомата A. Тогда k+1 k 1) если s ∼ s′ , то s ∼ s′ , k+1 k 2) s ∼ s′ тогда и только тогда, когда для всех x ∈ X h(s, x) ∼ h(s′ , x) и f (s, x) = f (s′ , x), 3) s ∼ s′ тогда и только тогда, когда для всех x ∈ X h(s, x) ∼ h(s′ , x) и f (s, x) = f (s′ , x), 4) если k ≥ 1, то состояния s и s′ являются k + 1-эквивалентными тогда и только тогда, k k когда для всех x ∈ X s ∼ s′ и h(s, x) ∼ h(s′ , x), k k+1 k 5) если отношение ∼ совпадает с отношением ∼ , то отношение ∼ совпадает с отношением ∼. k+1 Доказательство. 1) Если s ∼ s′ , то для всех входных символов x1 , x2 , . . ., xk+1 ∈ X выполнено равенство f ∗ (s, x1 x2 . . . xk+1 ) = f ∗ (s′ , x1 x2 . . . xk+1 ). (3.1) По правилу функционирования автомата, получим, что для всех входных символов x1 , x2 , . . ., xk+1 ∈ X будет выполнено соотношение f ∗ (s, x1 x2 . . . xk )f (sk , xk+1 ) = f ∗ (s′ , x1 x2 . . . xk )f (s′k , xk+1 ), где sk = h(s, x1 . . . xk ), а s′k = h(s′ , x1 . . . xk ). Таким образом, состояния s и s′ являются k-эквивалентными. 2) Состояния s и s′ являются k + 1-эквивалентными тогда и только тогда, когда выполнено равенство (3.1). По правилу функционирования автомата, получим, что для всех входных символов x1 , x2 , . . ., xk+1 ∈ X справедливо равенство f (s, x1 )f ∗ (s1 , x2 . . . xk+1 ) = f (s′ , x1 )f ∗ (s′1 , x2 . . . xk+1 ), k где s1 = h(s, x1 ), s′1 = h(s′ , x1 ). Это, в свою очередь, равносильно условию h(s, x) ∼ h(s′ , x) и f (s, x) = f (s′ , x) для всех x ∈ X. k+1 3) Состояния s и s′ являются эквивалентными тогда и только тогда, когда s ∼ s′ для всех k ≥ 0. Согласно уже доказанному пункту 2), это условие равносильно условиям k h(s, x) ∼ h(s′ , x) и f (s, x) = f (s′ , x) для всех k ≥ 0 и всех x ∈ X. Таким образом, s ∼ s′ тогда и только тогда, когда h(s, x) ∼ h(s′ , x) и f (s, x) = f (s′ , x) для всех x ∈ X. k 4) Если s и s′ являются k + 1-эквивалентными, то, согласно пунктам 1) и 2), s ∼ s′ и k k k h(s, x) ∼ h(s′ , x) для всех x ∈ X. Наоборот, из условия s ∼ s′ и h(s, x) ∼ h(s′ , x) для всех k x ∈ X следует, что f (s, x) = f (s′ , x) и h(s, x) ∼ h(s′ , x) для всех x ∈ X. Значит, по пункту 2), состояния s и s′ являются k + 1-эквивалентными. k k+1 k k+2 5) Покажем, что из условия ∼= ∼ следует, что ∼= ∼ . Пусть состояния s и s′ k+1 являются k-эквивалентными. Тогда из условия имеем s ∼ s′ . Из пункта 2) следует, k что f (s, x) = f (s′ , x) и h(s, x) ∼ h(s′ , x) для всех x ∈ X, а значит f (s, x) = f (s′ , x) и 29 k+1 k+2 h(s, x) ∼ h(s′ , x) для всех x ∈ X. Отсюда следует, что s ∼ s′ . Аналогично рассуждая k k+i k далее, получим ∼= ∼ для всех i ≥ 0, а значит ∼= ∼ .  Пусть дан автомат A = (X, S, Y, h, f ). Требуется найти разбиение множества S на классы эквивалентных состояний. Укажем один из способов построения искомого разбиения. Сначала найдем разбиение множества S на классы 1-эквивалентных состояний, сравнивая выходы автомата при различных входных символах. Пусть уже построено разбиение множества S на классы k-эквивалентных состояний и оно имеет вид: S = Sk1 ∪ Sk2 . . . ∪ Skr , где k ≥ 1. По этому разбиению строится разбиение множества S на классы k+1-эквивалентных состояний S = Sk+11 ∪ Sk+12 . . . ∪ Sk+1m , которое согласно пункту 1 теоремы 3.3 является измельчением разбиения на классы kэквивалентных состояний, то есть для всех i ∈ 1, m найдется j ∈ 1, r такое, что Sk+1i ⊂ Skj . Разбиение на классы k + 1-эквивалентных состояний строится по следующему правилу: выбираются произвольные состояния s и s′ , содержащиеся в одном классе Ski , где i ∈ 1, r. Если состояния h(s, x) и h(s′ , x) попадают в одинаковые классы k-эквивалентных состояний при любых входных символах x ∈ X, то, по пункту 4 теоремы 3.3, состояния s и s′ относятся в один класс k + 1-эквивалентных состояний. В противном случае, s и s′ оказываются в разных классах k + 1-эквивалентных состояний. Из пункта 5 теоремы 3.3 следует, что разбиение на классы k-эквивалентных состояний является разбиением на классы эквивалентных состояний как только оно совпадет с разбиением на классы k + 1-эквивалентных состояний. Пример 3.4 Пусть автомат задан следующей переходно-выходной таблицей: X S 1 2 3 4 5 6 x1 x2 3, 0 4, 0 2, 1 1, 1 6, 0 5, 1 2, 1 1, 1 4, 1 4, 1 1, 1 5, 1 Разбиение на классы 1-эквивалентных состояний находится по определению 1-эквивалентности и имеет вид: {1, 2, 5} {3, 4, 6}. Классы 2-эквивалентных состояний будут следующими: {1, 2, 5} {3, 4} {6}. Состояния 3 и 6 оказались в разных классах так как h(3, a) и h(6, a) оказались в разных классах 1-эквивалентности. Разбиение на классы 3-эквивалентности будет таким: {1, 2} {5} {3, 4} {6}. 30 Здесь состояния 1 и 5 являются 3-различимыми так как состояния h(1, a) и h(5, a) являются 2-различимыми. Разбиение на классы 4-эквивалентных состояний имеет вид: {1, 2} {5} {3, 4} {6}. Оно совпадает с разбиением на классы 3-эквивалентности, а значит является разбиением на классы эквивалентных состояний. §3.2 Минимальная форма автомата. В случае, когда в автомате есть различные эквивалентные состояния, можно построить автомат, имеющий меньшее число состояний и осуществляющий такое же преобразование входных последовательностей в выходные последовательности, как и исходный автомат. Наличие меньшего числа состояний приводит к тому, что с точки зрения реализации такой автомат является, как правило, более простым. Пусть ε1 и ε3 — отношения равенства на множествах X и Y соответственно. Из пункта 3 теоремы 3.3 следует, что (ε1 , ∼, ε3 ) является внутренней конгруэнцией автомата A. Определение 3.5 Факторавтомат à = A/(ε1 , ∼, ε3 ) = (X, S̃, Y, h̃, f˜) называется минимальной (приведенной) формой автомата A, а число µ(A) = |S̃| приведенным весом автомата A. Функции переходов и выходов автомата à задаются следующими равенствами: f˜([s]∼ , x) = f (s, x), h̃([s]∼ , x) = [h(s, x)]∼ , для всех классов [s]∼ ∈ S̃ и входных символов x ∈ X. Рассмотрим пример построения минимальной формы автомата. Пример 3.6 Построим минимальную форму автомата A из примера 3.4. Классами эквивалентности будут множества S1 = {1, 2}, S2 = {5}, S3 = {3, 4}, S4 = {6}. Минимальная форма автомата A будет иметь алфавит состояний S̃ = {S1 , S2 , S3 , S4 } и будет задаваться следующей переходно-выходной таблицей: X S S1 S2 S3 S4 a b S3 , 0 S4 , 0 S1 , 1 S2 , 1 S1 , 1 S1 , 1 S3 , 1 S2 , 1 Следующее утверждение описывает связь внутренних конгруэнций автомата A и отношения эквивалентности состояний. Утверждение 3.7 Пусть (ε1 , ε, ε3 ) — внутренняя конгруэнция автомата A, тогда для любых s, s′ ∈ S если sεs′ , то s ∼ s′ . Доказательство. Покажем, что если sεs′ то для всех l ∈ N, x1 , . . ., xl ∈ X выполнено As (x1 · · · xl ) = As′ (x1 · · · xl ). Соотношение sεs′ по определению внутренней конгруэнции влечет f (s, x1 ) = f (s′ , x1 ) и h(s, x1 )εh(s′ , x1 ). Отсюда получим f (h(s, x1 ), x2 ) = f (h(s′ , x1 ), x2 ) и h(s, x1 x2 )εh(s′ , x1 x2 ). Аналогично рассуждая далее получим As (x1 · · · xl ) = As′ (x1 · · · xl ). Таким образом s ∼ s′ .  Утверждение 3.7 показывает, что разбиение множества S на классы по отношению ε является измельчением разбиения на классы эквивалентных состояний. 31 Определение 3.8 Автомат A у которого µ(A) = |S| называется минимальным. Заметим, что à — минимальный автомат, причем существует сюръективный внутренний гомоморфизм (естественный гомоморфизм) автомата A в автомат Ã. Таким образом, согласно утверждению 1.32, при переходе от автомата A к его минимальной форме Ã, наследуются возможности преобразования входных последовательностей в выходные последовательности, но при этом автомат à не содержит эквивалентных состояний. Утверждение 3.9 Существует сюръективный внутренний гомоморфизм автомата A в автомат с меньшим числом состояний тогда и только тогда, когда автомат A не минимален. Доказательство. Если автомат A не минимален, то существует естественный гомоморфизм автомата A в его приведенную форму Ã, причем |S̃| < |S|. Пусть теперь (εX , β, εY ) — внутренний сюръективный гомоморфизм автомата A в автомат A′ и |β(S)| < |S|. Тогда найдутся различные состояния s, s′ ∈ S такие, что β(s) = β(s′ ). Согласно утверждению 1.32 для всех l ∈ N, x1 , . . ., xl ∈ X выполнено As (x1 . . . xl ) = A′β(s) (x1 . . . xl ) = A′β(s′ ) (x1 . . . xl ) = As′ (x1 . . . xl ), т. е. s ∼ s′ и автомат A не минимален.  §3.3 Степень различимости и приведенный вес автомата. Пусть A = (X, S, Y, h, f ) — произвольный автомат. Определение 3.10 Степенью различимости автомата A называется наименьшее целое неотрицательное число k такое, что отношение k-эквивалентности состояний автомата A совпадает с отношением эквивалентности. Степень различимости автомата A будем обозначать δ(A). Как следует из пункта 5 теоk k+1 ремы 3.3 степень различимости δ(A) совпадает с минимальным k таким, что ∼= ∼ . Если δ(A) s ∼ s′ для некоторых состояний s, s′ ∈ S, то состояния s и s′ эквивалентны, в противном случае они не являются эквивалентными. Поэтому, параметр δ(A) является наименьшей длиной входных последовательностей, с использованием которых может быть решена задача эквивалентности произвольных состояний автомата A. Заметим, что δ(A) ≥ 0, причем δ(A) = 0 тогда и только тогда, когда все состояния автомата A эквивалентны. Определение 3.11 Приведенным весом автомата A называется число µ(A) всех классов эквивалентных состояний в автомате A. Для автомата A из примера 3.4 справедливы равенства δ(A) = 3, а µ(A) = 4. Установим теперь некоторые оценки степени различимости произвольного автомата A. Теорема 3.12 В произвольном автомате A = (X, S, Y, h, f ) справедливы следующие неравенства: δ(A) ≤ µ(A) − 1 ≤ |S| − 1. Доказательство. Второе из этих неравенств очевидно. Докажем первое неравенство. Пусть разбиения на классы k-эквивалентных состояний автомата A имеют следующий вид: S = S11 ∪ S12 ∪ . . . ∪ S1r − классы 1-эквивалентных состояний, 32 S = S21 ∪ S22 ∪ . . . ∪ S2t − классы 2-эквивалентных состояний, ··· S = Sδ1 ∪ Sδ2 ∪ . . . ∪ Sδm − классы эквивалентных состояний, где δ = δ(A), а m = µ(A). Рассмотрим следующие два случая. 1) Число r классов 1-эквивалентных состояний равно 1. В этом случае любые состояния s и s′ из множества S являются 1-эквивалентными. Тогда из пункта 5) теоремы 3.3 1 следует, что ∼=∼=∼. Значит δ(A) = 0, а µ(A) = 1 и неравенство доказано. 2) Пусть теперь r > 1. Тогда, так как разбиение на классы 2-эквивалентных состояний является измельчением разбиения на классы 1-эквивалентных состояний и при k ≤ δ(A) разбиения на классы k-эквивалентных состояний не повторяются, то t > 2. Аналогично рассуждая далее получим, что m > δ. Значит δ(A) ≤ µ(A) − 1.  Следствие 3.13 Пусть автомат A имеет |S| = n состояний, s, s′ ∈ S. Тогда s ∼ s′ тогда n−1 и только тогда, когда s ∼ s′ . Приведем теперь оценки снизу степени различимости автомата. Теорема 3.14 Пусть A = (X, S, Y, h, f ) — произвольный автомат, у которого |Y | ≥ 2. Тогда 1) если |X| = 1, то δ(A) ≥ log|Y | µ(A), ( ) 2) если |X| ≥ 2, то δ(A) > log|X| log|Y | µ(A) − 1. Доказательство. Эквивалентность состояний s и s′ автомата A определяется при подаче на вход автомата, находящегося в этих начальных состояниях, всех входных последовательностей длины δ = δ(A). 1) Если |X| = 1, то входная последовательность длины δ ровно одна. Всего различных выходных последовательностей длины δ будет |Y |δ . Так как автомат A при произвольных начальных состояниях выдает ровно µ(A) различных выходных последовательностей длины δ, то справедливо неравенство µ(A) ≤ |Y |δ . Значит δ ≥ log|Y | µ(A). 2) Если |X| > 1, то для любых s, s′ ∈ S имеем s sin s′ тогда и только тогда, когда δ s ∼ s′ , что равносильно равенству ограничений As |X δ = As′ |X δ автоматных отображений на множество X δ . Число различных отображений As |X δ равно µ(A). Оценим число различных способов задания As |X δ при фиксированном s. Так как для всех x1 , . . ., xδ ∈ X As (x1 . . . xδ ) = f (s, x1 )f (h(s, x1 ), x2 ) · · · f (h(s, x1 . . . xδ−1 ), xδ ), то для некоторых отображений fi : X i → Y , i = 1, 2, . . . , δ имеем As (x1 . . . xδ ) = f1 (x1 )f2 (x1 , x2 ) · · · fδ (x1 . . . xδ ). Таким образом при фиксированном s число автоматных отображений As |X δ не превосходит числа упорядоченных наборов (f1 , f2 , . . . , fδ ). Существует ровно |Y ||X| способов задать 2 δ f1 , |Y ||X| способов задать f2 , . . ., |Y ||X| способов задать fδ , таким образом число рассматриваемых наборов равно |Y ||X| |Y ||X| · · · |Y ||X| = |Y ||X|+|X| 2 δ 2 +···+|X|δ . Используя формулу суммы элементов геометрической прогрессии и учитывая неравенство |X| ≥ 2, получим |X|δ − 1 < |X|δ+1 . |X| + |X|2 + · · · + |X|δ = |X| |X| − 1 33 Так как автомат A при произвольных начальных состояниях ровно µ(A) способами преобразует все входные последовательности длины δ в выходные последовательности длины δ, то справедливо неравенство δ+1 µ(A) < |Y ||X| . ( ) Значит δ > log|X| log|Y | µ(A) − 1.  §3.4 Эквивалентность автоматов. Пусть A1 = (X, S1 , Y, h1 , f1 ) и A2 = (X, S2 , Y, h2 , f2 ) — произвольные автоматы с одинаковыми входными и выходными алфавитами. Такие автоматы называют сравнимыми. Для состояний сравнимых автоматов тоже можно ввести понятие эквивалентности. Определение 3.15 Состояния s1 автомата A1 и s2 автомата A2 называются k-эквивалентными, если f¯1 (s1 , x̄) = f¯2 (s2 , x̄) для всех входных последовательностей x̄ длины k в алфавите X. k Для k-эквивалентных состояний s1 и s2 будем использовать обозначение s1 ∼ s2 . Определение 3.16 Состояния s1 автомата A1 и s2 автомата A2 называются эквивалентk ными, если s1 ∼ s2 для всех натуральных чисел k. Эквивалентные состояния s1 и s2 автоматов A1 и A2 будем обозначать следующим образом: s1 ∼ s2 . Определение 3.17 Сравнимые автоматы A1 и A2 называются эквивалентными, если для любого состояния s1 автомата A1 найдется состояние s2 автомата A2 такое, что s1 ∼ s2 и наоборот, для любого состояния s2 автомата A2 найдется состояние s1 автомата A1 такое, что s1 ∼ s2 . Для эквивалентных автоматов A1 и A2 будем использовать обозначение A1 ∼ A2 . Каждый автомат A эквивалентен своей минимальной форме Ã, при этом s ∼ [s]∼ для всех состояний s автомата A. Отметим, что вопрос об эквивалентности состояний автоматов A1 и A2 сводится к уже рассмотренному вопросу об эквивалентности состояний одного автомата. Для этого переобозначим элементы множеств S1 и S2 так, чтобы в них не было равных элементов. Рассмотрим автомат A1 + A2 , являющийся суммой автоматов A1 и A2 . Нетрудно показать, что состояния s1 ∈ S1 и s2 ∈ S2 являются k-эквивалентными тогда и только тогда, когда они k-эквивалентны в автомате A1 + A2 . Аналогичное утверждение справедливо и для состояний одного автомата. Автоматы A1 и A2 являются эквивалентными тогда и только тогда, когда вместе с каждым состоянием s1 ∈ S1 автомата A1 в одном классе эквивалентности автомата A1 + A2 содержится состояние s2 ∈ S2 автомата A2 и наоборот. Пример 3.18 Найдем эквивалентные состояния автоматов A1 и A2 , заданых переходновыходными таблицами A1 X S 1 2 3 a b 3, 0 1, 1 2, 1 2, 1 1, 0 3, 1 A2 X S 1 2 a b 2, 0 1, 1 2, 1 2, 1 34 Построим переходно-выходную таблицу автомата A1 + A2 , переобозначив состояния 1 и 2 автомата A2 как 1′ и 2′ соответственно. Она будет иметь следующий вид: X S 1 2 3 1′ 2′ a b 3, 0 2, 1 1, 0 2′ , 0 2′ , 1 1, 1 2, 1 3, 1 1′ , 1 2′ , 1 Разбиение на классы 1-эквивалентных состояний в этом автомате будет следующего вида: {1, 3, 1′ }, {2, 2′ }. Разбиение на классы 2-эквивалентных состояний будет состоять из классов {1, 3}, {1′ }, {2, 2′ }. Разбиение на классы 3-эквивалентных состояний совпадет с разбиением на классы 2-эквивалентных состояний, а значит классы эквивалентных состояний будут следующими: {1, 3}, {1′ }, {2, 2′ }. В частности 2 ∼ 2′ , но не существует состояния автомата A1 эквивалентного состоянию 1′ . Значит автоматы A1 и A2 не являются эквивалентными. Кроме того, состояния 1 и 3 автомата A1 эквивалентны, значит он не является минимальным, в то время как автомат A2 минимален. Сформулируем теперь критерий эквивалентности автоматов в терминах их минимальных форм. Теорема 3.19 Пусть Ai = (X, Si , Y, hi , fi ) — произвольные автоматы, где i ∈ {1, 2}. Тогда равносильны следующие условия: 1)автоматы A1 и A2 эквивалентны, 2)минимальные формы автоматов A1 и A2 эквиваленты, 3) минимальные формы автоматов A1 и A2 внутренне изоморфны. Доказательство. Покажем, что из пункта 1) следует пункт 2), из пункта 2) следует пункт 3), а из пункта 3) следует пункт 1). Таким образом, теорема будет доказана. Пусть автоматы A1 и A2 эквивалентны. Так как A1 ∼ Ã1 , а A2 ∼ Ã2 , то и автоматы Ã1 , Ã2 эквивалентны. Пусть минимальные формы Ã1 и Ã2 автоматов A1 и A2 эквиваленты. Так как автоматы Ã1 и Ã2 минимальны, то число состояний в них одинаково. Для каждого состояния [s1 ]∼ автомата Ã1 существует единственное, эквивалентное ему состояние [s2 ]∼ автомата Ã2 . Зададим отображение β из множества состояний автомата Ã1 в множество состояний автомата Ã2 , положив β([s1 ]∼ ) = [s2 ]∼ для всех состояний [s1 ]∼ автомата Ã1 . Очевидно, что отображение β биективно. Так как состояние s1 автомата A1 эквивалентно состоянию [s1 ]∼ автомата Ã1 , а состояние s2 автомата A2 эквивалентно состоянию [s2 ]∼ автомата Ã2 , то s1 ∼ s2 . Значит h1 (s1 , x) ∼ h2 (s2 , x) и [h1 (s1 , x)]∼ ∼ [h2 (s2 , x)]∼ при всех входных символах x ∈ X. Поэтому справедливы равенства: β(h̃1 ([s1 ]∼ , x)) = β([h1 (s1 , x)]∼ ) = [h2 (s2 , x)]∼ = h̃2 ([s2 ]∼ , x) = h̃2 (β([s1 ]∼ ), x), f˜1 ([s1 ]∼ , x) = f1 (s1 , x) = f2 (s2 , x) = f˜2 ([s2 ]∼ , x) = f˜2 (β([s1 ]∼ ), x). Таким образом, тройка отображений (εX , β, εY ), где εX , εY — тождественные отображения, заданные на входном и выходном алфавитах соответственно, является внутренним изоморфизмом автоматов Ã1 и Ã2 . 35 Если автоматы Ã1 и Ã2 внутренне изоморфны, то по теореме 1.32, они являются эквивалентными. Так как A1 ∼ Ã1 , а A2 ∼ Ã2 , то автоматы A1 и A2 являются эквивалентными.  Из доказанной теоремы получим важное Следствие 3.20 Минимальные автоматы являются эквивалентными тогда и только тогда, когда они внутренне изоморфны. §3.5 Оценки числа минимальных автоматов. Всюду в этом параграфе будем рассматривать множество всех автоматов с фиксированными алфавитами X, S, Y . Будем считать, что |X| = m, |S| = n, а |Y | = k. Всего таких автоматов будет (nk)mn , так как функцию переходов h : S × X → S можно задать nmn способами, а при каждом задании функции h, функцию выходов f : S × X → Y можно задать k mn способами. Определение 3.21 Автомат A = (X, S, Y, h, f ) назовем явно минимальным, если в нем любые различные состояния s и s′ не являются 1-эквивалентными. Другими словами, в таблице выходов явно минимального автомата нет одинаковых строк. Очевидно, что явно минимальный автомат является минимальным. Утверждение 3.22 При условии n ≤ k m число явно минимальных автоматов равно nmn k m (k m − 1) · · · (k m − n + 1). Доказательство. В явно минимальном автомате функция переходов h произвольна, поэтому существует nmn способов ее задания. Найдем число способов задания функции выходов. В таблице функции выходов f существует k m способов заполнить первую строку. При каждом заполнении первой строки, вторую строку можно заполнить k m − 1 способами. Рассуждая далее аналогично получим, что при каждом выборе заполнения первых n − 1 строк, последнюю строку можно заполнить k m − (n − 1) = k m − n + 1 способами. Значит функцию f можно выбрать k m (k m − 1) · · · (k m − n + 1) способами.  Определение 3.23 Автомат A = (X, S, Y, h, f ) назовем явно сократимым, если в нем существуют различные состояния s и s′ такие, что h(s, x) = h(s′ , x) и f (s, x) = f (s′ , x) для всех x ∈ X. Другими словами, в переходно-выходной таблице явно сократимого автомата есть хотя бы две одинаковые строки. Согласно пункту 3) теоремы 3.3, явно сократимый автомат не является минимальным. Утверждение 3.24 Число автоматов, которые не являются явно сократимыми равно (nk)m ((nk)m − 1) · · · ((nk)m − n + 1). Доказательство. Переходно-выходная таблица автомата, который не является явно сократимым содержит различные строки. Первую строку такой таблицы можно выбрать (nk)m способами. При каждом заполнении первой строки, вторую строку можно заполнить (nk)m −1 способами. Рассуждая далее аналогично получим, что при каждом выборе заполнения первых n−1 строк, последнюю строку можно заполнить (nk)m −(n−1) = (nk)m −n+1 способами. Значит, число автоматов, которые не являются явно сократимыми, равно (nk)m ((nk)m − 1) · · · ((nk)m − n + 1). 36 Теорема 3.25 Число N минимальных автоматов с фиксированными алфавитами X, S, Y , имеющими мощности |X| = m, |S| = n, |Y | = k, оценивается следующим образом: nmn k m (k m − 1) · · · (k m − n + 1) ≤ N ≤ (nk)m ((nk)m − 1) · · · ((nk)m − n + 1). Доказательство. Так как явно минимальный автомат является минимальным, то, по утверждению 3.22, справедливо первое неравенство, а так как каждый минимальный автомат не является явно сократимым, то, по утверждению 3.24, справедливо второе из доказываемых неравенств.  Из теоремы 3.25 следует, что число N минимальных автоматов с алфавитами X, S, Y , состоящими из двух элементов, находится в следующих пределах: 192 ≤ N ≤ 240. ЗАДАЧИ 3.1 Найти разбиение на классы эквивалентных состояний, степень различимости и приведенный вес автомата. Построить его минимальную форму. (а) X S 1 2 3 4 5 6 (в) X S 1 2 3 4 5 6 7 8 9 x1 x2 3, 0 4, 0 2, 1 1, 1 6, 0 5, 1 2, 1 1, 1 4, 1 4, 1 1, 1 5, 1 x1 x2 1, 0 4, 1 1, 0 3, 1 8, 1 8, 1 3, 1 1, 1 3, 0 5, 0 1, 0 2, 0 5, 1 3, 0 8, 0 2, 1 5, 1 6, 0 (б) X S 1 2 3 4 5 6 (г) X S 1 2 3 4 5 6 7 8 9 x1 x2 x3 2, 0 5, 1 1, 0 6, 0 1, 0 5, 1 3, 1 1, 1 2, 0 5, 1 2, 0 4, 1 4, 0 6, 1 6, 1 4, 0 1, 1 2, 1 x1 x2 x3 2, 0 1, 1 1, 1 8, 0 6, 1 8, 0 6, 1 4, 1 7, 0 4, 1 1, 0 6, 0 1, 1 4, 1 9, 1 1, 1 4, 0 9, 1 4, 1 5, 0 5, 0 1, 1 3, 0 6, 1 3, 0 7, 0 7, 1 3.2 (а) Для автомата A найти разбиение на классы эквивалентных состояний. (б) Для каждой из пар {2, 3}, {4, 5}, {1, 2} найти минимальную по длине входную последовательность, различающую ее состояния. X S 1 2 3 4 5 a b 1, 0 1, 0 5, 0 3, 1 2, 1 4, 1 5, 1 1, 1 4, 1 5, 1 37 3.3 В автомате A = ({a, b}, {1, 2, 3, 4}, Y, h, f ) известно, что δ(A) ≥ 3, h(1, a) = 4, h(3, a) = 6 и разбиение на классы 3-эквивалентных состояний имеет вид: {1, 2, 3}, {4}, {5}, {6}. Определите разбиение на классы 2-эквивалентных состояний. 3.4 Покажите, что (а) каждый класс [s]∼k есть объединение некоторых различных классов [s1 ]∼ , . . ., [sr ]∼ ; (б) если k ≤ δ(A), то число классов k-эквивалентных состояний не меньше, чем k + 1; (в) если k ≤ δ(A), то r ≤ µ(A) − k. 3.5 Пусть A — минимальный автомат с n состояниями. Покажите, что среди любых r различных состояний, где r > 1, всегда найдутся n − r + 1-различимые состояния. 3.6 Пусть у регистра сдвига A = R(ψ, φ) для всех z1 , . . ., zn ∈ Z, x ∈ X ψ(z1 , . . . , zn , x) = z1 . Докажите, что (а) автомат A является минимальным; (б) если |Z| > 1, то δ(A) = n; (в) число классов k-эквивалентных состояний в A равно |Z|k , k = 0, . . . , n. 3.7 Найти разбиение на классы k-эквивалентных состояний, k ∈ N и степень различимости следующего автомата Мура: ({0, 1}, {s1 , s2 , . . . , sn }, {0, 1}, h, f ), где h(si , 0) = si+1 для всех i < n, h(sn , 0) = sn , h(si , 1) = si−1 для всех i > 1, h(s1 , 1) = s2 , f (s1 ) = 1, f (si ) = 0 для всех i > 1. 3.8 Пусть разбиение на классы 1-эквивалентных состояний автомата A состоит из r классов. Докажите, что (а) если r = 1, то µ(A) = 1, δ(A) = 0; (б) при k ≤ δ(A) число классов k-эквивалентных состояний не меньше, чем r + k − 1; (в) при k ≤ δ(A) каждый класс k-эквивалентных состояний содержит не более, чем |S| − r − k + 2 состояний; (г) δ(A) ≤ µ(A) − r + 1. 3.9 Проверить, что для регулярного автомата при всех x ∈ X, s, s′ ∈ S выполнены соотношения: (а) s ∼ s′ тогда и только тогда, когда h(s, x) ∼ h(s′ , x); (б) [hx (s)]∼ = {hx (z) : z ∈ [s]∼ }; (в) |[s]∼ | = |[h(s, x)]∼ |. 3.10 (а) Покажите, что разбиение на классы эквивалентных состояний двоичного регистра сдвига A   z1 ψ  z2  6 ? +i x может быть одним из следующих: (1) {(00), (01), (10), (11)}, (2) {(00), (11)}, {(10), (01)}, (3) {(00)}, {(01)}, {(10)}, {(11)}. (б) Докажите, что разбиение (1) получается тогда и только тогда, когда ψ(z1 , z2 , z3 ) одна из функций 0, 1, z1 ⊕ z3 , z1 ⊕ z3 ⊕ 1. (в) Проверьте, что разбиение (2) получается тогда и только тогда, когда для всех z1 , z2 , z3 ∈ {0, 1} ψ(z1 , z2 , z3 ) = ψ(z̄1 , z̄2 , z̄3 ) и ψ отлична от функций из пункта (б). (г) Докажите, что автомат A явно минимален тогда и только тогда, когда все пары (ψ(0, 0, 0), ψ(0, 0, 1)), (ψ(0, 1, 0), ψ(0, 1, 1)), (ψ(1, 0, 1), ψ(1, 0, 0)), (ψ(1, 1, 1), ψ(1, 1, 0)) различны. (д) Приведите пример функций ψ при которых δ(A) = 2, δ(A) = 3. 3.11 Выяснить, какие состояния автономных автоматов A1 и A2 являются эквивалентными. Являются ли эквивалентными автоматы A1 и A2 ? 38  ?  A1 1n  1  ?   3n 2n 1  ?  A2 2n   1n 4n 1 1  ?  4n 3n 1 3.12 Выяснить, эквивалентны ли автоматы? Какие из автоматов являются минимальными? (а) X S 1 2 3 (в) X S 1 2 3 4 a X S 1 2 3 b 3, 0 1, 1 2, 1 1, 1 1, 0 3, 1 a b 2, 0 3, 0 3, 0 2, 0 3, 1 1, 0 2, 1 4, 1 a 2, 0 1, 1 2, 1 3, 1 3, 0 3, 1 X S 1 2 3 4 (б) X S 1 2 3 (г) X S 1 2 3 4 b a b 2, 0 2, 0 4, 0 2, 0 3, 0 4, 1 2, 1 3, 0 a X S 1 2 3 b 3, 1 2, 1 1, 0 3, 1 2, 1 3, 1 a b 4, 1 1, 1 2, 0 1, 1 2, 0 3, 0 4, 0 2, 0 X S 1 2 3 4 a b 3, 0 2, 1 1, 1 2, 1 2, 1 1, 1 a b 3, 0 2, 1 2, 1 3, 0 2, 0 3, 0 1, 0 2, 0 3.13 Определите, какие из трех автоматов являются эквивалентными, какие из них минимальные? (а) X S 1 2 3 4 (б) X S 1 2 3 4 a b 1, 0 3, 0 1, 1 4, 1 2, 1 4, 1 2, 1 3, 1 a b 2, 1 1, 1 2, 1 3, 1 1, 0 1, 1 1, 1 4, 0 X S 1 2 3 4 X S 1 2 3 4 a b 2, 0 2, 0 4, 1 4, 0 4, 1 1, 1 1, 0 2, 1 a b 2, 1 1, 1 2, 1 3, 1 1, 0 1, 1 1, 1 4, 0 X S 1 2 3 4 X S 1 2 3 4 a b 4, 1 2, 1 1, 0 4, 0 3, 1 1, 1 2, 1 3, 1 a b 2, 1 1, 1 4, 0 3, 0 1, 0 1, 1 2, 1 1, 1 3.14 Докажите, что существует сюръективный внутренний гомоморфизм автомата A в автомат с меньшим числом состояний тогда и только тогда, когда автомат A не является минимальным. 3.15 Доказать, что эквивалентные автоматы имеют равные степени различимости. 3.16 Покажите, что в классе автоматов с фиксированными алфавитами X, S, Y существует ровно |S|! автоматов, которые эквивалентны заданному минимальному автомату из этого класса. 39 3.17 Привести пример неминимальных эквивалентных автоматов с одинаковым числом состояний, которые не являются изоморфными. 3.18 Докажите, что если автоматы A1 и A2 — сильно связны и некоторое состояние s1 автомата A1 эквивалентно состоянию s2 автомата A2 , то автоматы эквивалентны. Глава 4. Эксперименты c автоматами. §4.1 Классификация экспериментов. Дерево преемников. Одна из основных задач изучения конечных автоматов состоит в распознавании состояний исследуемого автомата. После того, как состояние распознано, можно определить поведение автомата при всех дальнейших воздействиях на него, и могут быть предприняты шаги по приведению автомата в различные режимы работы, желательные для пользователя. Экспериментом для состояний автомата A называется процесс подачи входных последовательностей на автомат A, наблюдения соответствующих выходных последовательностей и вывода заключений, основанных на этих наблюдениях. Всюду в дальнейшем предполагается, что автомат, над которым проводится эксперимент, является "опечатанным черным ящиком". Экспериментатору доступны лишь вход и выход автомата, а также полностью известна переходно-выходная таблица или граф автомата A. Эксперимент, заключающийся в подаче последовательностей на k экземпляров одного автомата, находящихся в одном и том же начальном состоянии, где k > 1, называется кратным. При этом число k называется кратностью эксперимента. Эксперименты, для которых требуется один экземпляр автомата, будем называть простыми. По своим целям эксперименты делятся на диагностические и установочные. Диагностический эксперимент позволяет определить неизвестное начальное состояние автомата, в котором он находился перед экспериментом. Эксперимент, позволяющий определить конечное состояние автомата, в котором он оказался после проведения эксперимента, называется установочным. Трудоемкость проведения эксперимента определяется его длиной, которая равна общему числу входных символов, прикладываемых в процессе проведения эксперимента. При проведении эксперимента, как правило, интересуются только внешним поведением автомата, поэтому если исследуемый автомат A не минимальный, то всегда можно перейти к минимальной форме à автомата A. Всюду в дальнейшем будем считать, что исходный автомат A = (X, S, Y, h, f ) является минимальным. Множество состояний M ⊂ S, которое, как известно экспериментатору, содержит истинное начальное состояние автомата A, называется множеством допустимых начальных состояний и обозначается M (A). Диагностическая и установочная задачи становятся тривиальными, если |M (A)| = 1. Поэтому, всюду в дальнейшем, будем считать, что |M (A)| ≥ 2. В дальнейшем, нам понадобится понятие мультимножества, обобщающее понятие множества. Под мультимножеством понимается неупорядоченный набор некоторых объектов, которые называются элементами мультимножества. При этом элементы мультимножества не обязательно различны. Мультимножества, как и множества, будем обозначать большими латинскими буквами. Под мощностью мультимножества M будем понимать число |M |, равное количеству элементов из набора M , с учетом повторений этих элементов. 40 Определение 4.1 Если мультимножество M имеет мощность |M | = 1, то оно называется простым. Мультимножество, содержащее хотя бы один повторяющийся элемент, называется кратным. Если мультимножество не содержит различных элементов, то оно называется однородным. Пример 4.2 Пусть заданы мультимножества M1 = {2}, M2 = {1, 1, 2}, M3 = {3, 3, 3}. Тогда |M1 | = 1, |M2 | = 3 и |M3 | = 3. M1 — простое и однородное мультимножество, M2 — кратное мультимножество, не являющееся однородным, а M3 — однородное и кратное. Определим теперь понятие x̄-преемника мультимножества M = {s1 , . . . , sm }, где x̄ — входная последовательность автомата A. Пусть ȳ1 , ȳ2 , . . ., ȳt — все различные последовательности среди выходных последовательностей f¯(s1 , x̄), f¯(s2 , x̄), . . ., f¯(sm , x̄). Представим M в виде объединения мультимножеств M1 , M2 , . . ., Mt , где Mi содержит все состояния s из M (c учетом их повторений) для которых f¯(s, x̄) = ȳi , i ∈ 1, t. Определение 4.3 Неупорядоченный набор, состоящий из мультимножеств N1 , N2 , . . ., Nt называется x̄-преемником мультимножества M = {s1 , . . . , sm }, если Ni получено из Mi заменой каждого элемента s из Mi на элемент h(s, x̄) для всех i ∈ 1, t. Определение 4.4 Набор мультимножеств называется x̄-преемником набора мультимножеств {K1 , K2 , . . . , Kr }, если он состоит из всех x̄-преемников мультимножеств K1 , K2 , . . ., Kr и только их. Пример 4.5 Пусть автомат A задан следующей переходно-выходной таблицей: X S 1 2 3 a b 2, 0 3, 1 3, 1 1, 0 3, 0 2, 1 Найдем a-преемник мультимножества M = {1, 2, 3, 3}. Для этого, с учетом равенств f (1, a) = f (3, a) = 0, f (2, a) = 1, представим M в виде объединения мультимножеств M1 = {1, 3, 3} и M2 = {2} . Тогда a-преемник мультимножества M будет иметь вид {2, 3, 3}, {3}. В свою очередь b-преемником набора {2, 3, 3}, {3} будет следующий набор {1}, {2, 2}, {2}. Этот же набор будет ab-преемником мультимножества M . Укажем некоторые свойства преемников, доказательство которых читателю предлагается провести самостоятельно. Утверждение 4.6 Пусть набор N = {N1 , N2 , . . . , Nt } является x̄-преемником неупорядоченного набора мультимножеств M = {M1 , M2 , . . . , Mr }. Тогда 1) t ≥ r, 2) если K является x̄′ -преемником набора N , то K является x̄x̄′ -преемником набора M . Определим теперь важную конструкцию, называемую деревом преемников автомата A = (X, S, Y, h, f ), построенным для допустимого множества состояний M (A). Дерево преемников есть бесконечная структура, состоящая из вершин, расположенных на последовательных уровнях и ребер. Высшим уровнем считается нулевой уровень, следующий за высшим первый и так далее. Нулевой уровень содержит единственную вершину M (A). Пусть X = {x1 , x2 , . . . , xt }. Тогда вершинами первого уровня считаются t неупорядоченных 41 наборов мультимножеств, которые являются соответственно x1 , x2 , . . ., xt -преемниками множества M (A). Вершины второго уровня представляют из себя соответственно x1 , x2 , . . ., xt -преемники всех вершин первого уровня и так далее. Заметим, что на k-ом уровне дерева преемников содержится ровно tk вершин. Опишем теперь ребра дерева преемников. В дереве преемников присутствует ребро x- M N, помеченное входным символом x ∈ X, тогда и только тогда, когда набор мультимножеств N является x-преемником набора M . Пример 4.7 Пусть автомат A задан следующей переходно-выходной таблицей: X S 1 2 3 4 5 a b 3, 0 4, 0 5, 0 3, 1 3, 1 4, 0 3, 1 5, 0 3, 0 4, 0 Тогда первые четыре уровня дерева преемников, соответствующего автомату A и допустимому множеству состояний M (A) = {1, 2, 3} имеют вид: {1,2,3} a ? b ? {3,4,5} a ? {4,5}{3} b {5}{3,3} ? a {3}{5,5} b ? {5,3,4} ? ? a {4}{5,5} {3,3}{5} a ? b b {3,3}{5} ? {4,5,3} ? a {5,5}{3} b ? {3,4}{5} ? ? a b ? {5,5}{4} {5}{3}{3} {5,3}{4} Заметим, что по пункту 2 утверждения 4.6 вершинами дерева преемников автомата A, соответствующего допустимому множеству состояний M (A), являются все x̄-преемники множества M (A), где x̄ — произвольная последовательность в алфавите X. Неудобство в использовании дерева преемников связано с тем, что оно имеет бесконечное число уровней. В дальнейшем, для построения экспериментов, будем использовать некоторые конечные графы, полученные из дерева преемников. §4.2 Диагностические эксперименты. Рассмотрим простые диагностические эксперименты для автомата A = (X, S, Y, h, f ) и допустимого множества состояний M (A) = {s1 , s2 , . . . , sm }. Определение 4.8 Последовательность x̄ ∈ X l называется диагностической для автомата A и допустимого множества состояний M (A) если f ∗ (si , x̄) ̸= f ∗ (sj , x̄) для всех различных чисел i, j ∈ 1, m. 42 Ясно, что при наличии диагностической последовательности x̄, диагностическую задачу можно решить простым безусловным диагностическим экспериментом. Для этого, например, по переходно-выходной таблице определим выходные последовательности ȳi = f¯(si , x̄) для всех i ∈ 1, m. Эти последовательности являются попарно различными, поэтому после подачи на вход автомата A последовательности x̄ и наблюдения выходной последовательности ȳi , экспериментатор однозначно определит начальное состояние si автомата A. Заметим, что если для автомата A и допустимого множества состояний M (A) не существует диагностической последовательности, то и не существует простого безусловного диагностического эксперимента. Утверждение 4.9 Последовательность x̄ является диагностической последовательностью для автомата A и допустимого множества состояний M (A) тогда и только тогда, когда x̄-преемник множества M (A) состоит только из простых мультимножеств. Доказательство. Пусть M (A) = {s1 , s2 , . . . , sm }. Тогда последовательность x̄ является диагностической последовательностью тогда и только тогда, когда последовательности f ∗ (s1 , x̄), f ∗ (s2 , x̄), . . ., f ∗ (sm , x̄) различны. Это равносильно тому, что x̄-преемник множества M (A) имеет следующий вид {h(s1 , x̄)}, {h(s2 , x̄)}, . . ., {h(sm , x̄)}.  Таким образом, для нахождения диагностической последовательности достаточно найти вершину дерева преемников, которая состоит только из простых мультимножеств. Представляет интерес нахождение кратчайших диагностических последовательностей. Для этого определим важную конструкцию, называемую диагностическим деревом. Диагностическим деревом для автомата A и допустимого множества состояний M (A) называется часть соответствующего дерева преемников, полученная после признания некоторых вершин конечными и удаления из дерева преемников всех преемников этих вершин. В диагностическом дереве вершина M считается конечной в каждом из следующих случаев: 1) M содержит кратное мультимножество, 2) M совпадает с вершиной, которая уже находится в дереве преемников на предшествующем уровне, 3) M состоит только из простых мультимножеств, при этом построение последующих уровней диагностического дерева не производится. Заметим, что так как все вершины дерева преемников были соответствующими преемниками множества M (A), то и все вершины диагностического дерева также будут преемниками множества допустимых состояний. Следующая теорема показывает, что все кратчайшие диагностические последовательности можно найти с использованием диагностического дерева. Теорема 4.10 Последовательность x̄ является кратчайшей диагностической последовательностью для автомата A и допустимого множества состояний M (A) тогда и только тогда, когда в диагностическом дереве x̄-преемник множества M (A) состоит только из простых мультимножеств. Доказательство. Пусть последовательность x̄ — кратчайшая диагностическая последовательность и N является x̄-преемником множества M (A). Покажем, что N является вершиной диагностического дерева, состоящей только из простых мультимножеств. По утверждению 4.9, N состоит только из простых мультимножеств. Осталось показать, что N является вершиной диагностического дерева. Допустим противное, тогда в дереве преемников для автомата A и допустимого множества состояний M (A) оказалась одна из следующих ситуаций: 1) N является преемником вершины, содержащей кратное мультимножество, 43 2) N является преемником вершины, которая уже появлялась на предшествующем уровне, 3) на уровне, предшествующем тому уровню дерева преемников, где содержится вершина N , имеется вершина, состоящая только из простых мультимножеств. Случай 1) невозможен, так как N состоит только из простых мультимножеств. Случаи 2) и 3) невозможны, так как x̄ — кратчайшая диагностическая последовательность. В итоге получим, что N является вершиной диагностического дерева, состоящей только из простых мультимножеств. Пусть теперь в диагностическом дереве вершина N является x̄ преемником множества M (A) и состоит только из простых мультимножеств. Тогда по утверждению 4.9, последовательность x̄ является диагностической для автомата A и множества M (A). Если бы существовала более короткая диагностическая последовательность x̄′ для автомата A и множества M (A), то, по утверждению 4.9, x̄′ -преемник множества M (A) состоял бы только из простых мультимножеств. Тогда весь уровень диагностического дерева, содержащий эту вершину, являлся бы конечным и в диагностическом дереве отсутствовала бы вершина N , что не так.  Пример 4.11 Пусть автомат A такой же как и в примере 4.7 и M (A) = {1, 2, 3}. В этом случае диагностическое дерево будет иметь следующий вид: {1,2,3} a ? b {3,4,5} ? {5}{3,3} a ? {4,5}{3} b ? {5,3,4} ? {3,3}{5} a b ? {3,4}{5} ? a b ? {5}{3}{3} {5,3}{4} В этом дереве aa-преемник и ba-преемник множества M (A) являются конечными вершинами, так как содержат кратное мультимножество. Вершина {5, 3, 4} (ab-преемник множества M (A)) является конечной в силу того, что она уже появлялась на предыдущем уровне как a-преемник множества M (A). Третий уровень диагностического дерева является конечным, так как он содержит вершину, состоящую только из простых мультимножеств. По теореме 4.10, последовательность x̄ = bba является единственной кратчайшей диагностической последовательностью для автомата A и допустимого множества состояний M (A) = {1, 2, 3}. Для проведения эксперимента, сначала выпишем выходные последовательности автомата A при начальных состояниях 1, 2, 3 и занесем данные в таблицу начальное состояние, s 1 2 3 выходная последовательность, f ∗ (s, x̄) 000 101 001 Теперь, подав на вход автомата A последовательность x̄, по соответствующей выходной реакции, однозначно определим начальное состояние автомата A. Следует отметить, что не всегда в автомате A для заданного допустимого множества состояний M (A) существует диагностическая последовательность. 44 Пример 4.12 Пусть автомат A такой же как и в примере 4.7 и M (A) = {1, 4, 5}. В этом случае диагностическое дерево будет иметь следующий вид: {1,4,5} ? a b {3}{3,3} ? {4,3,4} Это дерево не содержит вершины, состоящей только из простых мультимножеств, поэтому для автомата A и данного множества M (A) не существует диагностической последовательности и диагностическая задача неразрешима с использованием простого безусловного эксперимента. Отметим, что не случайно в примере 4.12 допустимое множество состояний содержало более двух состояний. Следующее утверждение показывает, что диагностическая задача для двух допустимых состояний всегда разрешима. Утверждение 4.13 Пусть A = (X, S, Y, h, f ) — минимальный автомат, |S| = n, M (A) ⊂ S, |M (A)| = 2. Тогда существует диагностическая последовательность x̄ ∈ X l для автомата A и допустимого множества состояний M (A) такая, что l ≤ δ(A) ≤ n − 1. Доказательство. Пусть M (A) = {s1 , s2 }. Так как автомат A минимален, то выберем наименьшее число l такое, что состояния s1 и s2 являются l-различимыми. Тогда найдется последовательность x̄ ∈ X l такая, что f ∗ (s1 , x̄) ̸= f ∗ (s2 , x̄), и в этом случае последовательность x̄ является диагностической. Заметим, что состояния s1 и s2 являются δ(A)-различимыми, а значит l ≤ δ(A). Теперь, для доказательства утверждения, остается воспользоваться неравенством δ(A) ≤ n − 1, доказанным в теореме 3.12.  Оценим сверху длину диагностического эксперимента, если, конечно же, он существует. Заметим, что если x̄ — диагностическая последовательность для автомата A и допустимого множества состояний M (A), то любая последовательность вида x̄x̄′ , где x̄′ — произвольная последовательность из входных символов автомата A, также является диагностической. Поэтому, представляет интерес оценка сверху лишь для длины кратчайшего диагностического эксперимента. Теорема 4.14 Пусть A = (X, S, Y, h, f ) — минимальный автомат. Тогда если последовательность x̄ ∈ X l является кратчайшей диагностической последовательностью для автомата A и допустимого множества состояний M (A), то l ≤ (m − 1)nm , где |M (A)| = m, а |S| = n. Доказательство. Оценим высоту диагностического дерева (количество его уровней, кроме нулевого) для автомата A и допустимого множества состояний M (A). Пусть в этом дереве появилась вершина M = {M1 , M2 , . . . , Mr }, где r < m, причем |Mi | = mi для всех i ∈ 1, r. Согласно пункту 1) утверждения 4.6, любой преемник вершины M будет состоять не менее, чем из r мультимножеств. Найдем наибольшую длину t входной последовательности x̄′ такой, что x̄′ -преемник вершины M в диагностическом дереве также состоит ровно из r мультимножеств. Такая вершина имеет вид N = {N1 , N2 , . . . , Nr }, причем |Ni | = mi для всех i ∈ 1, r. Число различных неупорядоченных наборов K = {K1 , K2 , . . . , Kr } с условием |Ki | = mi для всех i ∈ 1, r не превосходит величины nm1 nm2 · · · nmr = nm . Согласно правилу 2) о признании конечными вершин диагностического дерева, получим, что t < nm . 45 Таким образом, преемник вершины M , соответствующий каждой входной последовательности x̄′ длины nm , либо отсутствует в диагностическом дереве, либо содержит количество мультимножеств большее, чем r. При таких рассуждениях число r может принимать значения из множества 1, m − 1, так как вершины, состоящие из m мультимножеств содержат только простые мультимножества и являются конечными в диагностическом дереве. В итоге получим, что l ≤ (m − 1)nm .  Заметим, что оценка, доказанная в теореме 4.14, на самом деле является оценкой высоты диагностического дерева (независимо от существования диагностической последовательности). В частности, из этой теоремы следует, что любое диагностическое дерево имеет конечное число вершин. Таким образом, с использованием диагностического дерева всегда можно ответить на вопрос о существовании диагностических последовательностей, и в случае положительного ответа, построить соответствующий простой безусловный эксперимент. §4.3 Кратные диагностические эксперименты. В предыдущем параграфе было показано, что диагностическая задача не всегда разрешима с использованием простого эксперимента. Рассмотрим теперь задачу нахождения неизвестного начального состояния при условии, что у экспериментатора имеется k экземпляров автомата A = (X, S, Y, h, f ), находящихся в одном и том же начальном состоянии. Такая ситуация возникает, например, когда автомат можно "возвращать"обратно в начальное состояние. Как и прежде будем считать, что автомат A минимален. Определение 4.15 Последовательность x̄ в алфавите X называется k-кратной диагностической последовательностью для автомата A и допустимого множества состояний M (A), если x̄ = x̄1 x̄2 . . . x̄k и справедливо соотношение (f ∗ (s, x̄1 ), f ∗ (s, x̄2 ), . . . , f ∗ (s, x̄k )) ̸= (f ∗ (s′ , x̄1 ), f ∗ (s′ , x̄2 ), . . . , f ∗ (s′ , x̄k )) для всех различных состояний s, s′ из множества M (A). При k = 1 понятие k-кратной диагностической последовательности совпадает с понятием диагностической последовательности. Если для автомата A и допустимого множества состояний M (A) существует k-кратная диагностическая последовательность, то задача нахождения неизвестного начального состояния s решается путем подачи на вход первого экземпляра автомата входной последовательности x̄1 , затем подачей последовательности x̄2 на вход второго экземпляра автомата и так далее. При этом, на последнем шаге, на вход k-ого экземпляра автомата подается входная последовательность x̄k . Тогда, по набору (f ∗ (s, x̄1 ), f ∗ (s, x̄2 ), . . . , f ∗ (s, x̄k )) однозначно будет определено начальное состояние s. Следующая теорема доказывает, что k-кратная диагностическая последовательность всегда существует при подходящем значении k. Теорема 4.16 Для любого минимального автомата A = (X, S, Y, h, f ) и допустимого множества состояний M (A) всегда существует k-кратная диагностическая последовательность x̄ ∈ X l , удовлетворяющая условиям l ≤ (m − 1)δ(A) ≤ (m − 1)(n − 1), где |S| = n, |M (A)| = m. k ≤ m − 1, 46 Доказательство. Укажем процесс построения искомой k-кратной диагностической последовательности x̄. Пусть s1 и s′1 — произвольные различные состояния из множества M (A). Тогда существует входная последовательность x̄1 ∈ X l1 , где l1 ≤ δ(A) такая, что f ∗ (s1 , x̄1 ) ̸= f ∗ (s′1 , x̄1 ). Пусть ȳ11 , ȳ12 , . . ., ȳ1t1 — все различные выходные последовательности среди последовательностей f ∗ (s, x̄1 ), где s ∈ M (A). Разобьем множество M (A) на t1 подмножеств M11 , M12 , . . . M1t1 , где множество M1i при i ∈ 1, t1 состоит из всех состояний s ∈ M (A) для которых f ∗ (s, x̄1 ) = ȳ1i . Если все множества M11 , M12 , . . . M1t1 являются одноэлементными, то x̄1 будет диагностической последовательностью кратности 1. В противном случае, выберем последовательность x̄2 ∈ X l2 , где l2 ≤ δ(A), которая различает два разных состояния, принадлежащих одному из множеств M1i . Разобьем множество M1i на подмножества так, что произвольные состояния s2 и s′2 из множества M1i будут принадлежать одному подмножеству тогда и только тогда, когда f ∗ (s2 , x̄2 ) = f ∗ (s′2 , x̄2 ). В итоге, получим новое разбиение M21 , M22 , . . ., M2t2 множества M (A), которое будет измельчением предыдущего разбиения и, в частности, t2 > t1 . Если каждое из множеств M2i является одноэлементным, то последовательность x̄1 x̄2 будет 2-кратной диагностической последовательностью. В противном случае, выбираем последовательность x̄3 ∈ X l3 такую, что l3 ≤ δ(A) и которая различает какие-либо два различных состояния, принадлежащих одному из множеств M2i . Аналогично вышеизложенному, в зависимости от реакций на последовательность x̄3 , построим разбиение M31 , M32 , . . ., M3t3 множества M (A). При этом, будет выполнено неравенство t3 > t2 . Будем продолжать процесс построения разбиений до некоторого шага k, когда будет выбрана входная последовательность x̄k ∈ X lk , где lk ≤ δ(A) и построено соответствующее разбиение Mk1 , Mk2 , . . ., Mktk множества M (A), состоящее только из одноэлементных множеств. По построению, будут справедливы соотношения m = tk > . . . > t2 > t1 . Последовательность x̄1 x̄2 . . . x̄k будет диагностической последовательностью и при этом k ≤ m − 1. Для длины l = l1 + l2 + . . . + lk этой последовательности, согласно теореме 3.12, будут справедливы оценки: l ≤ kδ(A) ≤ (m − 1)(n − 1). Теорема 4.16 показывает, что с использованием m − 1 копий автомата всегда можно решить диагностическую задачу. Кроме того, в доказательстве теоремы 4.16 изложен метод построения соответствующей диагностической последовательности. Рассмотрим пример на применение этого метода. Пример 4.17 Пусть автомат A = (X, S, Y, h, f ) такой же, как в примере 4.7 и M (A) = {1, 2, 3, 4, 5}. Согласно примеру 4.12, для множества состояний {1, 4, 5} не существует простого безусловного диагностического эксперимента, а значит и для выбранного множества состояний не существует 1-кратной диагностической последовательности. Построим кратную диагностическую последовательность. Выберем последовательность x̄1 = a, различающую состояния 1 и 4. Тогда f (1, a) = f (2, a) = f (3, a) = 0, а f (4, a) = f (5, a) = 1 и получим разбиение множества M (A) на классы M11 = {1, 2, 3}, M12 = {4, 5}. Возьмем последовательность x̄2 = b, которая различает состояния 1 и 2, принадлежащие множеству M11 . Тогда f (1, b) = f (3, b) = 0, а f (2, b) = 1 и получим разбиение множества M (A) на подмножества M21 = {1, 3}, M22 = {2}, M23 = {4, 5}. Выберем последовательность, различающую состояния 1 и 3. Такой последовательностью является, например, последовательность x̄3 = aa. При этом f ∗ (1, aa) = 00, а f ∗ (3, aa) = 01. Получим следующее разбиение множества M (A): M31 = {1}, M32 = {3}, M33 = {2}, M34 = {4, 5}. Осталось различить состояния 4 и 5. Для этого выберем последовательность x̄4 = ba для которой f ∗ (4, ba) = 00, а f ∗ (5, ba) = 01. Тогда получим разбиение M41 = {1}, M42 = {3}, M43 = {2}, M44 = {4}, M45 = {5}. В итоге, автомат A имеет 4-кратную диагностическую 47 последовательность x̄ = x̄1 x̄2 x̄3 x̄4 и для проведения кратного эксперимента понадобится 4 копии автомата A, которые обозначим A1 , A2 , A3 , A4 . Для наглядности, изобразим, так называемое, дерево кратного эксперимента: A1 ? A2 ? A3 00 ? {1} 1 ? {1,2,3}, x̄2 = b 1 ? {1,3}, x̄3 = aa {2} 01 {1,2,3,4,5}, x̄1 = a A4 ? {4} 00 {4,5}, x̄4 = ba 01 ? {5} ? {3} Теперь, подав на вход автомата Ai входную последовательность x̄i для всех i ∈ 1, 4 и получив соответствующие выходные последовательности, однозначно определим начальное состояние автомата A. Если, например, на выходе автомата A1 получили 1, а на выходе автомата A4 последовательность 00, то истинное начальное состояние автомата A было 4. Итак, для автомата A построен безусловный диагностический эксперимент кратности 4 и длины 6. §4.4 Установочные эксперименты. Рассмотрим задачу определения финального состояния автомата A = (X, S, Y, h, f ), находящегося в неизвестном начальном состоянии. Как и прежде, будем считать, что автомат A минимален. Определение 4.18 Последовательность x̄ ∈ X l называется установочной последовательностью для автомата A и допустимого множества состояний M (A), если для любых различных состояний s1 , s2 ∈ M (A) таких, что h(s1 , x̄) ̸= h(s2 , x̄) выполнено условие f ∗ (s1 , x̄) ̸= f ∗ (s2 , x̄). Другими словами, если x̄ установочная последовательность для автомата A и допустимого множества состояний M (A), то разным финальным состояниям будут соответствовать разные выходные последовательности. Таким образом, подав на вход автомата A, находящегося в неизвестном начальном состоянии s установочную последовательность x̄, по соответствующей выходной последовательности f ∗ (s, x̄) можно однозначно определить финальное состояние h(s, x̄) автомата A. Заметим, что любая диагностическая последовательность для автомата A и допустимого множества состояний M (A) также является и установочной. Это свидетельствует о том, что при существовании простого диагностического эксперимента всегда существует и простой установочный эксперимент. Напомним, что мультимножество называется однородным, если оно не содержит различных элементов. Непосредственно из определений получим Утверждение 4.19 Пусть A — минимальный автомат. Тогда x̄ — установочная последовательность для автомата A и допустимого множества состояний M (A) тогда и только тогда, когда x̄-преемник множества M (A) состоит только из однородных мультимножеств. Для нахождения кратчайших по длине установочных последовательностей в автомате A нам понадобится конструкция, так называемого, установочного дерева. Установочным деревом для автомата A и допустимого множества состояний M (A) называется 48 часть соответствующего дерева преемников, полученная после признания некоторых вершин конечными и удаления из дерева преемников всех преемников этих вершин. Вершина M считается конечной в любом из следующих двух случаев: 1) M совпадает с вершиной, которая уже находится в дереве преемников на предшествующем уровне, 2) M состоит только из однородных мультимножеств, при этом построение всех последующих уровней установочного дерева заканчивается. Заметим, что так как все вершины дерева преемников были соответствующими преемниками множества M (A), то и все вершины установочного дерева также будут преемниками множества допустимых состояний. Теорема 4.20 Пусть A — минимальный автомат. Тогда x̄ является кратчайшей установочной последовательностью для автомата A и допустимого множества состояний M (A) тогда и только тогда, когда x̄-преемник множества M (A) в установочном дереве состоит только из однородных мультимножеств. Доказательство. Пусть последовательность x̄ является кратчайшей установочной последовательностью для автомата A и допустимого множества состояний M (A), а N является x̄-преемником множества M (A). Согласно утверждению 4.19, N состоит только из однородных мультимножеств. С использованием утверждения 4.19 и того, что x̄ — кратчайшая установочная последовательность, получим, что в дереве преемников на уровнях, предшествующих уровню вершины N , нет вершин, состоящих только из однородных мультимножеств. В частности, там нет вершины N . Значит N является вершиной установочного дерева и состоит только из однородных мультимножеств. Пусть теперь x̄-преемник N множества M (A) в установочном дереве состоит только из однородных мультимножеств. Тогда, по утверждению 4.19, x̄ — установочная последовательность. Покажем, что она кратчайшая. Если бы существовала более короткая установочная последовательность для автомата A и допустимого множества состояний M (A), то тогда, по утверждению 4.19, в установочном дереве на уровне, предшествующем уровню вершины N находилась бы вершина, состоящая только из однородных мультимножеств. Значит по правилу 2) построения установочного дерева получим, что рассматриваемая вершина N в нем не существует, что противоречит условию. Таким образом, x̄ является кратчайшей установочной последовательностью.  Приведем теперь пример на нахождение установочной последовательности с использованием установочного дерева и на построение соответствующего безусловного установочного эксперимента. Пример 4.21 Пусть автомат A такой же, как в примере 4.7 и M (A) = {1, 2, 3}. В этом случае установочное дерево будет иметь следующий вид: {1,2,3} a ? b {3,4,5} ? {5}{3,3} a ? {4,5}{3} b ? {5,3,4} ? {3,3}{5} a b ? {3,4}{5} В этом дереве aa-преемник и ba-преемник множества M (A) являются конечными вершинами, так как состоят только из однородных мультимножеств. Само установочное дерево, в отличии от диагностического дерева (см. пример 4.11), содержит 3 уровня. Согласно 49 теореме 4.20, последовательности aa, ba и только они являются кратчайшими установочными последовательностями для автомата A и допустимого множества состояний M (A). Для проведения установочного эксперимента с использованием, например, установочной последовательности x̄ = ba, построим следующую таблицу: начальное состояние, s 1 2 3 выходная реакция, f ∗ (s, x̄) 01 10 01 финальное состояние, h(s, x̄) 3 5 3 Из таблицы видно, что если после подачи последовательности x̄ наблюдается выход 01, то финальное состояние будет 3, а если наблюдается последовательность 10, то финальное состояние будет 5. Следующая теорема не только указывает оценку длины кратчайшей установочной последовательности, но и показывает, что, в отличии от диагностической задачи, установочная задача всегда разрешима с использованием простого безусловного эксперимента. Теорема 4.22 Пусть A = (X, S, Y, h, f ) — минимальный автомат. Тогда для автомата A и допустимого множества состояний M (A) всегда существует установочная последовательность x̄ ∈ X l такая, что l ≤ (m − 1)δ(A) ≤ (m − 1)(n − 1), где |S| = n, а |M (A)| = m. Доказательство. Предложим алгоритм построения искомой установочной последовательности. Сначала выберем последовательность x̄1 ∈ X l1 , которая различает какие-либо два состояния из множества N1 = M (A). Такая последовательность существует в силу минимальности автомата A и можно считать, что l1 ≤ δ(A). Пусть N2 является x̄1 преемником множества N1 . Набор N2 будет содержать, по крайней мере, два мультимножества. Если N2 состоит только из однородных мультимножеств, то искомой установочной последовательностью является x̄1 . В противном случае, выбираем последовательность x̄2 ∈ X l2 длины l2 ≤ δ(A), которая различает некоторые различные состояния, содержащиеся в одном мультимножестве из набора N2 . Пусть N3 является x̄2 -преемником множества N2 . Набор N3 будет содержать, по меньшей мере, три мультимножества. Если N3 состоит только из однородных мультимножеств, то искомой установочной последовательностью является последовательность x̄1 x̄2 длины l1 + l2 ≤ 2δ(A). В противном случае, аналогично вышеизложенному выбираем последовательность x̄3 и так далее. В итоге, через k шагов, где k ≤ m − 1 будут построены последовательности x̄1 , x̄2 , . . ., x̄k , каждая из которых имеет длину не больше δ(A) такие, что x̄1 x̄2 . . . x̄k -преемник множества M (A) состоит только из однородных мультимножеств. Тогда, по утверждению 4.19, последовательность x̄ = x̄1 x̄2 . . . x̄k является установочной последовательностью, а c использованием теоремы 3.12, для ее длины l получим соотношения l ≤ kδ(A) ≤ (m − 1)(n − 1).  В доказательстве теоремы 4.22, на самом деле, изложен еще один метод нахождения установочной последовательности. Этот метод позволяет достаточно просто найти некоторую установочную последовательность, но которая не обязательно будет кратчайшей. 50 Пример 4.23 Рассмотрим автомат A, заданный следующей переходно-выходной таблицей: X a b c S 1 2, 0 1, 1 1, 1 2 1, 1 1, 0 3, 0 3 4, 1 2, 0 3, 0 4 1, 0 5, 1 4, 1 5 3, 0 5, 1 3, 1 Построим установочную последовательность для автомата A и допустимого множества состояний M (A) = 1, 5. Начнем с выбора последовательности x̄1 = a, которая различает состояния 1 и 2. Тогда x̄1 -преемник множества N1 = {1, 2, 3, 4, 5} будет иметь вид N2 = {{1, 2, 3}, {1, 4}}. Выберем теперь, например, последовательность x̄2 = b, различающую состояния 1 и 2, принадлежащие в наборе N2 одному мультимножеству. Тогда x̄2 -преемник набора N2 будет следующим: N3 = {{1}, {1, 2}, {1, 5}}. Теперь выберем последовательность x̄3 = a, различающую состояния 1 и 2. Пусть N4 является x̄3 - преемником набора N3 . В этом случае N4 = {{2}, {2}, {1}, {2, 3}} и выбираем последовательность x̄4 = ba, различающую состояния 2 и 3. Тогда x̄4 -преемником набора N4 будет набор N5 = {{2}, {2}, {2}, {2}, {1}}, состоящий только из однородных мультимножеств. Искомой установочной последовательностью является последовательность x̄ = x̄1 x̄2 x̄3 x̄4 = ababa. Проведенные рассуждения удобнее всего записывать с использованием следующей таблицы: шаг алгоритма, i 1 2 3 4 5 Ni x̄i {1, 2, 3, 4, 5} {1, 2, 3}{1, 4} {1}{1, 2}{1, 5} {2}{2}{1}{2, 3} {2}{2}{2}{2}{1} a b a ba Таким образом, по найденной установочной последовательности, можно построить установочный эксперимент длины 5. Читателю предлагается самостоятельно проверить, что для данного автомата A и допустимого множества состояний M (A) = {1, 2, 3, 4, 5} кратчайшая установочная последовательность имеет длину 3 и для ее нахождения необходимо построить достаточно громоздкое установочное дерево. Поэтому, в данном случае, удобнее решить установочную задачу с использованием алгоритма из теоремы 4.22. Результаты этого параграфа показывают, что для любого минимального автомата и любого допустимого множества состояний всегда можно решить установочную задачу с использованием простого эксперимента. В связи с этим, всегда существует возможность привести автомат к предсказуемому виду, когда после проведения эксперимента становится известным состояние, в котором оказался автомат. §4.5 Эксперименты по распознаванию автоматов. В предыдущих параграфах основное допущение состояло в том, что исходный автомат полностью задан, например, с использованием переходно-выходной таблицы. Неопределенность заключалась лишь в том, что было неизвестно начальное состояние автомата. В этой главе будет рассматриваться более широкая задача распознавания неизвестного автомата A, принадлежащего некоторому множеству автоматов {A1 , A2 , . . . , AN }. Сами 51 автоматы A1 , . . ., AN считаются полностью известными экспериментатору. Исследователь имеет дело с произвольным автоматом A ∈ {A1 , A2 , . . . , AN }, который находится в произвольном неизвестном начальном состоянии. Экспериментом по распознаванию автомата A называется процесс подачи на вход автомата A некоторых последовательностей, наблюдения соответствующих выходов и определения, на основе этих данных, с каким из указанных автоматов совпадает автомат A. Всюду в дальнейшем, будем считать, что каждый автомат Ai , где i ∈ 1, N является минимальным. Это предположение не вносит существенных ограничений, так как если окажется, что какой-либо из автоматов Ai не является минимальным, то его всегда можно заменить на минимальную форму Ãi . Пусть Ai = (Xi , Si , Yi , hi , fi ) для всех i ∈ 1, N . Всюду в дальнейшем, будем считать, что X1 = X2 = . . . = XN , а множества состояний Si и Sj не содержат одинаковых элементов при всех i, j ∈ 1, N , i ̸= j. В этом случае, множество автоматов {A1 , A2 , . . . , AN } будем называть классом автоматов. Определение 4.24 Последовательность x̄ ∈ X l называется распознающей последова′′ тельностью для класса автоматов {A1 , A2 , . . . , AN } если fi∗ (s′ , x̄) ̸= fj∗ (s , x̄) для всех ′′ s′ ∈ Si , s ∈ Sj и всех i, j ∈ 1, N таких, что i ̸= j. Другими словами, x̄ — распознающая последовательность, если по реакции автомата A на эту последовательность, сам автомат определяется однозначно. Определение 4.25 Класс автоматов {A1 , A2 , . . . , AN } назовем исключительным классом ′′ если любые состояния s′ ∈ Si и s ∈ Sj являются неэквивалентными при всех i, j ∈ 1, N , i ̸= j. Критерий распознаваемости автомата устанавливает следующий факт. Теорема 4.26 Пусть Ai = (X, Si , Yi , hi , fi ) — минимальный автомат для всех i ∈ 1, N и K = {A1 , A2 , . . . , AN }. Тогда для класса K существует распознающая последовательность тогда и только тогда, когда класс K является исключительным. Доказательство. Пусть x̄ — распознающая последовательность для класса K. Тогда ес′′ ли s′ ∈ Si и s ∈ Sj , где i, j ∈ 1, N , i ̸= j, то будут справедливы соотношения fi∗ (s′ , x̄) ̸= ′′ ′′ fj∗ (s , x̄), а значит состояния s′ и s неэквивалентны. В силу произвольности выбора со′′ стояний s′ и s , получим, что класс K является исключительным. Пусть теперь класс K — исключительный класс автоматов. Покажем, что для класса K существует распознающая последовательность. Рассмотрим автомат  = A1 + A2 + . . . + AN . Так как каждый из автоматов A1 , A2 , . . ., AN минимален и класс K является исключительным, то автомат  минимален. Пусть x̄ — установочная последовательность для автомата  и допустимого множества состояний S1 ∪ S2 ∪ . . . ∪ SN . Такая последовательность существует согласно теореме 4.22. Покажем, что x̄ будет различающей после′′ довательностью. Рассмотрим произвольные состояния s′ ∈ Si и s ∈ Sj , где i, j ∈ 1, N , ′′ i ̸= j. Если справедливо соотношение fi∗ (s′ , x̄) ̸= fj∗ (s , x̄), то доказывать нечего. Пусть ′′ fi∗ (s′ , x̄) = fj∗ (s , x̄). Тогда, по определению установочной последовательности, должно ′′ быть выполнено равенство hi (s′ , x̄) = hj (s , x̄), что невозможно так как множества Si и Sj не пересекаются. Таким образом, x̄ является искомой различающей последовательностью.  Следующая теорема описывает параметры эксперимента, распознающего автомат. 52 Теорема 4.27 Пусть A принадлежит исключительному классу K = {A1 , A2 , . . . , AN }, состоящему из минимальных автоматов Ai = (X, Si , Yi , hi , fi ), у которых |Si | = ni для всех i ∈ 1, N и n1 ≥ n2 ≥ . . . ≥ nN . Тогда автомат A может быть распознан простым безусловным экспериментом длины l, где (( N ) ) ∑ l ≤ (n1 + n2 − 1) ni − 1 . i=1 Доказательство. Класс K является исключительным, поэтому, согласно теореме 4.26, для него существует распознающая последовательность x̄ ∈ X l . Кроме того, можно считать, что x̄ — установочная последовательность для автомата Â∑ = A1 + . . . + AN и допустимого множества состояний S1 ∪ . . . ∪ SN , имеющего мощность N i=1 ni . По теореме 4.22, ∑N последовательность x̄ можно выбрать так, что l ≤ (( i=1 ni ) − 1)δ(Â). Теперь для доказательства теоремы остается показать, что δ(Â) ≤ n1 + n2 − 1. Если различные состояния s′ ′′ и s автомата  выбраны из одного множества Si , где i ∈ 1, N , то согласно теореме 3.12, ′′ примененной к минимальному автомату Ai , получим, что состояния s′ и s различимы ′′ последовательностью длины ni − 1 < n1 + n2 − 1. Если состояния s′ и s выбраны из различных множеств Si и Sj , где i, j ∈ 1, N , i ̸= j, то по теореме 3.12, примененной к ′′ минимальному автомату Ai + Aj , получим, что состояния s′ и s различимы последовательностью длины ni + nj − 1 ≤ n1 + n2 − 1. В итоге, любые два различные состояния автомата  будут различимы последовательностью длины не больше, чем n1 + n2 − 1, а значит δ(Â) ≤ n1 + n2 − 1.  Непосредственно из теоремы 4.27 получим следствие. Следствие 4.28 Пусть A принадлежит исключительному классу {A1 , A2 , . . . , AN }, где каждый автомат Ai содержит не более n состояний. Тогда автомат A может быть распознан простым безусловным экспериментом длины l, где l ≤ (2n − 1)(N n − 1). Пример 4.29 Пусть известно, что автомат A принадлежит классу K = {A1 , A2 }. Требуется распознать автомат A, если автоматы A1 и A2 заданы следующими переходновыходными таблицами: A1 X S 1 2 3 a b 2, 0 3, 1 1, 1 2, 1 1, 0 1, 1 A2 X S 1 2 3 a b 1, 1 3, 1 2, 1 2, 1 2, 0 1, 1 Проверим сначала является ли класс K исключительным. Переобозначим состояния автомата A2 , заменив состояние s на состояние s′ для всех s ∈ {1, 2, 3} и рассмотрим автомат  = A1 + A2 . Несложно проверить, что разбиение автомата  на классы 1-эквивалентности имеет вид {1, 3, 3′ }, {2, 1′ , 2′ }, а разбиение на классы 2-эквивалентных состояний следующее: {1}, {3}, {3′ }, {2}, {1′ }, {2′ }. Таким образом, K является исключительным классом и задача распознавания автомата A разрешима. Для этого, согласно доказательству теоремы 4.26, достаточно построить установочную последовательность для автомата  и M (Â) = {1, 2, 3, 1′ , 2′ , 3′ }. Воспользуемся алгоритмом из доказательства 53 теоремы 4.22. Представим рассуждения в виде следующей таблицы: шаг алгоритма, i 1 2 3 4 5 Ni x̄i {1, 2, 3, 1′ , 2′ , 3′ } {1, 2, 2′ }{1, 1′ , 2′ } {2}{1, 2′ }{2}{1′ , 2′ } {1}{2}{2′ }{1}{1′ , 2′ } {1}{1}{2′ }{1}{2′ }{2′ } a a a ba Искомой установочной последовательностью является последовательность x̄ = aaaba. Построим теперь таблицу реакций для автомата  при различных начальных состояниях и соответствующие конечные состояния автомата Â. начальное состояние, s 1 2 3 1′ 2′ 3′ выходная реакция, f ∗ (s, x̄) 01011 10110 00110 11110 11111 01111 финальное состояние, h(s, x̄) 1 1 1 2′ 2′ 2′ Подадим теперь на вход автомата A последовательность x̄ и по соответствующей выходной реакции, с использованием построенной таблицы реакций, однозначно определим финальное состояние автомата Â. Тогда, по конечному состоянию однозначно определим каким из автоматов был автомат A. Например, если на выходе получим последовательность 11110, то A = A2 и после подачи входа x̄, автомат оказался в финальном состоянии 2′ . Таким образом, построен эксперимент длины 5, распознающий автомат A. Заметим, что, на самом деле, последовательность x̄ является диагностической последовательностью для автомата  и распознает не только автомат A, но и начальное состояние, в котором он находился перед началом эксперимента. §4.6 Тестирование автоматов. Значительный практический интерес представляет задача тестирования автомата, то есть проверка правильности его функционирования или распознавания повреждений, вызвавших ту или иную неисправность. Задача о тестировании автомата может быть сформулирована следующим образом. Пусть дан автомат A0 = (X, S0 , Y, h0 , f0 ), который будем называть исправным. Считается, что заранее известен список возможных неисправностей автомата A0 , которым однозначно соответствуют неисправные автоматы Ai = (X, Si , Y, hi , fi ), где i ∈ 1, N − 1. Требуется распознать автомат A, принадлежащий классу автоматов {A0 , A1 , . . . , AN −1 }. В общем случае, рассматриваются два варианта задачи о тестировании автомата. Первый вариант — это задача диагноза, заключающаяся в том, что необходимо выяснить исправен автомат A или нет, и если неисправен, то определить эту неисправность. Для ее решения требуется построить эксперимент, который распознает автомат A из класса K = {A0 , A1 , . . . , AN −1 }. Такой эксперимент называется еще диагностическим тестом. Если класс K является исключительным классом автоматов, то согласно следствию 4.28, задача 54 диагноза всегда разрешима с использованием простого безусловного эксперимента длины l, не превосходящей число (2n − 1)(N n − 1), где n = maxi∈0,N −1 |Si |. Второй вариант задачи о тестировании автоматов — это задача контроля автомата. Она заключается в том, что необходимо построить эксперимент, дающий ответ на вопрос исправен автомат A или нет? При этом, в случае отрицательного ответа, не требуется определять происшедшую неисправность. Эксперимент, с использованием которого решается задача тестирования автомата, называют еще контрольным тестом. Таким образом, если автомат A′ является минимальной формой автомата A1 + . . . + AN −1 , то контрольный тест является экспериментом по распознаванию автомата из класса K ′ = {A0 , A′ }. Согласно теореме 4.27, если класс K ′ является исключительным, то задача контроля будет разрешима с использованием безусловного эксперимента. Пусть n = maxi∈0,N −1 |Si |. Тогда любые состояния автоматов A0 и A′ являются 2n − 1-различимыми и, согласно теореме 4.27, для длины l контрольного теста будет справедлива оценка l ≤ (2n − 1)(N n − 1). Кроме того, отметим, что любой диагностический тест является также и контрольным тестом. Основной трудностью при решении задачи тестирования автоматов является точное описание класса автоматов, соответствующих различным неисправностям автомата A0 . Рассмотрим пример решения задачи тестирования автоматов без памяти. В этом случае Ai = (X, Si , Y, hi , fi ), где |Si | = 1 для всех i ∈ 0, N − 1. Для таких автоматов используется обозначение Ai = (X, Y, fi ), и в этом случае каждый из автоматов однозначно сопоставляется отображению fi : X → Y , где i ∈ 0, N − 1. Как и ранее, считаем автомат A0 исправным, а автоматы A1 , . . ., AN −1 соответствующими неисправностям автомата A0 . Определим множества Xij = {x ∈ X : fi (x) ̸= fj (x)} для всех i, j ∈ 0, N − 1, причем i < j. Согласно теореме 4.26, для решения задачи диагноза достаточно построить распознающую последовательность x̄ (диагностический тест) для класса автоматов K = {A0 , A1 , . . . , AN −1 } и такая последовательность существует тогда и только тогда, когда класс K является исключительным, то есть отображения f0 , f1 , . . ., fN −1 являются попарно различными. Это равносильно тому, что множества Xij являются непустыми при всех 0 ≤ i < j ≤ N − 1. Следующее утверждение указывает правило построения диагностического теста. Утверждение 4.30 Пусть класс K = {A0 , A1 , . . . , AN −1 } состоит из автоматов Ai = (X, Y, fi ) для всех i ∈ 0, N − 1. Тогда последовательность x̄ = x1 x2 . . . xl является диагностическим тестом для класса K тогда и только тогда, когда {x1 , x2 , . . . , xl } ∩ Xij ̸= ∅ (4.1) для всех 0 ≤ i < j ≤ N − 1. Доказательство. Последовательность x̄ = x1 x2 . . . xl является диагностическим тестом тогда и только тогда, когда для всех 0 ≤ i < j ≤ N − 1 будет выполнено неравенство fi∗ (x̄) = fi (x1 ) . . . fi (xl ) ̸= fj∗ (x̄) = fj (x1 ) . . . fj (xl ). Это соотношение выполнено тогда и только тогда, когда fi (xr ) ̸= fj (xr ) при некотором значении r ∈ 1, l, а это равносильно тому, что xr ∈ Xij .  Из утверждения 4.30 следует, что для построения кратчайшего диагностического теста потребуется найти наименьшее число l элементов из множества X, удовлетворяющих условию (4.1) для всех 0 ≤ i < j ≤ N − 1. 55 Рассмотрим теперь задачу контроля для класса K = {A0 , A1 , . . . , AN −1 }. По теореме 4.26, для решения задачи контроля достаточно построить распознающую последовательность x̄ (контрольный тест) для класса автоматов K ′ = {A0 , A′ }, где A′ — минимальная форма автомата A1 + . . . + AN −1 . Такая последовательность существует тогда и только тогда, когда класс K ′ является исключительным, то есть отображения f0 и fj различны при всех j ∈ 1, N − 1. Это равносильно тому, что множества X0j являются непустыми при всех 1 ≤ j ≤ N − 1. Следующее утверждение доказывается аналогично утверждению 4.30, что читателю предлагается проверить самостоятельно. Утверждение 4.31 Пусть класс K = {A0 , A1 , . . . , AN −1 } состоит из автоматов Ai = (X, Y, fi ) для всех i ∈ 0, N − 1. Тогда последовательность x̄ = x1 x2 . . . xl является контрольным тестом для класса K тогда и только тогда, когда {x1 , x2 , . . . , xl } ∩ X0j ̸= ∅ (4.2) для всех 1 ≤ j ≤ N − 1. Из утверждения 4.31 следует, что для построения кратчайшего контрольного теста потребуется найти наименьшее число l элементов из множества X, удовлетворяющих условию (4.2). Пример 4.32 Пусть X = {0, 1}3 , Y = {0, 1}, Ai = (X, Y, fi ) и булевы функции fi (z1 , z2 , z3 ) заданы таблицами значений, где i ∈ 0, 3. Построим кратчайшие контрольный и диагностический тесты для класса K = {A0 , A1 , A2 , A3 }. z1 1 1 1 1 z2 1 1 1 1 z3 1 1 1 1 f0 1 1 1 1 f1 1 1 1 1 f2 1 1 1 1 1 f3 1 1 1 1 Согласно утверждению 4.31, рассмотрим множества X01 = {001, 100}, X02 = {000, 101, 111}, X03 = {000, 010, 101, 111}. Эти множества не содержат элемента, который был бы общим для них всех, поэтому кратчайший контрольный тест имеет длину большую, чем 1. Последовательность 001, 000, состоящая из двух входных символов, удовлетворяет соотношениям (4.2), а значит является кратчайшим контрольным тестом. Построим теперь кратчайший диагностический тест. Согласно утверждению 4.30, рассмотрим множества X12 = {000, 001, 100, 101, 111}, X13 = {000, 001, 010, 100, 101, 111}, X23 = {010}. Так как кратчайший контрольный тест имел длину 2, то кратчайший диагностический тест будет иметь длину не меньше, чем 2. Выясним есть ли в данном случае диагностический тест длины 2? Такой тест, согласно соотношениям (4.1), обязательно содержит символы из множества X01 и множества X23 , поэтому с точностью до замены местами двух входных символов, тест будет следующим: 001, 010 или 100, 010. Непосредственной проверкой соотношений (4.1), убеждаемся, что каждая из этих последовательностей не является диагностическим тестом. В то же время, последовательность 001, 010, 111, состоящая из трех входных символов, является диагностическим тестом. Значит, эта последовательность является кратчайшим диагностическим тестом. 56 ЗАДАЧИ 4.1 1) Постройте первые четыре уровня дерева преемников для автомата A и M (A) = {1, 2, 3}. 2) Укажите все диагностические (установочные) последовательности длины 3. 3) Постройте диагностическое (установочное) дерево и найдите все кратчайшие диагностические (установочные) последовательности. (a) X S 1 2 3 4 5 a b 3, 0 4, 0 5, 0 3, 1 3, 1 4, 0 3, 1 5, 0 3, 0 4, 0 X S 1 2 3 4 5 (б) a b 2, 0 1, 1 5, 1 4, 0 2, 0 2, 1 3, 1 1, 0 3, 1 4, 0 4.2 Перечислить все кратчайшие диагностические (установочные) последовательности для автомата A и допустимого множества состояний M (A) = {1, 2, 3}. (а) (в) X S 1 2 3 4 X S 1 2 3 4 5 a b 3, 0 2, 0 4, 0 1, 1 2, 1 1, 1 1, 1 2, 0 a b 1, 0 1, 0 5, 0 3, 1 2, 1 4, 1 5, 1 1, 1 4, 1 5, 1 X S 1 2 3 4 (б) (г) X S 1 2 3 4 5 a b 3, 0 2, 1 4, 0 2, 1 4, 1 1, 0 4, 1 3, 0 a b c 2, 1 1, 0 4, 1 1, 0 3, 0 2, 0 2, 1 2, 0 5, 1 5, 1 3, 0 2, 1 3, 0 4, 1 3, 1 4.3 Пусть автомат A задан переходно-выходной таблицей и M (A) = {1, 2, 3, 4}. Построить все кратчайшие диагностические (установочные) последовательности. (а) X S 1 2 3 4 a b 1, 0 1, 0 3, 0 3, 1 3, 1 1, 0 4, 1 3, 0 (б) X S 1 2 3 4 a b c 1, 0 3, 0 2, 0 4, 0 1, 0 2, 0 4, 0 3, 0 1, 0 2, 0 3, 0 4, 1 4.4 Пусть автомат A задан переходно-выходной таблицей и M (A) = {1, . . . , 8}. Построить 57 все кратчайшие диагностические (установочные) последовательности. (а) X S 1 2 3 4 5 6 7 8 a b 2, 0 3, 0 8, 0 5, 0 6, 1 7, 1 4, 1 1, 1 3, 0 2, 0 5, 0 8, 0 7, 1 6, 1 1, 1 4, 1 X S 1 2 3 4 5 6 7 8 (б) a b 1, 1 2, 1 3, 1 4, 1 5, 1 8, 1 7, 0 3, 0 8, 1 7, 0 6, 0 6, 1 5, 0 7, 0 7, 1 7, 1 4.5 Пусть автомат над полем GF (2) имеет следующий вид: - i * 6  ? +i ?  + i  ? +i где ∗ ∈ {+, ·}. Без построения диагностического дерева покажите, что если ∗ = +, то все последовательности длины 3 диагностические, а если ∗ = ·, то ни одна последовательность длины 3 не является диагностической. 4.6 Пусть A — минимальный автомат c n состояниями, |M (A)| = 2. (а) Покажите, что существует диагностическая последовательность x̄ ∈ X l такая, что l ≤ δ(A) ≤ n − 1. (б) Привести пример автомата с n состояниями, в котором некоторые два состояния различаются входной последовательностью длины n − 1, но не меньше. 4.7 Выясните, существует ли минимальный автомат A = (X, S, Y, h, f ), у которого |X| = 2, |S| = 3, |Y | = 2, |M (A)| = 2, а число N всех кратчайших диагностических последовательностей длины δ = δ(A) равно: (a) N = 1, δ = 1; (б) N = 2, δ = 1; (в) N = 3, δ = 1; (г) N = 1, δ = 2; (д) N = 2, δ = 2; (е) N = 3, δ = 2; (ж) N = 4, δ = 2; (з) N = 5, δ = 2; (и) N = 0, δ = 2? В случае положительного ответа привести пример соответствующего автомата A. 4.8 Существует ли минимальный автомат A = (X, S, Y, h, f ), у которого |X| = 2, |S| = 3, |Y | = 2, M (A) = S, а длины кратчайших установочных и диагностических последовательностей равны l и d соответственно: (a) l = 1, d = 1; (б) l = 1, d = 2; (в) l = 1, d = 3; (г) l = 2, d = 2; (д) l = 2, d = 1; (е) l = 2, d = 3; (ж) l = 3, d = 3; (з) l ∈ N, d ≥ 4; (и) l = 4, d ∈ N? В случае положительного ответа привести пример соответствующего автомата A. 4.9 Покажите, что кратчайшая диагностическая последовательность для автомата с t выходными символами, где t > 1 и с множеством допустимых состояний мощности m не может быть короче, чем logt m. 4.10 Докажите, что в регулярном автомате A для любого M (A) множества всех установочных и диагностических последовательностей совпадают. 58 4.11 Состояния s и s′ автомата A = (X, S, Y, h, f ) назовем x-совместимыми, если f (s, x) = f (s′ , x) и h(s, x) = h(s′ , x). Докажите, что в случае M (A) = S (а) если для всех x ∈ X найдется пара x-совместимых состояний, то нет диагностической последовательности; (б) если для каждого x ∈ X нет пар x-совместимых состояний, то существует диагностическая последовательность. 4.12 Найдется ли минимальный автомат A = (X, S, Y, h, f ), у которого |X| = 2, |S| = 3, |Y | = 2, M (A) = S, длина кратчайшей установочной последовательности равна l, а диагностических последовательностей не существует: (a) l = 1; (б) l = 2; (в) l = 3; (г) l = 4? В случае положительного ответа привести пример соответствующего автомата A. 4.13 1) Убедиться, что в автомате A для M (A) = S не существует простого диагностического эксперимента и построить кратную диагностическую последовательность. 2) Найти установочную последовательность (не обязательно кратчайшую). (а) X S 1 2 3 4 5 (в) X S 1 2 3 4 5 6 7 a b 4, 0 3, 0 2, 0 1, 0 3, 0 2, 0 3, 1 5, 0 5, 1 1, 1 a b 2, 0 3, 0 5, 1 1, 0 6, 0 7, 1 1, 0 5, 0 6, 0 4, 0 7, 1 5, 0 6, 0 7, 0 (б) X S 1 2 3 4 5 (г) X S 1 2 3 4 5 6 7 a b 2, 0 4, 1 5, 1 3, 1 3, 1 3, 1 1, 1 3, 1 4, 1 2, 1 a b 5, 1 3, 0 4, 0 5, 0 6, 0 7, 0 2, 0 4, 1 2, 0 6, 1 4, 0 2, 1 3, 0 1, 0 4.14 Показать, что в автомате A для любых m допустимых начальных состояний, где 2 ≤ m ≤ n, диагностическая задача решается экспериментом кратности m − 1, но не меньше. X x1 x2 x3 . . . xn−2 xn−1 S 1 1, 1 1, 0 1, 0 . . . 1, 0 1, 0 2 1, 0 1, 1 1, 0 . . . 1, 0 1, 0 3 1, 0 1, 0 1, 1 . . . 1, 0 1, 0 .. . n−1 n 1, 0 1, 0 1, 0 . . . 1, 0 1, 0 1, 0 . . . 1, 0 1, 0 1, 1 1, 0 4.15 Пусть разбиение на классы 1-эквивалентных состояний минимального автомата A c n состояниями содержит r классов. Показать, что в автомате A 59 (a) диагностическая задача для любых двух состояний может быть решена с использованием эксперимента длины l, где l ≤ n − r + 1; (б) диагностическая задача для любых m состояний может быть решена с использованием кратного эксперимента длины l, где l ≤ (m − 1)(n − r + 1); (в) установочная задача для любых m состояний может быть решена с использованием простого безусловного эксперимента длины l, где l ≤ (m − 1)(n − r + 1). 4.16 Доказать, что для сильно связного автомата A c n состояниями и любого допустимого множества состояний M (A) всегда существует эксперимент, переводящий автомат A в заранее выбранное состояние s. При этом длина l этого эксперимента удовлетворяет неравенству l ≤ (m − 1)δ(A) + n − 1, где |M (A)| = m. 4.17 Проверить, что класс K = {A1 , A2 , A3 } является исключительным и построить кратчайшую распознающую последовательность. (а) (б) (в) X S 1 2 X S 1 2 X S 1 2 a b 1, 0 2, 1 1, 0 1, 0 a b 1, 0 2, 1 1, 1 2, 1 a b 1, 1 2, 1 2, 0 1, 0 X S 1 2 X S 1 2 X S 1 2 a b 1, 1 2, 1 2, 0 2, 1 a b 2, 0 2, 1 2, 0 1, 0 a b 1, 1 2, 1 1, 1 1, 0 X S 1 2 X S 1 2 X S 1 2 a b 2, 1 2, 1 1, 0 2, 1 a b 2, 1 1, 1 1, 0 1, 1 a b 1, 1 2, 0 2, 0 2, 0 4.18 Проверить, что класс K = {A1 , A2 , A3 } исключительный и построить распознающую последовательность (не обязательно кратчайшую). (а) X S 1 2 (б) X S 1 2 3 (в) X S 1 2 3 4 a b 2, 1 1, 0 1, 0 1, 0 a b 1, 1 3, 1 2, 1 2, 1 2, 0 1, 1 a b 2, 0 3, 1 1, 0 4, 1 3, 1 4, 0 4, 0 3, 0 X S 1 2 X S 1 2 3 X S 1 2 3 4 a b 2, 0 1, 0 1, 1 2, 0 a b 2, 1 1, 1 1, 0 3, 1 3, 0 1, 1 a b 1, 0 2, 0 3, 1 3, 1 3, 1 2, 1 1, 0 2, 0 X S 1 2 X S 1 2 3 X S 1 2 3 4 a b 1, 0 2, 0 1, 1 2, 0 a b 3, 1 2, 0 1, 0 2, 1 3, 1 1, 0 a b 2, 0 1, 1 2, 0 3, 0 1, 1 1, 1 2, 0 4, 0 60 4.19 Известна часть графа автомата A = ({a, b}, {1, 2}, {0, 1}, h, f ). Построить эксперимент, с помощью которого можно закончить построение графа.  ? 1n  (b, 0) (a, - 0) 2n  (b, 1) 4.20 Известно, что минимальный автомат A имеет алфавиты X = {a, b}, S = {1, 2}, Y = {0, 1}, и в графе автомата нет петель. Найти распознающую последовательность. 4.21 Пусть заданы автоматы без памяти Ai = ({0, 1}2 , {0, 1}, fi ), где i ∈ 0, 3. Автомат A0 — исправный, а остальные автоматы соответствуют различным неисправностям. Построить все кратчайшие контрольные и диагностические тесты, если (a) f0 (x1 , x2 ) = x1 ⊕ x2 , f1 (x1 , x2 ) = x1 , f2 (x1 , x2 ) = x̄2 , f3 (x1 , x2 ) = x1 ∨ x2 , (б) f0 (x1 , x2 ) = x1 x2 , f1 (x1 , x2 ) = x̄1 x2 , f2 (x1 , x2 ) = x̄1 x̄2 , f3 (x1 , x2 ) = 1, (в) f0 (x1 , x2 ) = x1 ⊕ x2 , f1 (x1 , x2 ) = x̄1 x2 , f2 (x1 , x2 ) = x̄1 , f3 (x1 , x2 ) = x1 , (г) f0 (x1 , x2 ) = x1 x̄2 , f1 (x1 , x2 ) = x1 ∨ x2 , f2 (x1 , x2 ) = x̄1 x̄2 , f3 (x1 , x2 ) = x̄1 x2 , (д) f⃗0 = (00100001), f⃗1 = (00001001), f⃗2 = (11011110), f⃗3 = (10011111), (е) f⃗0 = (00100001), f⃗1 = (10111010), f⃗2 = (00010010), f⃗3 = (10110000). 4.22 Пусть Ai = ({0, 1, 2}2 , {0, 1, 2}, fi ), где i ∈ 0, 4. Автомат A0 — исправный, а остальные, соответствуют различным неисправностям. Построить все кратчайшие контрольные (диагностические) тесты, если отображения fi (z1 , z2 ) заданы следующей таблицей: z1 1 1 1 2 2 2 z2 1 2 1 2 1 2 f0 2 2 1 2 f1 1 2 1 2 2 f2 1 2 2 1 2 2 1 f3 2 1 1 1 2 f4 2 2 1 2 1 4.23 Пусть Ai = (X, Y, fi ) для всех i ∈ 0, N − 1, A0 — исправный автомат, а все остальные соответствуют различным неисправностям. Показать, что при условии |Y | > 1, длина l кратчайшего диагностического теста для распознавания неисправности удовлетворяет соотношениям log|Y | N ≤ l ≤ N − 1. 4.24 Автомат A задан переходно-выходной таблицей: A X S 1 2 3 a b 1, 0 3, 1 3, 0 3, 0 2, 1 1, 0 Известно, что A неисправен и в результате неисправности по крайней мере вместо одной из выходных единиц появляется нуль. Описать эксперимент, распознающий повреждение.