Определение

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

  A^* (f( ) =   из начального состояния q_r перерабатывает в ).

Для функции, которая вычисляется автоматом  из состояния q_r, применяется обозначение .

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

Диаграмма переходов автомата, который из начального состояния q₀ вычисляет эту функцию, приведена на рис. 7.2.

b(b)

q₀ q₁

a(a) a(a)

b(a) b(b)

a(a) q₂

Рис. 7.2

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

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

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

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

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

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

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

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

Запись обозначает слово в алфавите {0, 1}^k, первый символ которого представляет значения самого младшего разряда всех чисел n₁, . . . , n_k, второй  значения следующего разряда этих чисел и так далее. Заметим, что {0, 1}^k это все k-символьные последовательности из нулей и единиц.

ОПРЕДЕЛЕНИЕ

Числовая функция f: N^k  N вычисляется конечным автоматом  из состояния q_r, если:

n₁,...,n_k  N(f(n₁, . . . , n_k) = m  = ).

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

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

1(0)

0(0) q₀ q₁ 1(1)

0(1)

Рис.7.3

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

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

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

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

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

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

01(1) 10(0) 01(0)

q₀ q₁ 10(1)

00(0) 00(1)

11(1)

11(0) 00(0)

q₂ 01(1)

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

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