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

Двухвходовым триггером называют автомат, имеющий два вхо­ да X] и х2, который может также находиться в двух состояниях 0 О и 0 , . Его граф имеет вид, изображенный на рис. 7.4, 6. Автомат, получив на входе х х сигнал 1, перешел из состояния 0о в состояние 0 , (запись) и на выходе выдает сигнал 1. Получив сигнал 1 на входе х2, автомат переходит из состояния 0 , в состо­ яние 0о (сброс), а на выходе при этом выдается сигнал 0, причем одновременная подача единиц на оба входа и х2 невозможна. Имея минимальный набор элементов, например И, ИЛИ, НЕ , а также элементы памяти — задержку и триггеры, можно постро­ ить любую логическую схему, а значит, и любой конечный авто­ мат. Проектируя автомат как техническое устройство, мы осуще­ ствляем процесс перехода от описания его свойств к синтезу л о ­ гической схемы, соответствующей заданным свойствам. Причем в теории автоматов разработаны специальные алгоритмические м е ­ тоды и программы для автоматизации процесса синтеза логичес­ ких схем. Такой способ синтеза логических схем называют аппаратным, так как его результатом является создание конкретной электрон­ ной аппаратуры. Существует также программный способ синтеза логических схем, по которому создается не сама логическая схема, а программа, ей соответствующая. Очевидно, конечный автомат является частным случаем алго­ ритма, в частности алгоритма с конечной памятью, что соответ­ ствует конечному числу состояний автомата. ? Какие перспективы и применения имеет теория конечных автоматов? Благодаря исследованиям в области теории автоматов матема­ тика пополнилась новым направлением, связанным с понятием сложности некоторой системы. Выдающийся американский математик XX в., венгр по проис­ хождению, Джон фон Нейман использовал язык автоматов для описания основных законов взаимодействия сложных систем, т. е. как метаязык кибернетики. Впоследствии М .Л .Ц етлин , иссле­ дуя задачи целесообразности поведения взаимодействующих объектов, рассматривал их как задачи коллективного поведения автоматов. В своих исследованиях для описания поведения любых объектов, в том числе и живых, он использовал термины языка конечных автоматов. Новые научные направления «теория коллективного поведения автоматов» и «поведение автоматов в случайных средах» опирают­ ся на тактику поведения обычных конечных автоматов. Изучены условия, характеризующие их способность к адаптации в стацио­ нарных и нестационарных средах. 355