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

Автомат является комбинационным. Задача 45. Описать работу кодового замка, состоящего из пяти последовательно нажимаемых кнопок, который открывается при нажатии двух кнопок. Решение. Пусть кодовый замок с пятью кнопками открывается при последовательном нажатии двух кнопок, например кнопок В и D. Таким образом, для открытия замка необходим набор симво­ лов В, *, D, причем, пока кнопка D нажата, замок открыт. Для задания состояний такого кодового замка-автомата составим таб­ лицу переходов и выходов (табл. 7.4). Эта таблица показывает, что на пересечении q, строки и Xj столб­ ца наш автомат находится в состоянии 8(q„ а) и X(qh aj), что мож­ но задать аналитически. Перечислим эти состояния: S(fe В) =q2 и X(q2, В) = 0; 8(<?з> *) = 9з и X(qb *) = 0; 8(q4, D) =q4 и X(q4, D) = 1 — т.е. замок открылся. Для всех других входных сигналов А, С и Е выполняется 8(qx, A)=qi и X(qx, Л) = 0, 8 (qu С) = <?, и X(qx, С) = 0, 5 (qx, E ) = q x и X(qu Е) = 0. Этот автомат можно представить в виде диаграммы — ориен­ тированного графа. Граф состояний такого автомата содержит 4 вершины — состояния <?, и дуги, соответствующие переходу ав­ томата из состояния q в состояние qj. На дугах такого ориентиро­ ванного графа указывают входной сигнал, вызывающий этот пе­ реход, и выходной сигнал как результаты, которые отделяются друг от друга вертикальной чертой (рис. 7.2). Такой ориентированный взвешенный граф наглядно демонст­ рирует путь для отпирания замка, т.е. необходимую последова­ тельность символов {В, *, D }. Заметим, что если считать уже на­ жатую клавишу поступающим входным сигналом, то, во-первых, кодом для открытия будут слова вида B...B*...*D...D, во-вторых, в таблице перехода появятся 8 (q2, В) = q2 и т.д., в-третьих, анало­ гичные петли появятся и в графе на рис. 7.2. В таком случае, даже Таблица 7.4 Таблица переходов автомата — кодового замка Состояния Входы А В С D Е * 91 9110 9210 9i 10 9i 10 9i 10 9i 10 92 9i 10 9i 10 9i 10 9i 10 9i 10 9з 10 9з 9i 10 9110 9i 10 9411 9i 10 9i 10 94 9i 10 9i 10 9i 10 94 11 9i 10 9i 10 350