Способы задания конечного автомата

Комбинационные схемы, хотя и позволяют реализовать любые фиксированные зависимости между входными и выходными сигналами, не могут изменять характера своего поведения (т.е. последовательности обработки данных) - любое такое изменение требует изменения структуры схемы, т.е., по сути, переходу к другой схеме. Решить проблему перестройки работы без изменения структуры схемы возможно, если ввести в нее элементы памяти, которые позволяли бы фиксировать и сохранять промежуточные состояния устройства - в этом случае выходной сигнал будет зависеть не только от входного сигнала, но и от состояния схемы. Если количество таких элементов конечно, то, как указывалось выше, дискретное устройство будет называться конечным автоматом.

Конечным автоматом называется система <X, Y, Q, Y, Q>, в которой X и Y являются конечными входным и выходным алфавитами, Q - конечным множеством внутренних состояний, Y(x, q) - функцией переходов и Q(x,q) - функцией выходов.

Как указывалось ранее, Y(x,q) задает порядок преобразования входных символов и состояния автомата на предыдущем такте в состояние на последующем, a Q(x,q) - преобразования входных символов и состояния автомата на текущем такте в выходной символ. Если q₀- начальное состояние автомата, а i - номер такта, то его работа описывается системой:

Данные соотношения получили название системы канонических уравнений конечного автомата. Пользуясь ими можно, начиная с q₀, последовательно находить все последующие состояния автомата и выходные символы.

Выделяются два типа автоматов - инициальные и неинициальные. В инициальных автоматах начальное состояние фиксировано (т.е. они всегда начинают работать из одного и того же состояния q₀). В неинициальных автоматах в качестве начального состояния может быть выбрано любое из множества Q; этим выбором определяется дальнейшее поведение автомата.

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

В табличном способе автоматные функции задаются двумя конечными таблицами, именуемыми соответственно матрицей переходов и матрицей выходов. В этих таблицах строки обозначаются буквами входного алфавита, а столбцы - буквами внутреннего алфавита (символами, кодирующими внутреннее состояние автомата). В матрице переходов на пересечении строки (x_k) и столбца (q_r) помещаются значения функции Y (q_r, x_k), а в матрице выходов - значения функции Q(q_r, x_k).