Читайте также: |
|
t 0, t 0 + 1,..., t 0 + k,...
на вход автомата A поступают символы a i 1,..., a i k, то с помощью уравнений (1) - (3) можно определить последовательность символов на выходе автомата в процессе переработки указанных входных символов, а также последовательность состояний автомата в процессе работы.
ФУНКЦИИ КОНЕЧНЫХ АВТОМАТОВ
Пусть A = { a 1,..., a m } - некоторый алфавит. Словом в этом алфавите называется всякая конечная последовательность: a i 1,..., a ik, все элементы которой являются символами из A.
Введем в рассмотрение пустое слово, которое не содержит символов, и обозначается как L.
Длиной произвольного слова называется количество символов в нем. Длина произвольного слова обозначается как | |.
Для обозначения множества слов в алфавите A применяется обозначение A *.
Пусть , Î A *. Тогда запись обозначает слово, получаемое последовательным выписыванием сначала символов слова , а затем символов . Слово называется сцеплением слов и .
Если Â = (A, B, Q, j, y) - это некоторый автомат, то всякое слово A * называется входным словом для Â.
ОПРЕДЕЛЕНИЕ
Пусть A и B являются алфавитами. Тогда отображение f: A * ® B * называется словарной функцией.
Возьмем произвольное непустое входное слово = a i 1,..., a ik. Пусть в начальный момент времени t 0 автомат Â находится в состоянии qr и в моменты времени t 0, t 0+ 1,..., t 0+ k - 1 на его вход поступают символы a i 1,..., a i k.
В процессе работы автомата в эти же моменты времени на выходе Â появляются символы выходного алфавита b j 1,..., b j k, образующие слово , которое называется выходным словом автомата.
Будем говорить, что Â из начального состояния qr перерабатывает слово в слово .
ОПРЕДЕЛЕНИЕ
Словарная функция f: A * B * вычисляется автоматом Â = (A, B, Q, j, y) из начального состояния qr, если для любого слова A * выполняется соотношение:
" Î A * (f () = Û Â из начального состояния qr перерабатывает в ).
Для функции, которая вычисляется автоматом Â из состояния qr, применяется обозначение .
Пример. Рассмотрим словарную функцию f: A * ® B *, где A = { a, b }, B = { a, b }, которая заменяет в произвольном входном слове A * каждое третье вхождение символа b на символ a, а все остальные символы входного слова функция оставляет без изменения.
Диаграмма переходов автомата, который из начального состояния q 0 вычисляет эту функцию, приведена на рис. 7.2.
b (b)
q 0 q 1
a (a) a (a)
b (a) b (b)
a (a) q 2
Рис. 7.2
Уточним понятие функций, вычисляемых конечными автоматами, для числовых функций.
Пусть входным и выходным алфавитами автомата является множество { 0, 1 }. Тогда входные и выходные слова этого автомата можно интерпретировать как двоичные записи целых неотрицательных чисел в двоичной системе. Возможно, что такие записи имеют незначащие нули.
Для конечных автоматов естественно подавать на вход записи чисел в двоичной системе справа налево, поскольку многие традиционные схемы арифметических вычислений предполагают обработку цифр записей чисел, начиная с младших разрядов записей чисел.
Поскольку входные слова конечных автоматов, в том числе и такие, которые представляют числа, по определению поступают на вход автоматов в противоположном порядке, то будем представлять числа, подаваемые на входы автоматов в виде слов, являющихся инвертированными записями таких чисел.
Пусть n - произвольное целое неотрицательное число. Обозначим как - всякую инвертированную двоичную запись этого числа, в которой допускается существование незначащих нулей.
Незначащие нули приходится использовать из-за того, что реальные арифметические функции могут отображать числа одной длины в числа, записи которых имеют другую длину (большую или меньшую). Поскольку длины входных слов и выходных слов автоматов всегда совпадают, то в дальнейшем двоичные числа всегда будут представляться с точности до необходимого числа незначащих нулей в них, что позволяет вычислять числовые функции с помощью автоматов и тогда, когда длина записи числа результата больше длины числа, исходного данного.
Если числовая функция f отображает Nk в N, то всякий набор чисел, принадлежащий области определения этой функции, будем представлять словом, символами которого являются последовательности значений одноименных разрядов чисел этого набора.
Пусть n 1,..., n k это числа из N, представленные записями равной длины, получаемыми добавлением произвольного количества незначащих нулей.
Запись обозначает слово в алфавите
{ 0, 1 } k, первый символ которого представляет значения самого младшего разряда всех чисел n 1,..., n k, второй - значения следующего разряда этих чисел и так далее. Заметим, что { 0, 1 } k это все k -символьные последовательности из нулей и единиц.
ОПРЕДЕЛЕНИЕ
Числовая функция 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.
ТЕОРЕМА 7. 1
Множество функций, вычисляемых конечными автоматами, замкнуто относительно операции суперпозиции.
Доказательство
Пусть f: A * ® B * и g: B * ® C * - словарные функции, вычисляемые автоматами Â и Á из состояний и соответственно.
Рассмотрим устройство, получаемое подключением выхода автомата Â к входу автомата Á, как это изображено на рис. 7.5
 Á
C
Рис. 7.5
Это устройство называется суперпозицией автоматов Â и Á. Входным и выходным алфавитами автомата C являются множества A и C. Множество состояний автомата C состоит из всевозможных пар (, ), где - состояние Â, а - состояние Á. Работа автомата C в каждый момент времени связана с переработкой очередного входного символа a Î A из текущего состояния (, ), при котором сначала автомат Â перерабатывает a во входной символ автомата Á, который перерабатывает его в выходной символ, автомата C. Измененение состояния C состоит в изменении состояний Â и Á под действием входных символов автоматов Â и Á.
Тогда C является автоматом, который вычисляет функцию g f из начального состояния (, ).
Дата добавления: 2015-11-30; просмотров: 26 | Нарушение авторских прав