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

Требуется синтезироватьметодом каскадов контактную схему с пропускной способностью f из примера 5.2.Следовательно:fгдеx1 x 2 x 3x1 x 2 x 3x1 x 2 x 3x1 x 2x1 x 3 x 2 x 3 x1x 2 x 3 ,– знак операции сложения по модулю два. На рис. 14 проиллюстрирован процесссинтеза искомой контактной схемы методом каскадов. Сравнение диаграмм на рис. 13 ирис. 14 показывает, что метод каскадов является более оптимальным, чем синтез плоскопараллельной контактной схемы.►5.2.2.

Дерево анализа контактной схемыВ настоящем разделе рассматривается задача анализа заданной контактной схемыGr (V ; q, e)с неизвестной пропускной способностьюf2[ x1 ,..., xn ] , которуютребуется вычислить. Решение этой задачи осуществляется на основе алгоритмапостроениядереваанализаконтактнойсхемы,Оглавление oglavЭлементы теории автоматов и формальных языковВ.А. Кутыркин, А.Ю. Бушуевдиаграммакоторогопозволяет39перечислить все простые пути этой схемы, связывающие её вход и выход и,следовательно, вычислить искомую пропускную способность заданной контактной схемыGr (V ; q, e) .

Алгоритм построения такого дерева анализа описывается следующимобразом.Первый шаг. Создаём корень дерева текущего дерева анализа Drv , помечая еговершину входной вершиной q схемы Gr (V ; q, e) . Кроме того, из этого корня выпускаемy1ориентированные рёбра qykv1 ,..., qvk , где v1 ,..., vk – список всех попарноразличных вершин, смежных в схеме Gr (V ; q, e) с её входной вершиной q , и каждоереброyjXrjq{q, v j } R(V , )этой( x1 , x1 ,..., xn , xn ) .yjсхемыКромедляj 1, kтого,помеченоокончаниембулевойпеременнойориентированногоребраv j в создаваемом текущем дереве Drv является лист, помеченный вершинойv j схемы Gr (V ; q, e) для j 1, k . Такой лист называется заключительным листом, еслион помечен вершиной выхода e этой контактной схемы.

Другие листы так построенноготекущего дерева Drv анализа называются свободными.Второй шаг. Если в текущем дереве анализа Drv нет свободных листов, то выходимиз алгоритма с результатом в виде диаграммы этого текущего дерева. В противном случаепереходим к следующему шагу алгоритма.Третий шаг. Рассматривается свободный лист текущего дерева анализа Drv ,помеченный вершиной v схемы Gr (V ; q, e) .

Из этого листа выпускаем новыеy1ориентированные рёбра vykv1 ,..., vvk , где v1 ,..., vk – список всех попарноразличных вершин, смежных в схеме Gr (V ; q, e) с рассматриваемым листом, и каждоереброyjXrjq{v, v j } R(V , )этойсхемыдляj 1, kпомеченобулевойпеременной( x1 , x1 ,..., xn , xn ) . Кроме того, для j 1, k окончанием ориентированного ребраyjv j в дополняемом текущем дереве Drv является новый лист, помеченныйвершиной v j схемы Gr (V ; q, e) .

От корня дерева до этого нового листа существуетединственный( ) u1 u 2путь... u m(qu1w1 , w10 или путьu2w2 ,..., vumvj ).Есликонъюнкция(q, w1 , w2 ,..., wm 1, v, v j ) в схеме Gr (V ; q, e) неявляется простым, т.е. содержит цикл, то этот новый лист называется запрещённым и наОглавление oglavЭлементы теории автоматов и формальных языковВ.А. Кутыркин, А.Ю. Бушуев40диаграмме дополненного текущего дерева фон кружочка этого листа затемняется. Еслисреди оставшихся новых листов есть листы, помеченные вершиной выхода e контактнойсхемы Gr (V ; q, e) , то такие новые листы называются заключительными листамидополненного текущего дерева.

Новый лист, не являющийся заключительным изапрещённым, называется свободным листом дополненного текущего дерева. После этоготак дополненное дерево объявляется текущим деревом анализа Drv и происходит переходко второму шагу алгоритма.Пример 5.4 (анализа контактной схемы). На основе приведённого выше алгоритма дляконтактной схемы Gr (V ; q, e) , диаграмма которой показана на рис. 14, построенодерево анализа этой контактной схемы. Диаграмма этого дерева анализа показана нарис. 15.Рис.15На диаграмме дерева анализа, показанной на рис. 15, трём заключительным листамсоответствуют три пути, связывающие корень дерева с этими листьями:1(q2(q3(qx1x1x1v2 , v2v1 , v1v1 , v1x2x2x2v4 , v4v4 , v4v3 , v3x3x3x3Оглавление oglavЭлементы теории автоматов и формальных языковВ.А.

Кутыркин, А.Ю. Бушуевe) ,e) ,e) .41Эти пути можно интерпретировать и как пути в рассматриваемой контактной схемеGr (V ; q, e) . Тогда0(q, e) { 1,2 , 3}– совокупность всех простых путей в этойконтактной схеме. Следовательно, согласно теореме 5.1, её пропускная способностьf( 1)(2)(3)x1x2 x3x1x2 x3x1x2 x3 и найдена правильно, согласно примеру5.3.►Упражнение 5.2. Для контактной схемы, показанной на рис. 16, построить дерево анализаи найти её пропускную способность. Затем, используя метод каскадов синтезироватьконтактную схему с этой пропускной способностью, сравнив её с заданной.►Рис.166. Вопросы для самопроверки1. Универсальный и позитивный языки алфавита.

Понятие формального языка и еголексикографического словаря.2. Вычисление номера слова в словаре позитивного языка и алгоритм определения словапо его номеру.4. Понятие ориентированного графа и способы его задания, классификация вершин ипутей в орграфе.5. Классификация орграфов.6. Деревья и логические сети.7. Понятие неориентированного графа и способы его задания, классификация вершин ипутей в орграфе.8.

Понятие контактной сети.Оглавление oglavЭлементы теории автоматов и формальных языковВ.А. Кутыркин, А.Ю. Бушуев429. Понятия автоматов Мили и Мура. Классификация автоматов.10. Способы представления конечных автоматов и описание их работы.11. Понятия автоматного отображения и эквивалентности состояний для автоматов Мура.12. Понятие приведённого автомата. Алгоритм минимизации конечного автомата Мура посостояниям.13. Понятие логической схемы из функциональных элементов, её анализ и синтез.14. Понятия контактной схемы и её пропускной способности.15. Плоскопараллельные контактные схемы.16.

Алгоритм синтеза контактной схемы на основе метода каскадов.17. Понятие анализа контактной схемы и вычисление её пропускной способности толькона основе простых путей, связывающих её вход и выход.18. Алгоритм построения дерева анализа контактной схемы и вычисление её пропускнойспособности.7.

Индивидуальные домашние заданияЗадача 1По номеру №(x) = 1450 - 15 N слова x (N – номер фамилии студента в журналегруппы) в лексикографическом словаре позитивного языка над упорядоченным алфавитомA = a, b,c,d, t,f определить это слово и проверить результат вычисления.Задача 2Найти СДНФ, СКНФ и полином Жегалкина булевой функции f от четырёхпеременных, заданной таблицей:X100000000X200001111X300110011Оглавление oglavЭлементы теории автоматов и формальных языковВ.А. Кутыркин, А.Ю. БушуевX401010101fB1B2B3B4B5B6B7B84311111111Втаблице000011110011001101010101B9B10B11B12B13B14B15B16B1B2B3B4B5B6B7B8B9B10B11B12B13B14B15B16–двоичнаязаписьнатурального числа 215+19N, где N – номер фамилии студента в журнале группы.

Есливозможно, сократить запись совершенной нормальной формы и сделать проверку,используя таблицу истинности.Задача 3Синтезировать булеву функцию из предыдущей задачи 2 с помощью логическойсхемыизстандартныхфункциональныхэлементов(дублятора,дизъюнктора,конъюнктора и инвертора). Провести анализ результата и представить его в видесоответствующего графа.Задача 4Методом каскадов синтезировать контактную (переключательную) схему длябулевой функции из задачи 2. Провести проверку результата, используя диаграмму дереваанализа, и представить его в виде соответствующего графа.Задача 5Длятабличнозаданного,инициальногодетерминированногоавтомата,сначальным состоянием 1 (см. Приложение 1, N – номер фамилии студента в журналегруппы и номер его автомата), по входному слову AABCBBACCB найти соответствующеевыходное слово и цепочку переходов состояний автомата при переработке этого входногослова (переходы по состояниям представить графически, отмечая дуги переходов посостояниям соответствующим входным символом).Задача 6Оглавление oglavЭлементы теории автоматов и формальных языковВ.А.

Кутыркин, А.Ю. Бушуев44Для таблично заданного автомата (см. Приложение 1, N – номер фамилии студентав журнале группы и номер его автомата), используя соответствующие булевы функции,написать канонические уравнения, его определяющие. Реализовать выхода автомата ввиде контактных схем из функциональных элементов, проиллюстрировав их графически исделав их анализ с помощью дерева анализа.Задача 7Минимизировать по состояниям таблично заданный детерминированный автомат(см. Приложение 1, N – номер фамилии студента в журнале группы и номер его автомата).Результатпроиллюстрироватьграфически,приведядиаграммыисходногоиминимизированного автомата. Кроме того, выбрав входное слово, длины не менее 10,показать совпадение выходов исходного и минимизированного автомата, выбравсоответствующие начальные состояния.Оглавление oglavЭлементы теории автоматов и формальных языковВ.А.

Кутыркин, А.Ю. Бушуев45Приложение 11.4.ABCABC1 6A5B3B18C2B4B2 1C4A6A25A1C8A3 7A3B1B34B8A3A4 5C2A7A47B1A5A5 8A1B5B53B1A4A6 2C8A3A67A8C1A7 4C8A5A75B8A7A8 4C6A1A81C6B3B2.5.ABCABC13B6C1A14C5B3A28C7B2A25A7A8B35B8C3A31A4A2B48C1B5A47C2B1A53B8C4A57C1B8A68C7B3A64C6B2A75B2C1A74C8B5A88A6B3C86A7A3B3.6.ABCABC12B5B2A13A4C7B23C6A7B23A5C6B35B8B8A31B2A5C46A4C1C46A1C7B51C4A7B53A5C8B64A4C3C65B2A1C71B2B4A74B6A2C83C4A7B81B3A2CОглавление oglavЭлементы теории автоматов и формальных языковВ.А. Кутыркин, А.Ю. Бушуев467.10.ABCABC16B5A3A13B6A1C21C4B6B28A7B3C37B3A1A35B8A2C45C2B7B48A1B5C58B1A5A53B8A4C62C8B3B68A7B3C74C8B5B75B2A1C84C6B1B88C6B3A8.11.ABCABC13C6B1A12C5C2B28B7C2A23A6B7C35C8B3A35C8C8B48B1C5A46B4A1A53C8B4A51A4B7C68B7C3A64B4A3A75C2B1A71C2C4B88A6C3B83A4B7C9.12.ABCABC16A5C3C18B2A4A21B4A6A25C1B8C37A3C1C34A8C3C45B2A7A47A1C5C58A1C5C53A1C4C62B8A3A67C8B1C74B8A5A75A8C7C84B6A1A81B6A3AОглавление oglavЭлементы теории автоматов и формальных языковВ.А.