Читать «Математический аппарат инженера» онлайн - страница 62

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

- 565 -

Ясно, что последовательностные схемы должны обладать способностью сохранять предыдущее состояние до следующего такта, в связи с чем их называют также автоматами с памятью или последовательностными машинами. В качестве памяти могут использоваться элементы задержки, на выходах которых повторяются входные воздействия со сдвигом во времени на интервал между тактами Dt. Широко применяются также различные запоминающие элементы, например, триггеры, способные сохранять состояния на выходах до тех пор, пока оно не изменяется в результате воздействия на их входы.

3. Типы конечных автоматов. В технике с понятием автомата обычно связывается некоторое устройство, способное выполнять определенные функции без вмешательства человека или с его ограниченным участием. Однако такое понимание является слишком узким. В широком смысле конечный автомат - это математическая модель, отображающая физические или абстрактные явления самой разнообразной природы. Такая модель успешно используется как в технике (проектирование электронных вычислительных машин, систем управления и связи), так и в других областях - психологии и физиологии (исследование деятельности нервной системы человека и простейших видов поведения животных), лингвистике (анализ синтаксиса русского, английского или других языков, расшифровка древних рукописей), теории и практике административного управления и т.п. Универсальность теории автоматов позволяет рассматривать с единой точки зрения различные объекты, устанавливать связи и аналогии между ними, переносить результаты из одной области в другую.

Рис. 235. Блок-схема конечного автомата.

Конечный автомат М определяется как система с конечным входным алфавитом Х = { ξ₁, ξ₂, ... , ξ_p}, конечным выходным алфавитом Y = {v₁, v₂, …, v_q}, конечным множеством состояний S = {σ₁, σ₂, ..., σ_i}, и двумя характеристическими функциями:

s(ν + 1) = δ (x(ν), s(ν));

у(ν) = λ (х(ν), s(ν)),

называемыми соответственно функцией переходов и функцией выходов. Общая блок-схема конечного автомата (рис. 235) может быть представлена в виде комбинационной схемы, реализующей характеристические функции δ и λ, и памяти, сохраняющей на один такт предыдущее состояние автомата.

В определении автомата участвует три конечных множества X, Y, S и две функции δ и λ, задающие некоторые отношения между

- 566 -

элементами этих множеств. Следовательно, конечный автомат можно обозначить упорядоченной пятеркой М = (X, Y, S, δ, λ). Мощности множеств X, Y, S равны соответственно: