В.А. Кутыркин, А.Ю. Бушуев Элементы теории автоматов и формальных языков. (В.А. Кутыркин, А.Ю. - Бушуев Элементы теории автоматов и формальных языков. 2014), страница 6

конечные автоматы Мили с одним состоянием. Анализу и синтезутаких дискретных преобразователей и посвящён настоящий раздел. Важность дискретныхпреобразователей обусловлена тем, что на их основе разрабатываются принципы синтезаконечных детерминированных автоматов. К типу дискретных преобразователей относятсялогические схемы из функциональных элементов и контактные (переключательные)схемы.Диаграммы логических схем из функциональных элементов и контактных(переключательных) схем строятся на основе орграфов, называемых логическими иконтактнымисетями,соответственно.Крометого,анализконтактнойсхемыосуществляется на основе специального орграфа, называемого деревом анализаконтактной схемы.

Краткое изложение теории графов, необходимое для описаниялогических и контактных сетей приведено в разделе 3.5.1. Логические схемы из функциональных элементовЛогическая схема из функциональных элементов реализует дискретный преобразователь,поскольку она является автоматом с одним состоянием. Входным алфавитом такойлогическойAn2схемы1 ,..., nявляется:1 ,..., nсловарь20,1 } , гдебулева алгебра (булев 1-куб). Алфавит её выхода Bn -мерных2( 0,1 ,булевыхкортежей, , , 0,1 ) – стандартная2.Диаграммой логической схемы представляется в виде логической сети (см.определение 3.3) с n источниками и одним стоком. Каждый из n источников логическойОглавление oglavЭлементы теории автоматов и формальных языковВ.А.

Кутыркин, А.Ю. Бушуев33сети помечен одной из булевых переменных x1,...., xn так, что эти пометки попарноразличны для разных источников. Каждая из остальных вершин этой сети помечена однимиз логических функциональных знаков:знаком дизъюнкции(конъюнкции,,. При этом вершины, помеченные,), имеют позитивную валентность, равную двум;вершины, помеченные знаком логического отрицания(равенства), имеют единичнуюпозитивную валентность. Пометки вершин диаграммы логической схемы, иллюстрируютработу этой схемы. На первом такте работы схемы на её вход подаётся булев n -мерныйкортеж1,..., nn2и булевым переменным, помечающим источники сетилогической схемы, присваиваются значения: x11,...., xnn.Пометки других вершиндиаграммы иллюстрируют работу функциональных элементов логической схемы:дизъюнктора (помечен знакомзнаком), конъюнктора (помечен знаком) и дублятора-задержки (помечен знаком), инвертора (помечен).С помощью диаграммы логической схемы описывается её работа по реализациибулевой функции ff ( x1 ,...., xn ) :n22,называемой пропускной способностью этойлогической схемы.На рис.

12 для логической схемы с тремя источниками на примере её диаграммыпроиллюстрирована потактовая работа этой схемы, реализующей булеву функциюf( x1x2 ) x2 x3 .Рис.12Замечание 5.1. Логическая схема из функциональных элементов, диаграмма которойприведена на рис. 12, работает потактово. Для соблюдения этого требования на этойдиаграмме указан дублятор, иллюстрирующий задержку на один такт работы в этомфункциональном элементе схемы. Кроме того, диаграмма на рис. 12 иллюстрируетметоды анализа и синтеза логической схемы из функциональных элементов.►Оглавление oglavЭлементы теории автоматов и формальных языковВ.А.

Кутыркин, А.Ю. Бушуев34Пример 5.1. В настоящем примере демонстрируется описание канонических уравненийконечного автомата Мили на основе булевых функций, с помощью которых работуавтомата возможно реализовать логическими схемами из функциональных элементов. Дляэтого рассмотрим автомат( A, B,V , , ) , в котором Vv1 , v2 , v3 , v4– словарь егосостояний и, кроме того, алфавиты входа и выхода совпадают и имеют вид: Aa, bB.Работу этого автомата описывает таблица 7.Таблица 7aСменимобозначенияbv1v3av2v1bv2av3v1av1bv4v2bv3aсостоянийибуквv4bалфавитавходаивыходаавтомата( A, B,V , , ) следующим образом. Буквы a и b заменим на символы 0 и 1,соответственно, получив в качестве алфавитов входа и выхода алфавиты A1СловарьVсостоянийv1 , v2 , v3 , v4соответствующий словарь V11автомата( A, B,V , , )1заменимТаблица 8x100001111V1x200110011на( A, B,V , , ) , если работа( A1, B1,V1, , ) описывается, в соответствии с таблицей 7, таблицей 8.A1B1 .(0, 0), (0,1), (1, 0), (1,1) .

В результате получится автомат( A1, B1,V1, , ) , фактически, реализующий автоматавтоматаa, bx312010101011000100100011100Оглавление oglavЭлементы теории автоматов и формальных языковВ.А. Кутыркин, А.Ю. Бушуев0101101035Таким образом, работа автомата1( A1, B1,V1, , ) описывается двумерной булевойфункцией перехода по состояниям( x1, x2 , x3 ) ( 1 ( x1, x2 , x3 ), 2 ( x1, x2 , x3 )) и булевойфункцией( x1 , x2 , x3 ) , которые определены таблицей 8. Из таблицы 8 получаем:1x1x2 x3x1x2 x3x1x2 x3x1x2 x3x2 x3 ,2x1x2 x3x1x2 x3x1x2 x3x1x2x1x2 x3 ,x1x2 x3x1x3x1x2 x3x1x2 x3x1x2 x3Следовательно, автоматx1x3 .( A, B,V , , ) с помощью автомата1( A1, B1,V1, , ) можносинтезировать, используя логические схемы из функциональных элементов.►Упражнение 5.1.

Синтезировать работу автомата( A1, B1,V1, , ) из примера 5.1 с1помощью логических схем из функциональных элементов, построив для этогосоответствующие диаграммы логических схем.►5.2. Контактные схемыПусть Gr (V ; q, e) – контактная сеть (см. определение 3.4) и( x1 , x1 , x2 , x2 ,..., xn , xn ) –список булевых переменных и их отрицаний. Как и ранее, R (V ; ) – совокупность рёберсети Gr (V ; q, e) и задано отображение.

Тогда говорят, что определена: R(V , )контактная (переключательная) схема Gr (V ; q, e) .Рассмотрим совокупность путей( q; e) в сети Gr (V ; q, e) с началом во входнойвершине q V и с окончанием в заключительной вершине e V . Путь( q , e)представляем в виде списка его последовательных ребер:({q, v1},{v1, v2},...,{vk 2 , vk 1},{vk 1, e}) .Такому путипоставим в соответствие конъюнкцию:( )где2({q, v1}) ({v1, v2})... ({vk 1, e})2[ x1, x2 ,..., xn ] ,[ x1,..., xn ] – булева алгебра булевых функций от n булевых переменных x1 ,..., xn .Тем самым, отображениерасширяется до отображенияОглавление oglavЭлементы теории автоматов и формальных языковВ.А. Кутыркин, А.Ю. Бушуев: (q, e)2[ x1, x2 ,..., xn ] .36Определение 5.1 Пропускной способностью контактной схемы Gr (V ; q, e) называетсябулева функция f2[ x1 ,..., xn ] вида f( ) .►( q , e)Но, для того чтобы, согласно определению 5.1, вычислить пропускную способность( ) контактной схемы Gr (V ; q, e) , необходимо рассмотреть бесконечнуюf( q , e)совокупность путей( q, e) .

Оказывается, что для вычисления этой пропускнойспособности достаточно ограничиться подсовокупностью(путей, не содержащих циклы) среди путей совокупности0(q, e) – простых путей( q, e) . Совокупность0(q, e) ,вследствие конечности контактной схемы, также является конечной и допускает, какбудет показано далее, алгоритм её перебора без повторений.Теорема 5.1 (о вычислении пропускной способности контактной схемы). Пропускнаяспособность контактной схемы Gr (V ; q, e) вычисляется согласно формуле:( ) .►f0 ( q , e)На практике возникает и другая задача. По заданной пропускной способностисоздать контактную схему, её реализующую.

Такая задача называется задачей синтезаконтактной схемы.Пример5.2(плоско-параллельнойконтактнойконтактную схему с пропускной способностью fсхемы).x1 x 2 x 3Требуетсяx1 x 2 x 3x1 x 2 x 3синтезировать2[ x1 , x 2 , x 3 ] .На рис. 13 показана диаграмма контактной схемы с такой пропускной способностью. Этасхема называется плоско-параллельной.►Рис.13Оглавление oglavЭлементы теории автоматов и формальных языковВ.А.

Кутыркин, А.Ю. БушуевРис.1437Для любой булевой функции, представленной её дизъюнктивной нормальнойформой (ДНФ), в частности, – совершенной дизъюнктивной нормальной формой (СДНФ),плоско-параллельная контактная схема легко конструируется. Однако, такая контактнаясхема, как правило, не является оптимальной с точки зрения минимизации количества еёвершин и рёбер. Более оптимальным синтезом контактной схемы является методкаскадов, изложению которого посвящён следующий раздел.5.2.1. Синтез контактной схемы методом каскадовМетод каскадов для синтеза неизвестной контактной схемы с заданной пропускнойспособности осуществляется индуктивно.Пусть f2[ x1 ,..., xn ] – пропускная способность неизвестной контактной схемыGr (V ; q, e) , которую необходимо построить.Далее предполагается, что функцияfпредставлена полиномом Жегалкина,зависящим от всех булевых переменных x1 , x2 , …, xn .

Тогда алгоритм метода каскадовдля синтеза неизвестной контактной схемы Gr (V ; q, e) имеет следующий вид.Первый шаг. Создаем входную вершину q V и две другие различные вершиныv1, v2 V . Новому ребру {q, v1} R(V , ) ставим в соответствие перемененную x1 , новомуребру {q, v2} R(V , ) – переменную x 1 . После этого вершину v1 помечаем полиномомЖегалкина функции f1 ( x2 ,..., xn )функции f0 ( x2 ,..., xn )f (1, x2 ,..., xn )f (0, x2 ,..., xn )p1 , вершину v2 – полиномом Жегалкинаp2 .

Если p10 ( p20 ), то вершину v1 ( v2 ) ивходящее в неё новое ребро уничтожаем. Если p1 1 ( p21 ), то вершину v1 ( v2 )отождествляем с заключительной вершиной e V , т.е. полагаем v1e ( v2e ).…………………………………………………………………………………………Текущий шаг. Пусть для переменных x1 , x1 ,..., xk 1 , xk 1 , построена часть схемыGr (V ; q, e) , в которой есть вершина v V , помеченная полиномом Жегалкина p отпеременных xk ,..., xn и зависящим от переменной xk – существенно. Тогда для вершины vОглавление oglavЭлементы теории автоматов и формальных языковВ.А. Кутыркин, А.Ю. Бушуев38создаем две новые вершины w1 , w2 V . Новое ребро {v, w1} R(v; ) помечаем переменнойxk , новое ребро {v, w2 } – переменной xk . Кроме того, вершину w1 ( w2 ) помечаемполиномом p1 ( p2 ), полученным подстановкой в переменную xk полинома p числа 1(числа 0 ).

Если оказалось, что p10 ( p2новое ребро уничтожаем. Если же p1 1 ( p20 ), то вершину w1 ( w2 ) и входящее в неё1 ), то вершину w1 ( w2 ) отождествляем сзаключительной вершиной e V , т.е. полагаем w1e ( w2e ). Кроме того, если средиуже ранее построенных вершин есть такая вершина w , что p1q ( p2q ), где q –полином, помечающий вершину w , то в этом случае вершину w1 ( w2 ) отождествляемвершиной w , т.е. полагаем w1w ( w2w ).…………………………………………………………………………………………Заключительный шаг. Процесс метода каскадов заканчивается тогда, когдастановится невозможным построения новых вершин для синтезируемой контактнойсхемы.Пример 5.3 (синтеза контактной схемы методом каскадов).