Вопрос 42. Источник. Источник и регулярный язык. Теорема о детерминации КА.
Теорема : ( детерминация КА). Для любого недетерминированного КАвтомата K=< A,Q,B,?,?> сущ. Эквивалентный ему детерминированный КАвтомат K1=< A,Q,B,?1,?1> имеющий не более чем 2^n состояний ( n=|Q| , |Q1|=2^|Q| =2^n). ДОК-ВО : 1). Кпр=< A,Q,B,?,?> автомат-преобразователь , недетерминированный. Кпр ? Kp ( источник) Кр=< A’,Q,{e},?’,?’>. 2). Процедура детерминации : шаг 1: зафиксируем начал. сос-ние автомата q1, для q1 и для любого a’j?A ( j=1,2, … , |A’j| ). Строим подмножество вершин состояний ? Q , достижимый из Q1 при входном знаке a’j.
Шаг i : получили сис-му подмножеств на i-том шаге для любого вх. знака. Шаг i+1 : для любого мн-ва состояний строим которое достижимо из состояний при входном знаке для всех . Завершаем построение сис-мы подмножеств , если рассмотрены все и не появилось новых подмножеств. { }={ } для всех J. 3). Считаем полученную сис-му мн-в новыми состояниями детерминированного автомата. |Qд|=2^|Q|=2^n. 4). По методу мат. индукции доказать неотличимость этих автоматов К и Кд по длине входных строк. Замечание : 1). Заключит. сост-ниями детерминированного автомата явл. все те сост-я , подмножества сост-ний исходных автоматов которых содержат заключительные сост-я исходного автомата. 2). Может случиться так , что после перехода от источника к автомату- преобразователю он становится недетерминированным по входному знаку. Эта недетерминированность никак не связана с внутренней структурой автомата.
Вопрос 43. Сети из автоматов. Основные виды соединения автоматов. Способы синхронизации в автоматной сети.
Вывод : 1). КА — это модель дискретного преобразователя данных. 2). КА функционирует во времени. 3). Возможно различное соединение автоматов. Сетью из автоматов наз-ся соединение автоматов таким образом, что выходы одних служат входами других и все автоматы в сети функционируют одновременно (согласованно). Замечание : для описания сети из автоматов надо ввести понятие времени, т.к. важно знать в каких состояниях нах-ся каждый из автоматов сети и в какие моменты времени. Основные виды соединения : 1). Параллельное, с общим и с раздельным входом.
K=< A1*A2;Q1*Q2;B1*B2;?;?> K=< A;Q1*Q2;B1*B2;?;?>
2). Последовательное K=< A1;Q1*Q2;B2;???>
3). Соединение с обратной связью K=< A1*B1;Q1;???>
Представленных 3-х видов соединения достаточно для построения любой автоматной сети. Способы введения времени в автоматную сеть : 1). Синхронный : а). Вводиться шкала времени , которая делиться на отрезки одинаковой длины ( такты), которые нумеруются с 0.
б). Длина такта принимается за единицу измерения времени в). Входные и вых. строки ?= ai1,ai2, … , aik ; ?=bj1, bj2, … , bjk ; bj?B , ai?A рассматриваем как последовательность знаков сменяемых каждый такт. г). Автоматные ф-ции реализуются с задержкой q(t)?Q , a(t)?? , b(t)?? , t?{0,1, … ,}? ?;
??(q(t), a(t))=q(t+1) автомат Мили : ?(q(t),a(t))=b(t) ; автомат Мура ?(q(t),a(t))=b(t+1) д). Синхронизация работы автоматов в сети достигается за счет : ? внешнего источника синхронизации , ? идеальных временных характеристик среды и автоматов. 2). Асинхронный. Опред : состояние qi явл-ся устойчивым по входному знаку aj, если ?(qi, aj)=?(qi, aj aj)
В асинхронном автомате любое состояние устойчиво по любому входному знаку ведущему в это состояние.
Вопрос 44. Комбинационный автомат. Теорема о комбинационном автомате.
Комбинационный автомат — это конечный автомат , у которого для любого входного знака a и для любых двух входных состояний qi и qj выполняется следующее условие : ?(qi , a)=?(qj , a) { выходной знак зависит только от входного знака и не зависит от состояния}. Теорема : Любой автомат эквивалентен автомату Мили с одним состоянием Кмили = < A,{q}, B, ???> или автомату Мура с m-состояниями Кмура = < A, Qm, B, ???> , где m=|A|=|Qm|. ДОК-ВО : 1). Методом мат. индукции по длине входной строки ? можно показать , что для ?q?Q автоматное отражение K(qi, ?k)=K(qj, ?k), что по определению о неотличимых состояниях соответствует тому, что qi неотличимо от qj для ?qi и qj. 2). Т.к. все состояния неотличимы от некоторого qi , то применяя алгоритм Мили (минимизация) получим автомат с одним состоянием. 3). Построим для полученного min автомата неотличимый от него автомат Мура, |Qm|=n*m+n=|A|*|Q’|+|Q’|=|A|+1. Одно состояние появилось в рез-те неопределенности начального состояния автомата Мура. Доопределим состояние выхода для начального состояния как b1?B. В этом случае q10 и q1b1 явл. неотличимыми, где q10- начал. сост-е => этот автомат минимизируется до автомата Мура с m состояниями m=|Qm|=|A|. Замечание — любой комбинационный автомат может быть представлен как автомат = < A,{q},B,?> , где ?- функция состояния выхода =< A,B,?> ; ? : A*Q? {q1}, т.е. ? постоянна.
