Костенко К.И. Учебник. Часть VIII - файл n1.doc

приобрести
Костенко К.И. Учебник. Часть VIII
скачать (778.5 kb.)
Доступные файлы (1):
n1.doc779kb.24.08.2012 02:26скачать

n1.doc

  1   2   3   4

7. КОНЕЧНЫЕ АВТОМАТЫ



Дискретные системы вместе с конечными или счетными совокупностями составляющих их объектов могут иметь еще одно свойство. Такое свойство связано с существованием или функционированием системы на протяжении нескольких последовательных этапов, или моментов, времени, на каждом из которых системой выполняются определенные действия. В качестве примера систем, функционирующих во времени, можно привести схемы их функциональных элементов, которые на каждом шаге своей работы получают на входах некоторый набор значений переменных и перерабатывают этот набор в значения, появляющиеся на выходах схемы. В данном разделе пособия рассматривается одна из простейших моделей таких систем, называемых конечными автоматами.
7.1. НАЧАЛЬНЫЕ ПОНЯТИЯ
Конечные автоматы представляют собой модель вычислительных устройств, имеющих ограниченную память. Это отличает автоматы от схем из функциональных элементов, функционирование которых определяется только наборами значений, поступающих на входы, и не зависит от предыдущей работы таких систем.

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

Содержательно автомат  это устройство, которое взаимодействует с внешней средой посредством входного и выходного каналов.

Эти каналы называются входом и выходом автомата.

По входному каналу в автомат поступают сигналы из внешней среды.

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

Автоматы сохраняют информацию о своей предыдущей работе с помощью состояний и используют ее в последующем как данные.

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

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

t0, t0 + 1, . . . , t0 + i, . . . ;
2) в каждый момент времени устройство находится в одном из своих внутренних состояний;

3) сигнал на выходе устройства в некоторый момент времени и его состояние в следующий момент времени однозначно определяются сигналом на входе автомата и его состоянием в текущий момент времени.
Если множество входных сигналов автомата и множество его состояний  конечные, то такой автомат называется конечным автоматом.

Рассмотрим пример реального устройства, которое может считаться конечным автоматом.

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

В качестве входных сигналов устройства можно выбрать:

1) помещение жетона;

2) нажатия на кнопку выбора напитка (количество разных символов равно числу видов имеющихся напитков);

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

Состояния устройства соответствуют ситуациям наличия и отсутствия жетона в приемном кармане.
Функционирование устройства может рассматриваться в дискретном времени, когда каждый этап работы происходит в течение одного момента времени и состоит либо в выдаче упаковки с напитком, либо в пропуске действия.
7.2. ОПРЕДЕЛЕНИЕ И ЗАДАНИЕ АВТОМАТОВ
Алфавитом называется всякое конечное множество A = {a1, . . . , an}. Элементы множества A называются символами.

ОПРЕДЕЛЕНИЕ


Конечным автоматом называется всякая пятерка

A = (A, B, Q, , ), где:

  1. A входной алфавит;

  2. B выходной алфавит;

  3. Q  конечное множество состояний автомата;

  4. : A Q Q  функция перехода;

  5. : A Q B  функция выхода автомата.


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

Символы входного и выходного алфавитов представляют входные и выходные сигналы автомата.

Отображения  и  задают функционирование автомата A и называются функциями перехода и выхода.

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

Отображение  задает символ на выходе A для такой же ситуации.

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

Рассмотрим основные способы представления автоматов.

7.2.1. ДИАГРАММЫ ПЕРЕХОДОВ

Пусть = (A, B, Q, , )  это автомат и
A = {a1, . . . , am}, Q = {q1, . . . , qr}.

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

Дуге, выходящей из состояния qj, помеченной входным символом ai, припишем также выходной символ (ai, qj), заключив его в скобки.

Проведем эту дугу в состояние (ai, qj).

Соответствующий фрагмент изображения автомата имеет вид, приведенный на рис.7.1.

qj qk
ai((ai, qj))

Рис. 7.1

Здесь qk = (ai, qj).

Построенное по заданным правилам представление автомата называется диаграммой переходов.

Диаграммы переходов полностью определяют представляемые ими автоматы.

Множества A и B определяются символами, приписанными дугам без скобок и в скобках соответственно.

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

Множество всех состояний автомата задается помеченными кругами.

Отображения  и  полностью представлены в диаграмме. При этом значение (ai, qj) равно состоянию, в которое ведет дуга диаграммы, выходящая из состояния qj и помеченная входным символом ai.

Значение (ai, qj) равно символу выходного алфавита, который приписан в скобках для той же дуги.

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

Если в некоторый момент времени t автомат находится в состоянии qj и на его вход поступает символ ai, то функционирование этого автомата можно представить с помощью перемещения по диаграмме из состояния qj по дуге, помеченной входным символом ai.

При этом выбранная дуга ведет в состояние, в котором будет находиться в момент времени t + 1. Символ на выходе автомата в момент t приписан этой же дуге в скобках.

Поэтому функционирование автомата в последовательные моменты t0, t0+1, . . . , t0+i, . . . можно промоделировать с помощью прохождения соответствующего пути в диаграмме переходов.

Упражнение. Покажите, что диаграмма переходов всякого автомата имеет элементарные циклы ненулевой длины.
7.2.2. ТАБЛИЧНОЕ ЗАДАНИЕ АВТОМАТОВ

Поскольку множества A, B и Q автомата присутствуют в определениях функций перехода и выхода, то для задания достаточно определить только сами эти функции.

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

Элемент таблицы для , лежащий на пересечении i-й строки и j-го столбца, равен (ai, qj). Аналогичный элемент таблицы для отображения  равен (ai, qj).
qj qj

. . . .

. . . .

ai . . . (ai, qj) . . . ai . . . (ai, qj) . . .

. . . .

. . . .

Табличное здание автоматов удобно, например, если необходимо организовывать хранение и моделирование работы моделей автоматных устройств с помощью ЭВМ. В этом случае таблицы для функций  и  являются достаточно простыми структурами данных для компьютерных программ.
7.2.3. КАНОНИЧЕСКИЕ УРАВНЕНИЯ
Пусть для автомата задано фиксированное состояние q0, в котором он всегда начинает свою работу в начальный момент времени t0. Тогда, если отображения  и  могут быть записаны в виде формульных выражений, то функционирование такого автомата во времени представляет следующая система соотношений, называемых каноническими уравнениями:


q(t0) = q0;

(1)

q(t+1) = (x(t), q(t));

(2)

y(t) = (x(t), q(t)).

(3)


Здесь q(t) обозначает состояние автомата в момент t, а x(t) и y(t)  это соответственно символ на входе и символ на выходе этого автомата в момент времени t.

Уравнение (1) задает начальное состояние , уравнение (2)  состояние в следующий момент времени, а уравнение (3)  символ на выходе в момент t.

Очевидно, что если в последовательные моменты времени


t0, t0 + 1, . . . , t0 + k, . . .

на вход автомата A поступают символы ai1, ... , aik, то с помощью уравнений (1)  (3) можно определить последовательность символов на выходе автомата в процессе переработки указанных входных символов, а также последовательность состояний автомата в процессе работы.
7.3. ФУНКЦИИ КОНЕЧНЫХ АВТОМАТОВ
Пусть A = {a1, ... , am}  некоторый алфавит. Словом в этом алфавите называется всякая конечная последовательность: ai1, ... , aik , все элементы которой являются символами из A.

Введем в рассмотрение пустое слово, которое не содержит символов, и обозначается как .

Длиной произвольного слова называется количество символов в нем. Длина произвольного слова обозначается как ||.

Для обозначения множества слов в алфавите A применяется обозначение A*.

Пусть , A*. Тогда запись обозначает слово, получаемое последовательным выписыванием сначала символов слова , а затем символов . Слово называется сцеплением слов и .

Если = (A, B, Q, , )  это некоторый автомат, то всякое слово A* называется входным словом для .
ОПРЕДЕЛЕНИЕ

Пусть A и B являются алфавитами. Тогда отображение f: A*B* называется словарной функцией.
Возьмем произвольное непустое входное слово = ai1, ..., aik. Пусть в начальный момент времени t0 автомат находится в состоянии qr и в моменты времени t0, t0+1, . . . , t0+k 1 на его вход поступают символы ai1, . . . , aik.

В процессе работы автомата в эти же моменты времени на выходе появляются символы выходного алфавита bj1, . . . , bjk, образующие слово , которое называется выходным словом автомата.

Будем говорить, что из начального состояния qr перерабатывает слово в слово .

ОПРЕДЕЛЕНИЕ


Словарная функция f: A* B* вычисляется автоматом = (A, B, Q, , ) из начального состояния qr, если для любого слова A* выполняется соотношение:

A* (f() = из начального состояния qr перерабатывает в ).
Для функции, которая вычисляется автоматом из состояния qr, применяется обозначение .

Пример. Рассмотрим словарную функцию f: A*B*, где A = {a, b}, B = {a, b}, которая заменяет в произвольном входном слове A* каждое третье вхождение символа b на символ a, а все остальные символы входного слова функция оставляет без изменения.
Диаграмма переходов автомата, который из начального состояния q0 вычисляет эту функцию, приведена на рис. 7.2.
b(b)

q0 q1

a(a) a(a)

b(a) b(b)
a(a) q2
Рис. 7.2
Уточним понятие функций, вычисляемых конечными автоматами, для числовых функций.

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

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

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

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

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

Пусть n1, . . . , nk это числа из N, представленные записями равной длины, получаемыми добавлением произвольного количества незначащих нулей.

Запись обозначает слово в алфавите
{0, 1}k, первый символ которого представляет значения самого младшего разряда всех чисел n1, . . . , nk, второй  значения следующего разряда этих чисел и так далее. Заметим, что {0, 1}k это все k-символьные последовательности из нулей и единиц.
ОПРЕДЕЛЕНИЕ

Числовая функция f: NkN вычисляется конечным автоматом из состояния qr, если:

n1,...,nkN(f(n1, . . . , nk) = m =).

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

Пример. На рис.7.3 изображена диаграмма переходов автомата, который из начального состояния q0 вычисляет функцию f(x) = 2x.

1(0)




0(0) q0 q1 1(1)
0(1)
Рис.7.3

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

Последнее предположение требуется для того, чтобы длина результата равнялась длине входного слова.

Состояния q0 и q1 приведенного автомата необходимы для запоминания значения переноса в старший разряд при поразрядном умножении входного числа на 2.

На диаграммах автоматов наборы значений одноименных разрядов чисел n1, . . . , nk будем представлять горизонтальными последовательностями.

Пример. На рис. 7.4 изображена диаграмма переходов автомата, который из начального состояния q0 вычисляет функцию f(x, y) = 2x + y.

Входным алфавитом этого автомата является множество: {00, 01, 10, 11}.

01(1) 10(0) 01(0)
q0 q1 10(1)

00(0) 00(1)

11(1)

11(0) 00(0)

q2 01(1)
10(0), 11(1) Рис. 7.4

Состояния q0, q1 и q2 приведенного автомата соответствуют запоминанию значений переноса в старшие разряды значений 0, 1 и 10. В последнем случае имеет место перенос в два последующих разряда входных чисел: в первый из последующих разрядов ничего не добавляется, а во второй добавляется 1.

  1   2   3   4


7. КОНЕЧНЫЕ АВТОМАТЫ
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации