Рассмотрим вкратце еще одну вычислительную модель, эквивалентную уже изученным моделям, – модель вычислений на конечных автоматах.
Детерминированным конечным автоматом называется конечная система где
Q – непустое множество состояний,
S – непустой выходной алфавит,
– функция переходов,
– начальное состояние,
– множество заключительных (принимающих) состояний,
– функция печати (функция выходов).
Выберем некоторое слово w=s1…sn и зададим работу автомата М на слове w. На первом шаге автомат находится в начальном состоянии q0 и после прочтения первого символа s1 слова w определяется состояние После этого автомат переходит в состояние и при наличии непустой информации, выдаваемой значением , это значение подается на выход. Продолжая последовательность читать слово w и определяя состояния по функции t (где ), на каждом шаге выводится соответствующая информация (если она не пуста). Работа автомата заканчивается после прочтения символа , не принадлежащего выходному алфавиту S, а если слово w принадлежит то после прочтения всего слова.
|
|
Входное слово w называется представимым автоматом М, если состояние, в которое переходит М после прочтения слова w, принадлежит множеству F.
Изображением автомата М называется изображение помеченного графа, состоящего из множества вершин Q с выделенными вершинами из множества F, а также из множества дуг где каждая дуга помечается символом sj, который определяется из соотношения а если Æ, то соответствующим словом При этом каждая дуга может иметь несколько таких меток, а вершина q0 дополнительно помечается входящей дугой.
Пример. Рассмотрим конечный автомат М, изображенный на рис. 3.4. Автомат М имеет четыре вершины – q0, q1, q2, q3. При этом входящая вершина q0 выделена и образует одноэлементное множество заключительных состояний F. Функция печати для всех дуг выдает пустые значения, т. е. не дает никакой информации на выход.
При чтении слова автоматом М возникает последовательность состояний q0q1q2q1q0q1. Поскольку состояние q1 не является заключительным, слово w не представимо
автоматом М. Нетрудно заметить, что произвольное непустое слово представимо в автомате М тогда и только тогда, когда w содержит четное число символов а и четное число символов b.
Пример. Рассмотрим конечный автомат М, изображенный на рис. 3.5.
Автомат М для любой пары чисел, записанных в двоичной системе счисления (т. е. для двух последовательностей нулей и единиц), вычисляет и выводит их сумму. При этом данные начинаются с битов, имеющих наименьшие разряды, и числа читаются справа налево. Недостатком автомата М является то, что он не распознает условий переполнения и не работает с отрицательными числами.
|
|
Пример. Конечный автомат М, изображенный на рис. 3.6 является модификацией автомата из предыдущего примера и позволяет на выходах q0 и q1 получать арифметически правильную сумму двоичных чисел. При этом с помощью состояний q2 и q3 проверяется наличие ошибок, связанных с внесением значений и знаковый бит и их вынесением из знакового бита.
Отметим, что аналогично машинам Тьюринга любой конечный автомат можно проинтерпретировать в виде конечного автомата с алфавитом
Конечная система называется недетерминированным конечным автоматом, если – соответствующие элементы детерминированного конечного автомата, а функция переходов t каждой паре ставит в соответствие некоторое, не обязательно одноэлементное, подмножество множества т. е. выдает несколько значений из Q, в которое может поместиться пара (q,s).
Таким образом, отличие недетерминированного конечного автомата состоит в том, что функция переходов является многозначной.
Использование недетерминированных конечных автоматов упрощает задачу построения сложных машин. Ниже будет установлено, что любой недетерминированный конечный автомат может быть естественным образом проинтерпретирован в виде детерминированного конечного автомата.
Определим множество А(М) слов алфавита S, представимых недетерминированным конечным автоматом М. Пусть - некоторое слово алфавита S. Определим по интуиции множество T(w), положив
Очевидно, T(w) – множество всех состояний автомата М, которые могут быть достигнуты под действием входного слова w. Будем говорить, что слово w представимо автоматом М, если Æ. Таким образом, Æ}.
Теорема. Для любого недетерминированного конечного автомата М1 существует детерминированный конечный автомат М2 для которого А (М1)= А (М2).
Доказательство. Рассмотрим недетерминированный конечный автомат и построим детерминированный конечный автомат с условием А(М1)=А(М2). Положим
Функцию p2 зададим произвольно, а функцию t2 определим по шагам:
1)
2)
3) если на шаге некоторое значение уже определено, то
4) на множествах , для которых значение не задается ни на каком шаге, описанном в пп. 1 – 3, положим для определенности Æ.
Непосредственно проверяем, что построенный таким образом детерминированный автомат М2 является искомым.
Задачи и упражнения
1. Доказать, что функции примитивно рекурсивны:
а) ; б) ; в) .
2. Найти функцию , полученную из функций и по схеме примитивной рекурсии:
а) , ;
б) , .
3. Найти функции, получаемые из числовой функции с помощью операции минимизации по каждой ее переменной.
а)
б)
4. Доказать, что однократное применение операции минимизации к всюду определенной числовой функции приводит к функции, определенной хотя бы в одной точке.
5. Построить Машину Тьюринга, вычисляющую функцию
а) ; б) ; в) .