ОПРЕДЕЛЕНИЕ. Числовая функция f: Nk ® N вычисляется конечным автоматом Â из состояния qr, если:

Числовая функция 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.