Вопрос 36. Теорема о минимизации КА. Алгоритм Мили.
Эквивалентным преобразованием называется переход от автомата K к автомату K’ который неотличим от исходного. Постановка задачи минимизации : среди автоматов неотличимых от автомата K найти автомат Ko с наименьшим числом состояний. 
Теорема 3.1. : Для любого автомата K существует эквивалентный ему минимальный автомат Ko с точностью до изоморфизма , имеющий L состояний , если множество состояний Q разбивается на L классов эквивалентности. ДОК-ВО : 1). Пусть задан КА K и множество его состояний разбито на L классов его эквивалентности : С1={q11, q12, … , q1i1 } C2={q21, q22, … , q2i2} … CL= {qL1, qL2, … , qLiL}. Два состояния q и q’ принадлежат одному классу эквивалентности, если эти состояния неотличимы. 2) Тогда для любого a ? A+ ,(где A- множество входных знаков автомата) и состояний q , q’ ? Q и qi1, qi2 ?. Ci , состояния ?( qi1, a) и ?(qi2, a) также ? одному классу эквивалентности CK . ? ( qi1, a ) и ? (qi2, a ) неотличимы , т.к. они принадлежат одному классу эквивалентности Cк. Предположим что они отличны, тогда существует некоторая строка ??? A+ , которую подаем на вход нашего автомата, то на выходе K1 (qi1, ? ) =K2 (qi2, ? ) ; ? ( qi1, ??a )=? (? (qi1, ????a )= ? ( qi2, ??a) может найтись некоторая строка ? , для которой текущее состояние автомата ? одному и тому же классу эквивалентности. ? ( ? (qi2, ? ), a ). 3). Определим минимальный автомат K0=<A, Q0, B,?0, ? 0>. Обозначим Q0 — как множество классов эквивалентности : Q0={C1,C2,…,CL} ?0( Ci , aj ) = Ck, где Cк — класс эквивалентности , в который входит ?( qi, aj )=qk. 4). Покажем что этот автомат является минимальным : Kо — неотличим от K, Ci qi . Докажем что Kо является минимальным. Предположим что Kо не минимален, тогда существует автомат Kо’ с меньшим числом состояний. | Qo | < L. Существует как ( у Ко) минимум 2 состояния, которые неотличимы, а это значит, что 2 класса эквивалентности являются неотличимы, что противоречит условию теоремы. Значит автомат Kо — является минимальным. 5 ). Докажем , что любой другой минимальный автомат Ko’ будет изоморфен автомату Kо. Ko’ и Ko неотличимы и имеют одинаковое количество состояний. Если это так то тогда мы имеем право переименовать состояния как хотим.
Алгоритм Мили: (построение классов эквивалентности): Шаг1: Разбиваем множество состояний Q некоторого автомата K=<A, Q, B, ?, ??? на классы следующим образом. Два различных состояния q и q’ относим в один и тот же класс эквивалентности Ci1,если для всех a ? A, ?(q, a) = ?(q’ , a). Шаг i: Получено разбиение на n — классов эквивалентности . Шаг i+1 : Два состояния q и q’ из одного класса эквивалентности Cji относим в один класс Cji+1 , если для любого входного знака нашего автомата ??q, a) и ?(q’ , a) ? одному и тому же классу. Иначе образуем новый класс CK+1i+1 куда заносим состояния q’ , а так же все остальные q из множества Cji для которых ?(q, a) и ?(q’ , a) принадлежат одному классу. Условие завершения процедуры : Если на i+1 шаге получим разбиение, которое не уменьшилось по отношению к i шагу .

Вопрос 37. Определение автомата Мура. Теорема о существовании АМ.
Автоматом Мура называется конечный автомат , у которого функции выхода не зависят от входного знака (зависит только от состояния автомата).K=<A, Q, B, ?, ? >. Для любого qi принадлежащего Q и для любого aj1, aj2 принадлежащего A. ?( qi, aj1) = ? (qi, aj2) — это означает что функция ? является одноаргументной функцией и зависит только лишь от состояния автомата. Обозначим эту функцию ?? Km=< A, Q, B, ?, ??> , ? : Q ? B ( иногда ? называют — функцией отметок). Состояние выхода можно записать в самой системе.
Теорема 3.2. Для любого автомата Мили существует неотличимый от него автомат Мура. ДОК-ВО : 1). Задан некоторый автомат K=< A, Q, B, ?, ? >. Определим исходные множества на которых задан автомат в общем виде : A={a1, a2, … , am} Q={q1, q2, … , qn}. 2). Построим АМ эквивалентный K, где АМ зададим :Km =< Am, Qm, Bm, ?m??????Зададим определение алфавитов : Am=A, Bm=B, Qm={q10, q20, … , qn0, q11,q12, … , q1m, q21,q22, … , q2m, … , qnm}. Задаем : ?m(qi0, aK)=qiK ; ?m (qij, aj)=qLK , где L вычисляется ?(qi, aj )=qL ; ? ( qi 0 )-неопределенна ; ? (qij ) = ? (qi, aj) ; i =1, n ; j =1, m .
3). Докажем что построенный АМ неотличим от исходного автомата Мили : для любого qi ?Q и для любой ? ? A+, K(qi, ?)=Km( qi0, ? ); имеется соответствие qi ? qi 0, т.е. эти состояния соответствуют друг другу. Доказательство приведем путем индукции по длине строки ? шаг 1: длина |?? |=1, и ? = aj ; K( qi, aj) = ?( qi, aj ) = ? ( qij ) ; Km ( qi0, aj )= ? ( ?m ( qi0,aj ) ) = ? ( qij ); шаг p : Предположим что для строки |?p| длина = p , ?p = aj … ak ; K( qi, aj … ak) = ? ( qij ) … ? ( qSK ) ; шаг p+1 : обозначим ? (qS , aK) = qT; ? (qT , aL) = qU ; K( qi, aj … aK, aL)=Km( qi0, aj … aK , aL) ; Пусть K( qi, aj … aK , aL)=? ( qi, aj) … ? ( qS, aK)*? ( qT,aL) Посмотрим каким образом АМ переработает новую строку : Km ( qi0, aj … aKaL ) = ? ( qij ) … ? ( qSK )* ? ( ?m ( qSK, aL) ) ; ? ( ?m ( qSK, aL) )= ? ( qtL) = ? ( qT, aL) . Вывод : получили АМ. Замечание 1: для исследования возможностей КА достаточно рассматривать более простой АМ. Замечание 2 : Без потери общности можно считать , что алфавит отметок состоит из P- знаков , которые делят множество состояний на P непересекающихся подмножеств. В этом случае КА можно задать не ограничивая общности , как : K= < A, Q, B, Q1, Q2, … , Qp >

Вопрос 38. . Построение АМ.
Построим АМ эквивалентный K, где АМ зададим :Km =< Am, Qm, Bm, ?m,?????Зададим определение алфавитов : Am=A, Bm=B, Qm={q10, q20, … , qn0, q11,q12, … , q1m, q21,q22, … , q2m, … , qnm}. Задаем : ?m(qi0, aK)=qiK ; ?m (qij, aj)=qLK , где L вычисляется ?(qi, aj )=qL ; ? ( qi 0 )-неопределенна ; ? (qij ) = ? (qi, aj) ; i =1, n ; j =1, m .