Автоматы с памятью.

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

Автомат с памятью (State machine) это механизм (реальный или представляемый) который содержит определенное состояние, называемое начальным состоянием, может принимать входные данные (воздействия), затем производить новое состояние и выходные данные которые зависят только от предыдущего состояния и входных данных.

Таким образом, автомат с памятью описывается функцией, которая ставит в соответствие паре (вход, состояние) пару (выход, состояние). Например, файл типа TEXT ведет себя как автомат с памятью, в котором состояние это значение файловой переменной, а входы и выходы определяются операторами READ и WRITE.

Для файла F1 в состоянии выполнения s со значением

F1(s) = < †AB†, †CD†, R>

и оператора READ(F1, Ch) как входа для TEXT-машины, результатом будет новое состояние t, такое что

F1(t) = < †ABС†, †D†, R>

Выход TEXT-машины может быть значением Ch:

Ch(t) = C

Тот же вход для состояния t не произведет тот же выход, потому что внутренне состояние иное.

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

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

Имена и значения объектов данных скрытых модулем образуют состояние автомата.

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

Например, в модуле счетчика, состояние конечного автомата счетчика задается именованными значениями Hundreds, Tens и Ones как конкретное состояние, которое является подмножеством состояния выполнения всей программы, скажем

{Hundreds·3, Tens·5, Ones·2}

(соответствующее абстрактное состояние содержит Counter·352).

Процедурный оператор

Value(V100, V10, V1)

является входом, который не меняет состояния автомата и возвращает как выход значения V100, V10 и V1, а именно 3, 5 и 2. Напротив, процедурный оператор Bump является входом, который создает новое конкретное состояние выполнения

{Hundreds·3, Tens·5, Ones·3}

и не производит выхода.

Автомат с памятью с конечным количеством состояний называется конечным автоматом с памятью (finite state machine) или просто конечный автомат. Этот автомат может быть описан диаграммой, в которой каждое состояние представлено кругом, содержащим имя состояния и переходами между состояниями, представленных стрелками, помеченными входными символами, которые являются причиной изменения состояния автоматом. В следующей диаграмме символ x производит изменение состояния из S в T.

Одно состояние автомата обозначается как начальное состояние – оно будет иметь непомеченную входящую стрелку, не имеющую другого, исходного состояния. Например, S начальное состояние в

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

Когда автомат, который начинает работу в его стартовом состоянии, делает переход для каждого входного символа и заканчивает в одном из финальных состояний, говорят, что он распознал или принял вход. Автомат, изображенный выше, начинает в состоянии S и останавливается в состоянии S, если его вход – пустая строка или строка из четного числа элементов x.

Автоматы, как изображенный выше, называют распознавателями (recogniser) или приемщиками (acceptor) – они обеспечивают только один выход: успех, если они в финальном состоянии в конце входа и ошибка в противном случае.

Другие автоматы, называемые преобразователями (transducer), могут производить выходной символ для каждого считанного входного. Метка стрелки с символами, разделенными наклонной чертой / означает, что когда первый символ считывается, второй записывается.

Распознаватель приведенный выше может быть переделан в преобразователь, который выводит половину # от количества прочитанных x.

Модуль с внутренними данными только типа CHAR, как модуль счетчика, может быть смоделирован конечным автоматом с памятью. Модуль с внутренними данными типа TEXT не может быть смоделирован конечным автоматом, потому нет ограничения на длину файла типа TEXT и, следовательно, на количество возможных состояний.

Конечные автоматы очень полезны для описания ситуаций, в которых требуется сделать конечное число выборов для входных строк произвольной длины. Например, конечный автомат может быть использован для определения, содержит ли входная строка возрастающий набор длиной не менее 10 символов. Состоянием выполнения могут быть последние 9 символов. Существует конечное число возможных состояний, потому что ограничено количество возможных символов. Для каждого нового входного символа может быть принято решение, образуют ли 9 ранее считанных символов и последний считанный требуемый набор данных. Если это так, что ответом будет “да”, если не образуют и входная строка закончилась, ответом будет “нет”. В новое состояние включается последний считанный символ, самый старый отбрасывается.

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

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

BEGIN {модуль тестирования счетчика}

Start;

Value(Ch1, Ch2, Ch3);

WRITELN(Ch1, Ch2, Ch3);

WHILE (Ch1 < > ‘9’ OR Ch2 < > ‘9; OR Ch3 < > ‘9’)

DO

BEGIN

Bump;

Value(Ch1, Ch2, Ch3);

WRITELN(Ch1, Ch2, Ch3);

END;

Bump;

Value(Ch1, Ch2, Ch3);

WRITELN(Ch1, Ch2, Ch3);

END {модуль тестирования счетчика}

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