Строки этих таблиц соответствуют входам, а столбцы – состояниям автомата. На пересечении столбца ai и строки zj в таблице переходов ставится состояние ak, в которое автомат приходит из состояния ai под воздействием сигнала zj, а в таблице переходов – соответствующий этому переходу выходной сигнал wk.
Автомат Мура описывается одной таблицей переходов, в которой каждому столбцу приписан кроме состояния ещё и выходной сигнал.
Задание автоматов графами переходов имеет преимущество большей наглядности и понятности. Граф переходов автомата Мили, соответствующий табл. 1 и 2, показан на рис. 2.
Рис. 2. Граф переходов автомата
Граф автомата – ориентированный граф, вершины которого соответствуют состояниям автомата, а дуги – переходам между ними. В вершинах указывается обозначение состояния, а для автоматов Мура – ещё и выходной сигнал в данном состоянии. На дугах для автоматов Мили отмечается выходной сигнал и для обоих видов – входной, при котором происходит данный переход.
После краткого изложения основ перейдем непосредственно к вопросу о связи автоматов с Computer Science, предварительно рассказав об ученых, положивших начало данному направлению в науке.
История развития теории автоматов. Раньше всего в теории автоматов получило развитие одно из направлений прикладной теории автоматов – комбинационный синтез релейно-переключательных схем. Ещё в 1910 году петербургский физик П. С. Эренфест указал на возможность использования алгебры логики при построении релейных схем [3]. Но началом становления теории конечных автоматов можно считать работы В. И. Шестакова и
К. Шеннона (C. E. Shannon), в 1938 году применивших аппарат булевой алгебры к синтезу таких схем [4]. В 40-50-х годах теория прикладных автоматов была расширена за счет исследований в областях структурного и блочного синтеза автоматов (работы Д. Хафмена, Г. Мили, В. И. Шестакова,
М. А. Гаврилова, М. Уилкса) [5].
Loading ...