Глава 2. Способы задания конечных автоматов

Можно по-разному описывать принципы работы автомата. Один из способов описания - с помощью набора правил функционирования - использовался в примере 1 §1. Рассмотрим более удобный табличный способ. Чтобы задать автомат табличным способом, надо заполнить его таблицу выходов и переходов, исходя из функции выходов f и функции переходов g (табл. 1).

Таблица 1

	v1	…	vr
a1	f(a1,v1),g(a1,v1)	…	f(a1,vr),g(a1,vr)
…		…
аs	f(as,v1),g(as,v1)	…	f(as,vr),g(as,vr)

В крайнем левом столбце таблицы перечислены символы входного алфавита A = {a₁,а₂, ...,a_s}, а в верхней строке - элементы множества состояний V= {v₁,v₂,...,v_r}. В клетке, стоящей на пересечении строки а_i и столбца v_j, стоит пара f(a_i,v_j), g(a_i,v_j), которая согласно определению функций f и g указывает, что если автомат находился в состоянии v_j и на вход ему подали сигнал a_i, то на выходе автомата получим сигнал f(a_i,v_j), и автомат перейдет в состояние g(a_i,v_j). Используя такую таблицу, можно для любой последовательности входных сигналов определить, как будет выглядеть соответствующая последовательность выходных сигналов или состояний автомата.

Обычно во множестве V={v_1,v₂,…,v_r} особо выделяют одно из состояний (как правило, это состояние v₁) и называют его начальным. Этот факт записывают в виде равенства q(0)=v₁ и считают, что в момент «включения» автомата его состояние (точнее, состояние его памяти) известно. Такой автомат называется инициальным. В дальнейшем мы будем рассматривать только инициальные автоматы.

Один и тот же абстрактный автомат можно использовать для описания двух совершенно различных конкретных устройств, если они сходны по своим принципам функционирования.

Пример 1. Пусть автомат, алфавиты которого A = В = {а, b, с }, задан с помощью таблицы выходов и переходов (табл. 2). Будем считать его инициальным автоматом с начальным состоянием v₁.

Таблица 2

	v1	v2
а	а, v1	а, v2
b	b, v1	а, v1
с	c, v2	c, v2

Предположим, что ему на вход могут поступать последовательности символов (символьные строки) произвольной длины, но только двух типов - оканчивающиеся символом b или символом с. Тогда, зная состояние автомата после завершения его работы над входной строкой, но не имея доступа к этой строке, мы, тем не менее, можем точно установить её тип. Действительно, из табл. 2 видно, что когда на вход автомату поступает символ b, то он из любого состояния переходит в состояние v₁. Значит, в этом состоянии автомат и завершит работу, если символ b был последним символом входной строки. Аналогично из табл. 2 следует, что если на вход автомату подать символ с, то он из любого состояния перейдет в состояние v₂ и в нем же остановится, если входная строка оканчивается символом с. Но поскольку мы знаем, что последний символ входной строки - это всегда либо b, либо с, то само состояние, в котором автомат завершит свою работу, покажет нам тип входной строки: когда автомат завершает работу в состоянии v₁ это означает, что входная строка заканчивалась символом b. Если же автомат остановился в состоянии v₂, то она заканчивалась символом с.

Предположим, например, что входные строки - это идентификаторы переменных и констант в некотором языке программирования. И пусть согласно синтаксису этого языка имя переменной - это символьная строка в алфавите A = {а, b, с }, которая всегда заканчивается символом b, а имя константы - строка, заканчивающаяся символом с. Проведенный выше анализ показывает, что данный автомат отличает имя константы от имени переменной. Значит, он способен выполнять одну из функций компилятора - осуществлять синтаксический анализ символьных строк, подаваемых ему на вход. Заметим, что рассмотренный автомат - это автомат из примера 1 §1, у которого символы алфавитов A и В переобозначили по следующему правилу: а₁=b₁= а, а₂ = b₂ = b, а₃ = b₃ = с.

Другой способ задания автомата - с помощью диаграммы Мура. При таком способе автомат изображается в виде ориентированного графа, в котором допускаются кратные дуги и петли. Число вершин равно r — числу состояний автомата. Каждая вершина помечена символом из множества состояний V = { v_{1 ,} v_{2 ,}... v_r }. Дуга выходит из вершины v_k в вершину v_n тогда и только тогда, когда в данном автомате возможен переход из состояния v_k в состояние v_n по некоторому входному сигналу. Все дуги, выходящие из вершины v_k, помечены парой символов вида (a_i,b_j), где а_i ÎA, b_j=f(a_i,v_k). Иными словами, начало дуги определяет состояние автомата в предшествующий, а её конец - в последующий моменты времени. При этом на самой дуге указывается входной и соответствующий ему выходной сигналы.

Граф диаграммы Мура должен удовлетворять условию детерминированности. Оно заключается в том, что для любого входного символа а_i из каждой вершины должна выходить только одна дуга, помеченная этим символом. Поэтому в диаграмме Мура из каждой вершины выходит ровно s дуг, где s - это мощность алфавита А. Диаграмма Мура для автомата, рассмотренного в примере 1, изображена на рис. 2.

Реальные вычислительные устройства имеют, как правило, несколько входных и выходных каналов. Для их описания удобнее рассматривать автомат с несколькими входами и выходами и считать, что за один такт он получает на вход и направляет на выход не один, а не­сколько сигналов одновременно - по одному сигналу на каждый канал.

Простейшим детерминированным автоматом с n входами и m выходами является схема из функциональных элементов, реализующая систему m булевых функций от n аргументов. Это пример логического автомата, у которого отсутствует блок памяти.

Автомат, имеющий много входных каналов, как и автомат с одним входом, можно задавать и табличным способом, и диаграммой Мура. В этом случае таблица выходов и переходов в крайнем левом столбце содержит не отдельные символы входного алфавита, а все возможные наборы входных символов длины n, где n - число входных каналов. Аналогичные изменения будут и в диаграмме Мура: первый элемент метки на дугах теперь представляет собой не отдельный сим­вол алфавита A, а один из возможных наборов входных символов длины n. Рассмотрим соответствующий пример.

Пример 2. Пусть автомат задан диаграммой Мура (рис. 3).

Рис.3

Он имеет два состояния v₁ и v₂, из которых v₁ считается начальным. Входной и выходной алфавиты А и В совпадают, причем А = В = {0,1}. Метки на дугах указывают, что у автомата два входных и один выходной канал. Например, метка (01,1) на дуге, ведущей из вершины v₁ в v_{1 ,} означает, что если в начале такта автомат находился в состоянии v₁ и по первому каналу на вход ему поступил сигнал 0, а по второму каналу 1, то на его выход будет направлен сигнал 1, и в конце такта автомат останется в том же состоянии v₁.

Данный автомат можно было бы задать таблицей выходов и переходов (табл. 15). Покажем, что он складывает по модулю 2ⁿ два произвольных n -разрядных числа a=(a_n,a_n-1,…,a₁) и b=(b_n,b_n-1,…,b₁), заданных в двоичной системе счисления, и выдает результат c=(c_n,c_n-1,…,c₁) также в двоичной системе счисления. Числа а и b будем подавать на вход автомата поразрядно, начиная с младших разрядов, т.е. в моменты времени t = 1, 2, 3,...,n по первому входному каналу будет поступать сигнал а_t, а по второму каналу b_t. Тогда в конце i -го такта на выходе автомата появится сигнал с_t. Анализ табл. 3 показывает, что входные сигналы а_t, b_t, и соответствующий выходной сигнал с_t связаны равенст­вом

где d_t = 0, если в начале i -го такта автомат находится в состоянии v_{1 ,} либо d_t=1, если автомат находится в состоянии v₂. По смыслу величи­на d_t является признаком переноса единицы в следующий разряд и оп­ределяется только состоянием автомата в начале t -го такта. Поскольку в начальный момент времени автомат находится в состоянии v₁ то d₁ = 0. Таким образом, данный автомат заn тактов выполнит сложение по модулю 2ⁿ чисела и b «столбиком» и выдаст их сумму поразрядно, начиная с младшего разряда.

Дата добавления: 2015-11-30