Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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






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

" n 1,..., n k Î N (f (n 1,..., n k) = m Û = ).

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

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

 

 

1 (0)

 
 


0 (0) q 0 q 1 1 (1)

 

0 (1)

 

Рис. 7.3

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

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

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

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

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

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

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

 

q 0 q1 10 (1)

00 (0) 00 (1)

11 (1)

11 (0) 00 (0)

q 2 01 (1)

 

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

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

 






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.