Тематический план

  • 1. Предварительные сведения

    Цель учебно-методического пособия - познакомить читателя с начальными понятиями теории автоматов. Сначала излагаются необходимые сведения из теории множеств и современной алгебры, приводятся примеры решения задач, представлен список задач для самостоятельного решения. Соответствующий материал можно найти в любой книге по универсальной алгебре или теории полугрупп. Мы отсылаем читателя к [1,2,3,9]. Затем вводим понятие конгруэнции на автомате и определяем фактор-автомат. Одно из ключевых понятий - это отношение эквивалентности на множестве состояний автомата, изучаем это понятие. Излагаем метод построения приведенного (или минимального) автомата. Здесь мы следуем книге [4]. Показываем, как можно преобразовать компьютерные программы, соответствующие данному автомату, в более простые. Полезными оказались также  книги [5,6,7]. Отметим, что  пособие сопровождается достаточным числом подробно разобранных примеров. Мы приводим большое количество задач для самостоятельного решения.

    В основу данного учебного пособия положены лекции, на протяжении многоих лет читаемые автором на математическом факультете Алтайского государственного университета.  

    Условимся через N, Q, R обозначать множества натуральных, рациональных, действительных чисел соответственно. Напомним некоторые стандартные формулы:

         a ∈ A - элемент a принадлежит множеству A,

         a ∉ A - элемент a не принадлежит множеству,

        A ⊆ B - A является подмножеством множества B,

         A ⊈ B - A не является подмножеством множества B,

         |A| - количество элементов конечного множества A. |A| называется порядком множества A.

         Выражение {a∈A ∣...} читается "множество всех элементов  a ∈ A таких, что ..."  Например, {n ∈N |  n делится на  2}  - это множество всех n ∈ N, которые делятся на 2, т.е. множество всех натуральных четных чисел.

         ∅ - знак пустого множества,

         ⇒ - следует,

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

         ∀ - для каждого,

         A∩B={ x | x ∈ A и  x ∈ B} - пересечение множеств A и B,

         A∪B={ x | x ∈ A или  x ∈ B} - объединение множеств A и B.

         A \ B={ x ∈ A | x ∉ B} - разность множеств A и B.

         Через A1× A2×...× An обозначаем множество всех последовательностей (a1,a2,...,an), где ai∈ Ai, т.е.
         A1× A2×...× An ={(a1,a2,...,an) |  a1∈ A1, a2∈ A2,..., an∈ An}. Например, 1) если A={1,2} , B={1,3,4}, то A× B={(1,1), (1,3), (1,4), (2,1), (2,3), (2,4)}, если A={△,▽}, B={0, x}, то A × B = {(△,0), (△, x), (▽,0), (▽, x)}. Несложно заметить, что  |A× B|=|A||B|.

         A1× A2×...× An называется  декартовым произведением множеств  A1, A2,...,  An     

         Закон, который каждому элементу a множества A сопоставляет некоторый элемент (однозначно определенный) f(a) из B, называется  отображением множества A в множество B и обозначается либо буквой f либо так: f : A → B.  Вместо f разрешается использовать любые символы, например, ◦. Элемент f(a) называется  образом элемента a при отображении f, элемент a - прообраз элемента f(a) при f.

        Отображение f : A → B называется отображением на множество B, если каждый элемент из B имеет прообраз. В этом случае иногда пишем  f : A на→ B.

        Отображение  f : A → B называется  взаимно однозначным, если оно "на" и различным элементам из A сопоставлены разные элементы из B (т.е.   a≠b ⇒ f(a) ≠ f(b)).

    Упражнение 1.1 Выписать все элементы множества A× B, если
        1) A = {1, 2}, B = {3, 4}, 2) A={1,2,3}, B={1,2,3} , 3) A={ a,b} , B={ x,y,}, 4) A ={∗, ⋆}, B={◦, •,×}.

  • 2. Фактор-множество

         Пусть A - произвольное непустое множество. Любое подмножество θ ⊆ A × A называется бинарным отношением на A.


    Пример 2.1 A = {0, 1}, θ = {(0,1), (1,0), (0,0)} - бинарное отношение на A.


         Вместо (a,b) ∈ θ часто пишут aθb и произносят "a находится в отношении θ с b".


    Пример 2.2 ≤ ={ (a,b) | a,b ∈ N, a ≤ b} - бинарное отношение на N (Вместо θ мы используем символ ≤. Ясно, что вместо (a,b) ∈ ≤ удобнее писать  a≤ b.


         Бинарное отношение θ на A называется эквивалентностью (или отношением эквивалентности), если оно удовлетворяет следующим аксиомам:

        1) для любого a ∈ A имеем: aθa  (закон рефлексивности),
        2) для любых a, b ∈ A если aθb, то bθa  (закон симметричности),
        3) для всех a,b,c ∈ A, если aθb и bθc, то aθc (закон транзитивности).


        Обозначение: εA = {(a, a) | a ∈ A}. εA является эквивалентностью на A и называется отношением равенства.


        Пусть θ   эквивалентность на A. Берем любой элемент  a ∈ A. Тогда множество {b ∈ A | bθa} называется смежным классом A по θ, содержащим элемент a. Этот смежный класс будем обозначать так: aθ, [a]θ, [a] или ā в зависимости от ситуации.


    Теорема 2.1  Пусть θ - эквивалентность на A, a,b ∈ A. Тогда смежные классы aθ и bθ либо совпадают либо не пересекаются.
     Доказательство. Предположим, что aθ ∩ bθ ≠  ∅. Докажем сначала, что aθ⊆bθ. Зафиксируем любой элемент c ∈ aθ ∩ bθ. Пусть x ∈ aθ. Видим, что xθa, aθc, cθb. Следовательно, по закону транзитивности, xθb. Отсюда aθ⊆bθ. Включение bθ⊆aθ доказывается аналогично. Итак, aθ = bθ. Теорема доказана.


        Обозначение: A/θ ={aθ | a ∈ A} - множество различных смежных классов A по эквивалентности θ.  A/θ   называется фактор-множеством множества A по эквивалентности θ. Отметим, что элементы фактор-множества - это смежные классы.


    Пример 2.3 Пусть A={ 1,2,3,4,5}, θ ={ (x,y) | x, y одинаковой четности}. Тогда 1θ ={b | bθ1} ={1,3,5}, 2θ ={b | bθ2} ={2,4} , откуда A/θ ={{1,3,5} ,{ 2,4}} . Таким образом, фактор-множество A/θ состоит из двух элементов. Заметим, что запись классов неоднозначная. В нашем случае 1θ =3θ =5θ, 2θ =4θ.


    Упражнение 2.2
    1) Переписать определение эквивалентности, заменив везде выражение вида xθy на (x,y) ∈ θ.
    2) Убедиться, что класс aθ содержит элемент a.
    3) Каким аксиомам из определения эквивалентности удовлетворяют следующие отношения на N:
    F_1={(x,y) | x  делит  y} ,
    F_2={(x,y) | x  и  y взаимно простые},
    F_3={(x,y) | x = y2}?
    4) Какими свойствами обладает бинарное отношение  F ⊆ R × R, определенное так:

    (a,b) ∈ F ⇔  \( \frac{a}{a^2+1}\leq \frac{b}{b^2+1}. \) 

    5) Привести примеры бинарных отношений, которые из трех аксиом (рефлексивность, симметричность, транзитивность) удовлетворяют только двум.
    6) Выписать все отношения на { 0,1}, удовлетворяющие закону рефлексивности.
    7) Найти все эквивалентности θ на A={1,2,3} и выписать элементы всех возникших фактор-множеств A/θ.


  • 3. Полугруппы

         Любое отображение f: A × A -> A называется  (бинарной) операцией на A. Образ элемента (a1,a2) при f обозначается через f(a1,a2)  либо через  a1fa2. Последнее удобно, если вместо f писать знаки +,  ∘,∗ ,... Знак умножения \( \cdot \)  часто опускается.

         Всякое непустое множество A с заданной на нем бинарной операцией \( \cdot \), удовлетворяющей аксиоме: для любых a,b,c ∈ A (ab)c=a(bc)  (закон ассоциативности), называется  полугруппой. Эта полугруппа обозначается буквой A или   <A;\(\cdot \)>.

    Упражнение 3.1  Пусть A - полугруппа, a1,a2,... ,an ∈ A. Доказать, что результат произведение a1a2... a не зависит от способа расставления скобок.


         Ввиду упражнения 3 в произведениях вида a1a2... a скобки обычно не ставятся  и пишут an вместо aa...a (n раз).

    Пример 3.1  <R \{0} ;\(\cdot\) >, <\{ 1,-1\}; \(\cdot\) >, <Q; +> \) - примеры полугрупп.


         Элемент e полугруппы A называется единицей, если для любого x ∈ A ex=xe=x. Полугруппа может не содержать единицы. С другой стороны, если e1, e2 - единицы полугруппы, то по аксиоме элемент e1e равен как e1 так и e2 . Следовательно, e1 = e2 . Итак, если полугруппа содержит единицу, то она единственна.

         Важным примером полугруппы является полугруппа преобразований данного множества A, которая обозначается SA. Дадим ее определение. Преобразованием множества A называется любое отображение A в себя. Если A={ a1, ... , an} - конечное множество, то  преобразование  f:A -> A   часто обозначают через  \( f= \begin{pmatrix} a_1 & a_2 & \ldots & a_n \\ a_{i_1} & a_{i_2} & \ldots & a_{i_n} \end{pmatrix}, \)  где \( a_{i_k}=f(a_i) \). Операция умножения преобразований определена так:
     \( \begin{pmatrix} \ldots & a_i & \ldots \\ \ldots & a_k & \ldots \end{pmatrix} \begin{pmatrix} \ldots & a_k & \ldots \\ \ldots & a_m & \ldots \end{pmatrix}=\begin{pmatrix} \ldots & a_i & \ldots \\ \ldots & a_m & \ldots \end{pmatrix}, \)
    т.е. (fg)(i)=g(f(i)). Единицей полугруппы SA служит преобразование
     \( \begin{pmatrix} a_1 & a_2 & \ldots & a_n \\ a_1 & a_2 & \ldots & a_n \end{pmatrix}. \)

         Пусть A и B - полугруппы. Отображение  f:A -> B  называется  гомоморфизмом полугруппы A в полугруппу B, если для любых a,b ∈ A f(ab)=f(a)f(b). Взаимно однозначный гомоморфизм f:A -> B  называется изоморфизмом. Говорят, что полугруппы A и B  изоморфные (пишут  \( A \simeq B \)), если существует изоморфизм  A на B. Заметим, что изоморфные полугруппы воспринимаются одинаковыми, так как одна из другой получается переобозначением каждого элемента a  на f(a).

         Эквивалентность  θ на полугруппе A называется конгруэнцией, если для любых a1,a2,b1,b2 ∈ A справедливо следующее:

     если a1 θb1 и a2 θb2 , то  a1 a2 θ b1b2.

          Введем на фактор-множестве A/θ операцию так: aθ  bθ =abθ.

         Теорема. Если θ - конгруэнция на полугруппе A, то A/θ - полугруппа.

          Доказательство. Поскольку, как было отмечено ранее, запись смежного класса неоднозначная, то проверим сначала, что результат произведения не зависит от способа обозначения смежных классов. Пусть a1 θ =b1θ, a2 θ =b2θ. Тогда a1 θb1 и a2 θb2 , откуда

    a1 a2 θ b1b2. Значит, a1 a2 θ = b1b2 θ . Корректность определения умножения доказана. Закон ассоциативности следует из равенств:

    (a θ  b θ )cθ  =a bcθ , aθ ( bθ cθ )=abcθ . Теорема доказана.

         Полугруппа A/θ называется фактор-полугруппой полугруппы A по конгруэнции θ.

         Отображение f :A-> A/θ , при котором f (a)=aθ, является гомоморфизмом полугруппы A на фактор-полугруппу A/θ и называется  естественным гомоморфизмом.

         Пример. Пусть f:A-> B - гомоморфизм полугрупп. Полагаем ker f={ (a1,a2) | f(a1)=f(a2)}. Несложно проверить, что ker f является конгруэнцией на A.

         ker f называется ядерной конгруэнцией на A.

         Cформулируем теорему о гомоморфизмах полугрупп.

       

         Теорема (о гомоморфизмах). Пусть f: A-> B - гомомрфизм полугруппы A на полугруппу B. Тогда полугруппа B изоморфна фактор-полугруппе  A/ker f.

         Доказательство приведено в файле Теорема о гомоморфизмах.

         Дадим определение свободной полугруппы. Пусть X={ x1, ... ,xn} - любое множество (называемое алфавитом). Полагаем:

    1) если x ∈ X, то x - слово,
    2) если t, f - слова, то tf - слово (tf получается приписыванием к слову t слова f),
    3) всякое слово может быть получено по правилам 1), 2).

         На множестве всех слов введем операцию умножения следующим образом:

     t\(\cdot\) f=tf .

         Возникшую полугруппу обозначаем через F(X)  и называем свободной полугруппой, порожденной множеством X.

         Добавим к  F(X) новый символ \( \lambda \)  (\(\lambda \) обычно интерпретируется, как пустое слово). Полагая \( t\cdot\lambda =\lambda\cdot t=t \), получим новую полугруппу F0(X)=F(X) ∪ { \( \lambda\) }, называемую  свободной полугруппой с единицей, порожденной множеством X. Полугруппу F0(X), как правило, будем  обозначать через X*.

    Пример 3.2 Если X={x} , то F(X)=F(x)={x, xx, xxx,...} ={ x | n∈ N}, X*={\(\lambda \),x, xx, xxx,...}.

          Длиной элемента \( x_{i_1}x_{i_2}\ldots x_{i_n}\in X^* \) называется число n. |t| - так обозначается длина t. По определению |\(\lambda \)|=0.


    Упражнение 3.2 На множестве M определена операция ∘  по правилу, сформулированному ниже.  Является ли M полугруппой? В случае, когда M - полугруппа, найти ее единицу.

    1) x  ∘ y = x2 y2, M={r ∈ R | r > 0}.

    2)  x  ∘ y = 2xy, M=N.

    3) x  ∘ y = x-y, M=Z.

    4) x  ∘ y = xy, M=N.

    5) x  ∘ y = sin x sin y, M=R.

    6) x  ∘ y = x2 y2, M=Z.

    7)  x  ∘ y = НОД(x,y), M=N.

    8)  (x,y)  ∘ (z,t) = (x,t), M=N × N.

    9) (x,y,z)  ∘ (u,v,t) = (x+u,y+v,z+t), M=N × N × N.

    10) (x,y)  ∘ (u,v) = (xu-yv,xv+yu), M=R × R.

  • 4. Определение автомата

         Конечным автоматом называется набор из пяти объектов  (A,X,B, ∘ ,∗ ), где

    A называют множеством состояний автомата,

    X - множеством входных символов (множеством входов),

    B - множеством выходных символов (множеством выходов),

     ∘ : A × X -> A   - отображение (называемое функцией переходов автомата),

    ∗ : A × X -> B  -  отображение (называемое функцией выходов автомата).

         Предполагается, что A,X,B - конечные множества. Автомат будем обозначать либо (A,X,B, ∘ ,∗ ) \), либо (A,X,B), либо какой-нибудь одной буквой, например, A.

    Часто реальную ситуацию моделируют в виде автомата, а затем ее изучают. Приведем пример.


    Пример 4.1 Устройство имеет две входные линии  и одну выходную. Оно может находится в двух состояниях 0 и 1. На каждую линию могут подаваться сигналы 0 (отсутствие сигнала) либо 1 (наличие напряжения на линии). Значение на выходе совпадает с состоянием устройства. Значения входов рассматриваем как последовательности: x1=(0,0), x2=(0,1), x3=(1,0) (варианта (1,1) не бывает). Эти входы действуют так:

    если устройство находилось в состоянии 0, то при входах x1 и  x2 состояние не меняется а при входе  x3 оно переходит в состояние 1;

    если устройство находилось в состоянии 1, то при входах x1 и  x3 состояние не меняется а при входе  x2 оно переходит в состояние 0.

         Смоделируем ситуацию в виде автомата. Полагаем: X={x1,x2,x3} , A={0,1}, B ={0,1}. Функции переходов и выходов  определяются так:

      0 ∘ x_1=0,   0 ∘ x_2=0,  0 ∘ x_3=1,

     1 ∘ x_1=1,  1 ∘ x_2=0,  1 ∘ x_3=1,

    0∗ x_1=0,  0∗ x_2=0,  0∗ x_3=1,  

       1∗ x_1=1,  1∗x_2=0,  1∗ x_3=1. 

    Получили автомат  (A,X,B, ∘ ,∗ ) ,  к изучению которого можно применять любые методы теории автоматов.


         Существуют разные способы задания автоматов. Способ задания ∘ ,∗, рассмотренный в примере 4.1, называется аналитическим.

         Табличный способ - это в задание функций  ∘ ,∗,  в виде таблиц. В примере 4.1 таблицы выглядят так (они совпадают): (cм.Табл1.pdf).

         Прежде, чем изложить графический способ задания автомата, введем одно понятие.

         Ориентированный граф G - это пара множеств (V,E), где V - множество вершин, E - множество ребер.  Каждому ребру e ∈ E соответствует упорядоченная пара вершин (v,u), v,u ∈ E (ребро ведет из v в u). Возможны петли (v=u). Геометрически ориентированный граф изображается так:  каждой вершине соответствует точка (либо круг) на плоскости, а каждому ребру (v,u) - линия, направленная от вершины v к вершине u (направление указывается стрелкой).

         Графический способ задания автомата (с помощью ориентированного графа) состоит в следующем. Вершины - это состояния автомата. Из вершины a1 выходит ребро с концом в a2, если существует x ∈ X такой, что a2=a1 ∘ x. Это ребро обозначается парой (x,b), где  b - выходной символ, равный b=a1 ∗ x.

    Примеру 1 соответствует следующий граф: (Граф1.pdf).

    Упражнение 4.1 Построить автоматы, соответствующие следующим ситуациям, изобразить их графически и в виде таблиц.

    1) A=X=B={0,1} . Функции  ∘ , ∗   определяются так: a ∘ x =a+x (mod 2), a ∗ x =ax (mod 2).

    2) A=X=B={0,1,3} . Функции ∘ , ∗,    определяются так: a ∘ x =a+x (mod 3), a ∗ x =ax (mod 3).

    3) На устройство подаются числа 0 и 1. На каждом шаге оно вычисляет сумму  чисел по модулю 3, введенных в устройство и печатает это число. Рекомендация: X={0,1} , A={a0, a1, a2}, B={0,1,2}.

    4) Монета многократно подбрасывается и делается отметка при при четных выпаданиях цифры и при каждом втором выпадании герба (не обязательно подряд). Рекомендация: X={Г, Р}, A={a00, a01 , a10, a11}, B={0,1}.

    5) Грузовой лифт, обслуживающий трехэтажный магазин, имеет кнопку вызова на каждом этаже и работает по следующим правилам: если нажата одна кнопка, то лифт движется на этаж, на котором расположена данная кнопка; если нажаты одновременно две или три кнопки, то лифт движется на самый нижний из всех этажей, на которых нажаты кнопки. Ни одна кнопка не может быть нажата во время движения лифта.
    Рекомендация: x - этаж, на котором нажата кнопка, b - направление, в котором будет двигаться лифт, и число этажей, которое он при этом пройдет без остановки, A={0,1,2}.

    6) Вращение колеса, приводимого в движение двигателем, определяется двухпозиционным ключом. Правое положение ключа соответствует вращению в направлении по часовой стрелке, левое - против часовой стрелки. В момент изменения направления вращения вспыхивает индикаторная лампа. Если при вращении в данный момент по часовой стрелке переместить ключ вправо или при  вращении в данный момент против часовой стрелки переместить ключ влево, то направление движения не изменится.
    Если при вращении в данный момент по часовой стрелке переместить ключ влево или при  вращении в данный момент против часовой стрелки переместить ключ вправо, то направление движения  меняется. Рекомендация: A={по часовой стрелке, против часовой стрелки}, X={справа, слева}, B={лампа включена, лампа выключена}.

    7) Организм возбуждается двумя стимулами "положительным"  и "отрицательным". Организм не реагирует на отрицательный стимул и реагирует на чередование положительных стимулов.

    A={реакция на последний положительный стимул, нет реакции на последний положительный стимул} ,

     X={положительный стимул, отрицательный стимул},

    B={реакция, нет реакции}.

    При состоянии в данный момент "реакция на последний положительный стимул" и входе "положительный стимул" появляется выход "нет реакции" и следующее состояние "нет реакции на последний положительный стимул". При состоянии системы в настоящий момент "нет реакции  на последний положительный стимул" и входе "положительный стимул"  появляется выход "реакция" и следующее состояние  "реакция на последний положительный стимул". При входе "отрицательный стимул" появится выход "нет реакции" , независимо от состояния в настоящий момент, а состояние системы не изменяется.

  • 5. Фактор-автомат

         Конгруэнцией на автомате A=(A,X,B)  называется тройка эквивалентностей ρ =(ρ123), где ρ1 - эквивалентность на множестве A, ρ2 - на множестве X, ρ3 - на множестве B, удовлетворяющая условиям: для любых a1,a2 ∈ A, x1,x2 ∈ X

     если a1 ρ1 a2,  xρ2x2, то (a1 ∘ x11(a2 ∘ x2),

    если  a1ρ1a2, xρ2 x2, то  (a1 ∗ x13(a∗ x2).

         Примеры конгруэнций: (A × A, X × X, × B), (εAXB ),(A×A, εX ,B×B), где, как ранее было отмечено, εX ={(x,x) | x ∈ X}.

         Пусть ρ =(ρ123) - конгруэнция на автомате A=(A,X,B). Автомат с основными множествами A/ρ1, X/ρ2, B/ρ3
    и операциями ∘, ∗, определенными по правилу:

    [a]ρ∘ [x]ρ2=[a ∘ x]ρ1, [a]ρ∗ [x]ρ2=[a ∗ x]ρ3,
    называется фактор-автоматом автомата A и обозначается  A/ρ.

         Необходимо проверить, что определение операций не зависят от вида записи смежных классов. Действительно, пусть      [a]ρ1=[a']ρ1, [x]ρ2=[x']ρ2. Тогда aρ1a', xρ2x'. Теперь из определения конгруэнции: (a ∘ x)ρ1(a' ∘ x'), (a ∗ x)ρ3(a' ∗ x'), т.е.                          [a ∘ x]ρ1=[a' ∘ x']ρ2, [a ∗ x]ρ3=[a' ∗ x']ρ3. Проверка корректности определения операций завершена.

         Пусть ρ =(ρ123), τ =(τ123) - конгруэнции на автомате A. Из определения конгруэнции следует, что
    ρ ∩ τ =(ρ1 ∩ τ12 ∩ τ23 ∩ τ3) - конгруэнция. Возьмем произвольную тройку s=(s1,s2,s3) множеств  (s1 ⊆  A, s2 ⊆  X, s3 ⊆ B). Пересечение всех конгруэнций ρ =(ρ123),  таких, что s1 ⊆ ρ1, s2 ⊆  ρ2, s3 ⊆ ρ3, называется  конгруэнцией, порожденной s (т.е. это наименьшая конгруэнция, содержащая s). Отметим, что множества si могут быть пустыми.

    Пример 5.1 Пусть  A - автомат, изображенный на Рис.2 (см. Граф2.pdf). Найти наименьшую конгруэнцию ρ = (ρ123) такую, что (1,3) ∈ ρ1 и построить фактор-автомат A/ρ.

    Решение. Поскольку (1,3) ∈ ρ1, то (1 ∗ a,3 ∗ a)=(1,3) ∈ ρ1. Из определения эквивалентности следует, что ρ1 ⊇  ε∪ {(1,3),(3,1)}. Непосредственная проверка показывает, что ρ1   =  ε ∪ { (1,3),(3,1)} ,ρ2  X, ρ3= ε∪ {(1,3),(3,1)} ) является конгруэнцией. Значит, ρ совпадает с этой конгруэнцией.

         Из определения фактор-множества следует, что

     A/ρ1=\( \{ \overline{1}, \)\( \overline{2}, \)\( \overline{4}, \)\( \overline{5}, \)\( \overline{6}\} \), где \( \overline{1}=\{ 1,3\} \), \( \overline{2}=\{ 2\} , \overline{4}=\{ 4\} \), \( \overline{5}=\{ 5\}, \overline{6}=\{ 6\}. \)  \( X/\rho _2=\{ \overline{a},\overline{b}\} \), где \( \overline{a}=\{ a\} \),
    \( \overline{b}=\{ b\} \). \( B/\rho _3=\{ \overline{1},\overline{2},\overline{4},\overline{5},\overline{6} \) \(\}\), где   \( \overline{1}= \)\( \{ 1, 3\} \),
    \( \overline{2}=\{ 2\} , \overline{4}=\{ 4\} , \overline{5}=\{ 5\} , \overline{6}=\{ 6\} \).

    Одноэлементный класс \( \overline{m} \) будем обозначать через m.  Теперь можно изобразить автомат графически так: (Граф2.pdf , Рис. 3).

    Упражнение 5.1 

    1) Найти наименьшую конгруэнцию ρ = (ρ123) такую, что (0,1) ∈ ρ2 и построить фактор-автомат A/ρ, где A: (см. Табл2.pdf ).

    2)  Пусть A - автомат, изображенный на Рис.2 (см. Граф2.pdf ).  Найти наименьшую конгруэнцию  ρ = (ρ123)  такую, что (1,3),(1,5) ∈ ρ1 и построить фактор-автомат  A/ρ.

    3)  Пусть A - автомат, изображенный на Рис.2 (см. Граф2.pdf ). Найти наименьшую конгруэнцию ρ = (ρ123) такую, что (1,3),(4,6) ∈ ρ1 и построить фактор-автомат  A/ρ.

    4)  Пусть A - автомат, изображенный на Рис.2 (см. Граф2.pdf ). Найти наименьшую конгруэнцию ρ = (ρ123) такую, что (1,3),(1,5),(4,6)∈ ρ1 и построить фактор-автомат  A/ρ.


  • 6. Эквивалентность состояний

         Пусть A=(A,X,B, ∘ ,∗ ) \) - автомат. Отображения f*: A × X* →  A,  g*: A ×  X* → B* определим следующим образом:

                                                    f*(a,λ )=a,

                                              f*(a,wx)=f*(a,w) ∘ x,

                                                     g*(a,λ )=λ,

                                        g*(a,wx)=g*(a,w)(f*(a,w) ∗ x)

    для всех a ∈ A, x ∈  X, w ∈ X*. Здесь слово g*(a,w)(f*(a,w) ∗ x) получается приписыванием справа к слову g*(a,w) слова f*(a,w) ∗ x. Из определений следует, что

    f*(a,x1x2x3... xn-1xn )=(... (((a ∘  x1) ∘  x2) ∘  x3) ∘ ... ∘  xn-1 ) ∘ xn,

    поэтому вместо f*(a,x1x2x3... xn-1xn  ) мы иногда будем писать просто a ∘ x1x2x3... xn-1xn.

    Пример 6.1  Пусть A -  автомат, изображенный на Рис.2 (Граф2.pdf ), тогда
    1) f*(1,abbbaaba)=1 ∘ abbbaaba=1∘ bbbaaba=2 ∘ bbaaba=4 ∘ baaba=6∘ aaba=5 ∘ aaba=3 ∘ aba=3 ∘ ba=2 ∘ a=3,
    2) g*(1,abba)=g(1,abb) (1 ∘  abb) ∗ a=g^*(1,abb)(4 ∗  a)=g*(1,abb)5=g*(1,ab)((1 ∘  ab) ∗ b)5=g*(1,ab)(2∗ b)5=g*(1,ab)45=
    g*(1,a)((1 ∘ a) ∗ b)45=(1∗ a)(1∗ b)45=1245.

    Математической индукцией по длине слова w несложно доказывается следующая теорема
    Теорема 6.1 Пусть A=(A,X,B,∘ ,∗ )  - автомат. Тогда для произвольных v,w ∈ X* и каждого a ∈  A выполняются равенства

    f*(a,vw)=f*(f*(a,v),w),

    g*(a,vw)=g*(a,v)g*(f*(a,v),w).

    Доказательство оставляем читателю в виде легкого упражнения.

         Отметим, что эта теорема позволяет вычислять g*(a,w) сначала вводя первую букву слова w, затем вторую и т.д. Это удобно. В качестве примера снова вычислим g*(1,abba) из примера 6.1. Имеем:

    g*(1,abba)=1 ∗ ag*(1 ∘ a,bba)=1g*(1,bba)=1(1 ∗ b)g*(1 ∘ b,ba)=12g*(2,ba)=12(2 ∗ b)g*(2 ∘ b,a)=124(4 ∗ a)=1245.

         Состояния a1 и a2 называются  эквивалентными, если g*(a1,w)=g*(a2,w) для каждого w ∈ X*. Введем отношение эквивалентности τA на множестве состояний A. Полагаем: a1τAa2 тогда и только тогда, когда a1 и a2  эквивалентны, т.е.

     a1τAa⇔  g*(a1,w)=g*(a2,w) для каждого w ∈  X*.

    Лемма 6.1. Пусть  A=(A,X,B, ∘ ,∗ ) \) - автомат,  τ =( τA, εX B). Тогда  τ  - конгруэнция.

    Доказательство. Пусть a1τAa, x1εXx2. Тогда  x1= x2. Проверим истинность свойств из определения конгруэнции. Из определения эквивалентности состояний следует, что

    a∗  x1 =g*( a, x1 )=g*( a2, x1 )= a2 ∗  x1 , т.е. ( a∗  x1 ) εB ( a2 ∗  x1 ), 
    значит, одно из свойств конгруэнции выполнено.

         Берем любое слово v  ∈ X*. Поскольку состояния a1, a2 эквивалентные, то g*(a1,x1v)=g*(a2,x1v).  Воспользуемся теоремой 6.1:
    g*(a1, x1v)=g*(a1, x1)g*(f*(a1, x1),v) \( \Rightarrow \)   g*(a1,x1v)=a1 x1g*(a1   x1,v),
     g*(a2,x1v)=g*(a2,x1)g*(f*(a2,x1),v) \(\Rightarrow\)  g*(a2,x1v)=a2  x1g*(a2  x1,v).
     Ранее было показано, что a1x1=a2  x1. Отсюда g*(a1x1,v)=g*(a2  x1,v). Это означает, что  состояния a1 x1,a2  x1 эквивалентны. Лемма доказана.

         Автомат A/τ  =(A/τA,X/εX,B/εB) называют  приведенным (или  минимальным) автоматом, соответствующим автомату A. Так как смежные классы фактор-множеств X/εX, X/εB одноэлементные, то класс \(\overline{m}\) принято обозначать просто m. В этих обозначениях имеем:
    A/τ =(A/τA, X, B).
         Отметим, что в приведенном автомате нет разных эквивалентных состояний.


  • 7. Приведенные автоматы

         Наша  ближайшая цель - научиться строить приведенные автоматы. Достичь эту цель поможет теорема Хаффмана - Мили и ее доказательство. Предварительно введем одно понятие.

         Пусть дан автомат A=(A,X,B), m - натуральное число. Состояния a,a' называются m-эквивалентными, если
    g*(a,w)=g*(a',w) для всех входных последовательностей w длины, не превышающей m. Пишем a ma', если a,a' m-эквивалентные.
         Обозначение: Km=A/ m, т.е. элементами множества  Km являются смежные классы A по  m.

    Теорема 7.1(Хаффман, Мили) Для эквивалентности двух состояний a1 и a2 автомата с n состояниями (n>0) достаточно, чтобы g*(a1,w)=g*(a2,w) для всех входных последовательностей w длины, не превышающей n-1.

    Доказательство в файле ТеоремаХМ.pdf.

         При доказательстве теоремы мы получили, что Ki=Ki+1=Ki+2=... Это означает, если два состояния лежат в одном классе по  i, то они эквивалентны. Значит смежные классы по ⊖i и по  τA совпадают, т.е. Ki=A/ ⊖.

    Следствие 7.1
    Если Ki=Ki+1, то A/τ =(Ki,X,B).

         Это следствие мы будем использовать при построении приведенного автомата.

    Пример 7.1 Построить приведенный автомат, соответствующий автомату A, изображенному на Рис. 4 (см. Граф4.pdf).

    Решение. Вычисляем

    0 ∗ 0=0, 1 ∗ 0=0, 2 ∗ 0=1,

    0 ∗ 1=1, 1 ∗ 1=1, 2 ∗ 1=0.

    Видим, что 0 и 1 являются 1-эквивалентными. Значит, K1={ { 0,1} ,{ 2}}. Вычисляем

    0 ∗ 00=00, 1 ∗ 00=00,

    0 ∗ 10=11, 1 ∗ 10=11,

    0 ∗ 01=01, 1 ∗ 01=01,

    0 ∗ 11=10, 1 ∗ 11=10.

    Смежный класс

     = { 2}  состоит из одного элемента, поэтому разбиение его на более мелкие классы не произойдет. Получаем, что 0 и 1 являются 2-эквивалентными. Значит, K2={ { 0,1} ,{ 2}}=K1.  В виду следствия (и по теореме) процесс построения приведенного автомата закончен и A/ τ =K_1. Этот автомат изображен на Рис.5 (см. Граф4.pdf)..

    Упражнение 7.1 Найти графическое изображение следующих (см. Табл3.pdf)  и соответствующих им приведенных автоматов.


  • 8. Преобразование компьютерных программ

         Любой автомат A позволяет  вычислять g*(a,w) по входной последовательности w. Возникает алгоритм вычисления   g*(a,w) по w. Этот алгоритм всегда можно оформить в виде компьютерной программы. Если от автомата A перейти к приведенному автомату A/τ то из определения конгруэнции τ следует, что  g*(a,w)=g*( ,w). Это означает, что приведенный автомат вычисляет ту же функцию w -> g*(,w)(=g*(a,w)). По приведенному автомату мы можем написать новую программу, вычисляющую g*(,w) по w. Возник способ преобразования программ, соответствующих автомату A, в более простые программы (соответствующие приведенному автомату), вычисляющие те же функции.

    Пример 1.
    Пусть A - автомат, изображенный на Рис. 4 (см. Граф4.pdf). Наша цель - написать программу, вычисляющую по каждой входной последовательности  x1x2...слово  g*(0,x1x2...xn), где  xi ∈{ 0,1}.

    Решение. Сначала изложим алгоритм вычисления g*(0,x[1]x[2]...x[n]).  У нас s соответствует состоянию, в котором
    находится автомат, x[i] - входному символу, d - состоянию, в которое перейдет автомат в результате ввода x[i] (d=s ∘ x[i]), b - выходному символу (b=s ∗ x[i]),
    команда print b  означает, что печатается b.

    Вводим n, x[1],x[2],...,x[n]. s= 0.
    Далее алгоритм выглядит в виде цикла, где i - счетчик цикла. Тело цикла получается в результате обработки  алгоритма:

    если s=0 и x[i]=0, то d=1 и b=0;

    если s=0 и x[i]=1, то d=2 и b=1;

    если s=1 и x[i]=0, то d=0 и b=0;

    если s=1 и x[i]=1, то d=2 и b=1;

    если s=2 и x[i]=0, то d=2 и b=1;

    если s=2 и x[i]=1, то d=0 и b= 0;

    s=d;

    print b.

    В результате программа напечатает слово g*(0,x[1]x_[2]...x[n]).

         Этот алгоритм можно реализовать в виде следующих программ на языке программирования C.

    Вариант 1.
    #include<stdio.h>
    #include<stdlib.h>

    int main(void) {
     int n = 0;
     int s = 0;
     int d = 0;
     int b = 0;
     int * x;
     inti;
     
     scanf("%d", &n);
     x = (int *)malloc(n * sizeof(int));
     
     for ( i = 0; i< n; i++) {                              
      scanf("%d", &x[i]);
     }
     
     for (i = 0; i< n; i++) {
      if (0 == s && 0 == x[i]) {
       d = 1;
       b = 0;
      }

      if (0 == s && 1 == x[i]) {
       d = 2;
       b = 1;
      }
      
      if (1 == s && 0 == x[i]) {
       d = 0;
       b = 0;
      }
      
      if (1 == s && 1 == x[i]) {
       d = 2;
       b = 1;
      }
      
      if (2 == s && 0 == x[i]) {
       d = 2;
       b = 1;
      }
      
      if (2 == s && 1 == x[i]) {
       d = 0;
       b = 0;
      }

      s = d;
      printf("%d\n", b);
     
     }
     free(x);
     return 0;
    }

    //////////////////////////////
    Вариант 2.

    #include<stdio.h>
    #include<stdlib.h>

    int main(void) {
     int n = 0;
     int s = 0;
     int d = 0;
     int b = 0;
     int x;
     inti;
     
     scanf("%d", &n);
     for (i = 0; i< n; i++) {
      scanf("%d", &x);
      if (0 == s && 0 == x) { d = 1; b = 0; }
      if (0 == s && 1 == x) { d = 2; b = 1; }
      if (1 == s && 0 == x) { d = 0; b = 0; }
      if (1 == s && 1 == x) { d = 2; b = 1; }
      if (2 == s && 0 == x) { d = 2; b = 1; }
      if (2 == s && 1 == x) { d = 0; b = 0; }
      s = d;
      
      printf("%d\n", b);
     
     }
     return 0;
    }

          На Рис. 5 (Граф.pdf) изображен приведенный автомат A/τ , соответствующий рассматриваемому автомату A (Рис. 4, Граф.pdf). По автомату A/τ  составим программу, вычисляющую по каждой входной последовательности x1x... xn слово  g*(,x1x2...xn ), где xi ∈{ 0,1}. Вместо  будем писать просто a.

    Алгоритм вычисления g*(0,x[1]x[2]... x[n]). 

    Вводим n, x[1],x[2],...,x[n]. s= 0. Далее алгоритм выглядит в виде цикла, где i - счетчик цикла. Тело цикла получается в результате обработки  алгоритма:

    если s=0 и x[i]=0, то d=0 и b= 0;

    если s=0 и x[i]=1, то d= 2 и b= 1;

    если s=2 и x[i]=0, то d=2 и b=1;

    если s=2 и x[i]=1, то d=0 и b= 0;

    s=d;

    print b.

    Вариант 1'.
    #include<stdio.h>
    #include<stdlib.h>

    int main(void) {
     int n = 0;
     int s = 0;
     int d = 0;
     int b = 0;
     int * x;
     inti;

     scanf("%d", &n);

     x = (int *)malloc(n * sizeof(int));

     for ( i = 0; i< n; i++) {                              
      scanf("%d", &x[i]);
     }

     for (i = 0; i< n; i++) {          
      if (0 == s && 0 == x[i]) {
       d = 0;
       b = 0;
      }

      if (0 == s && 1 == x[i]) {
       d = 2;
       b = 1;
      }

      if (2 == s && 0 == x[i]) {
       d = 2;
       b = 1;
      }

      if (2 == s && 1 == x[i]) {
       d = 0;
       b = 0;
      }

      s = d;
      printf("%d\n", b);
     }
     
     free(x);
     return 0;
    }

    Вариант 2'.
    //////////////////////////////
    #include<stdio.h>
    #include<stdlib.h>

    int main(void) {
     int n = 0;
     int s = 0;
     int d = 0;
     int b = 0;
     int x;
     inti;

     scanf("%d", &n);

     for (i = 0; i< n; i++) {          
      scanf("%d", &x);
      if (0 == s && 0 == x) {
       d = 0;
       b = 0;
      }

      if (0 == s && 1 == x) {
       d = 2;
       b = 1;
      }

      if (2 == s && 0 == x) {
       d = 2;
       b = 1;
      }

      if (2 == s && 1 == x) {
       d = 0;
       b = 0;
      }

      s = d;
      printf("%d\n", b);
     }
     
     return 0;
    }

         Все программы эквивалентные (т.е. вычисляют одну и ту же функцию). Программа в варианте 1' проще программы из варианта 1,  программа в варианте 2' проще программы из варианта 2.

                                                                                             Вывод.


    Возник метод упрощения программ, соответствующих автомату. Он состоит в следующем: строим приведенный автомат, пишем программу, ему соответствующую. Эта программа эквивалентна предыдущей и более простая.