Теорема 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 из начального состояния ( , ).

Доказательство окончено.

Существуют числовые функции, которые не вычисляются конечными автоматами.

ТЕОРЕМА 7. 2

Числовая функция f(x, y) = xy не вычисляется конечными автоматами.

Доказательство

Предположим противное. Пусть существует конечный автомат  = (A, B, Q, , ), который из начального состояния q₀ вычисляет f.

Здесь A = {00, 01, 10, 11}, B = {0, 1} и Q = {q₁, . . . , q_k}.

Пусть перемножаются два числа, большее из которых представляется в двоичной системе записью длины d. Тогда длина произведения двух таких чисел может достигать длины 2d1. При этом, если представлять такие произведения двоичными записями длины 2d1, то первые d компонент в них могут быть любыми двоичными последовательностями длины d.

Будем считать, что перемножаемые числа x и y, большее из которых представляется двоичной записью длины d, пополняются незначащими нулями и записываются в виде наборов длины 2d1.

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

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

После этого на вход  поступают остальные символы в виде последовательности d1 пар нулей.

Значения появляющихся при этом символов на выходе автомата образуют слово длины d1, определяемое только состоянием q_i.

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

Поэтому для любого значения d должно выполняться неравенство: k  2^d-1.

Поскольку значение k является фиксированным, а d  произвольное, то последнее неравенство неверно.

Следовательно, предположение о существовании автомата , вычисляющего функцию умножения пар чисел, неверно.

Доказательство окончено.

Упражнение.

1. Доказать, что для любого фиксированного натурального числа n существует конечный автомат, вычисляющий функцию f(x) = n  x;

2. Доказать, что не существует конечного автомата, вычисляющего функцию f(x, y) = div(x,y).

Имеет место еще одно свойство, ограничивающее вычислительные возможности автоматов, следующее из конечности множеств состояний.

Пусть A = {a₁, ... , a_n}  некоторый алфавит. Всякая бесконечная последовательность символов этого алфавита называется сверхсловом в A.Множество всех сверхслов в алфавите A обозначается как .

Сверхслово называется периодическим, если оно может быть представлено в виде: = ( )^. Здесь и  слова в алфавите A. Сверхслово ( )^ получается сцеплением слова и сверхслова ( )^, получаемого последовательным выписыванием бесконечное число раз. Слово называется периодом, а ( )^  периодической частью сверхслова .

Если автомат  в момент t₀ находится в начальном состоянии q₀ и в моменты времени t₀, t₀+1, . . . на его вход поступают символы сверхслова , то в эти же моменты времени на выходе  появляются символы выходного алфавита, образующие выходное сверхслово .

В этом случае будем говорить, что  из начального состояния q₀ перерабатывает входное сверхслово в выходное сверхслово .

ТЕОРЕМА 7.3

Если  это периодическое сверхслово и автомат  из состояния q₀ перерабатывает в , то является периодическим сверхсловом.

Доказательство

Пусть = ( )^, где = a_i1, ... , a_ik и = a_j1, ... , a_jp, и автомат  перерабатывает в из начального состояния q₀.

Обозначим начальный момент времени как t₀.

Рассмотрим последовательность q₁, q₂, . . . , q_i, . . .  (1)

состояний автомата  в моменты времени:

t₀+k, t₀+k+p, . . . , t₀ + k + (i  1)p, . . .

То есть это моменты времени, в которые на вход  поступают первые символы первого, второго, . . . , i-го, . . . вхождений периода во входное сверхслово .

Поскольку множество состояний  является конечным, то в последовательности состояний (1) имеются одинаковые состояния. Пусть это q_s и q_r, где s < r.

Тогда , начав работу в состоянии q_s, заканчивает переработку слова ( )^r-s переходом в исходное состояние. Следовательно, следующее слово ( )^r-s в слове ( )^ этот автомат перерабатывает так же, как и предыдущее такое слово.

Представим в виде ( )^{s - 1}(( )^{r - s})^.

Тогда при переработке из начального состояния q₀ последовательно идущие вхождения слова ( )^r-s в части (( )^{r - s})^.перерабатывается автоматом в одинаковые фрагменты выходного сверхслова. Последнее утверждение верно, поскольку такая переработка всякий раз начинается из одного и того же состояния.

Следовательно, автомат  перерабатывает в периодическое сверхслово

= ( ( )^{s - 1})( (( )^{r - s}))^.

Доказательство окончено.

Замечание. Если автомат , рассматриваемый в доказательстве теоремы, имеет n внутренних состояний, то можно считать, что r - s n. Поэтому длина кратчайшего периода выходного сверхслова не превосходит значения n  | |.