Спирина, М.С. Дискретная математика

ются все возможные ситуации, встречающиеся при работе этого автомата. Однако при большом числе состояний и входных сигна­ лов таблица переходов становится громоздкой и неудобной в упот­ реблении. Графический способ. Задание с помощью ориентированного гра­ фа —более удобная и компактная форма описания автомата. Граф автомата содержит вершины, соответствующие состоянию q{е Q, а также дуги, соединяющие вершины, — переходы автомата из одного состояния в другое. На дугах принято указывать пары вход­ ных и выходных сигналов — сигналов переходов. Если автомат переходит из состояния qt в состояние qj под во з­ действием нескольких входных сигналов, то на соответствующей дуге графа этот вариант будет представлен через дизъюнкцию. Для представления автомата используют двухполюсные графы с выде­ ленными начальным и конечным состояниями. Задача 44. Опишем работу кодового замка с пятью кнопками. Назовем их А, В, С, D, Е. Замок открывается при нажатии одной кнопки и остается открытым 5 с, причем никакие две кнопки одновременно не набираются. Решение. Множество входных символов содержит 6 элементов: сигналы А, В, С, D, Е — сигналы нажатия соответствующей буквы, и сигнал * — сигнал паузы (кнопка не нажата): X - {А, В, С, D, Е*}. Множество выходных сигналов Y содержит два элемента: 0 — о з ­ начает, что дверь закрыта (замок не открыт), и 1 — замок открыт. Замок открывается при нажатии одной кнопки (например, кн оп ­ ки В), тогда выходной сигнал зависит только от текущего вход­ ного сигнала. Таким образом, любое кодовое слово, имеющее В только в конце, например D*C*A*E*B, открывает замок. У такого замка может быть два состояния: основное q0 — он закрыт и на любые нажатия (кроме В) не реагирует, и состояние, когда он среагировал на В и из q0 перешел в qb а дверь открылась. Далее, удерживая В, автомат остается в состоянии qx\ b{qu В) = q] и Х(Я\, В) = 1. Любое нажатие влечет за собой закрытие двери и переход авто­ мата обратно в q0. Учитывая, что две клавиши одновременно не набираются, клавишу Драно или поздно придется отпустить, тогда будет подаваться *, и дверь закроется. Такой кодовый замок задается табл. 7.3. Т а б л и ц а 7.3 Задание автомата —кодового замка А В с D Е * Яо Яо 1 0 Я\ 1 1 ?о 1о 0о |0 0olO 0olO Я\ ?ol0 я\ U ?olO 0olO 0olO 0olO 349