- •7. Конечные автоматы
- •7.1. Начальные понятия
- •7.2. Определение и задание автоматов
- •Определение
- •7.2.1. Диаграммы переходов
- •7.2.2. Табличное задание автоматов
- •7.2.3. Канонические уравнения
- •Очевидно, что если в последовательные моменты времени
- •7.3. Функции конечных автоматов
- •Определение
- •Теорема 7. 1
- •7.4. Отличимость состояний автоматов
- •Определение
- •7.5. Минимальные автоматы определение
- •1. Построение минимального автомата
- •2. Доказательство минимальности автомата
- •7.6. Распознавание слов автоматами
- •Определение
- •7.7. Схемы конечных автоматов
- •7.7.1. Композиция автоматов
- •7.7.2. Операция обратной связи
- •Определение
- •Определение
- •7.8. Схемы из элементарных автоматов
Теорема 7. 1
Множество функций, вычисляемых конечными автоматами, замкнуто относительно операции суперпозиции.
Доказательство
Пусть f: A* B* и g: B* C* словарные функции, вычисляемые автоматами и из состояний и соответственно.
Рассмотрим устройство, получаемое подключением выхода автомата к входу автомата , как это изображено на рис. 7.5
C
Рис.7.5
Это устройство называется суперпозицией автоматов и . Входным и выходным алфавитами автомата C являются множества A и C. Множество состояний автомата C состоит из всевозможных пар ( , ), где состояние , а состояние . Работа автомата C в каждый момент времени связана с переработкой очередного входного символа aA из текущего состояния ( , ), при котором сначала автомат перерабатывает a во входной символ автомата , который перерабатывает его в выходной символ, автомата C. Измененение состояния C состоит в изменении состояний и под действием входных символов автоматов и .
Тогда C является автоматом, который вычисляет функцию g f из начального состояния ( , ).
Доказательство окончено.
Существуют числовые функции, которые не вычисляются конечными автоматами.
ТЕОРЕМА 7. 2
Числовая функция f(x, y) = xy не вычисляется конечными автоматами.
Доказательство
Предположим противное. Пусть существует конечный автомат = (A, B, Q, , ), который из начального состояния q0 вычисляет f.
Здесь A = {00, 01, 10, 11}, B = {0, 1} и Q = {q1, . . . , qk}.
Пусть перемножаются два числа, большее из которых представляется в двоичной системе записью длины d. Тогда длина произведения двух таких чисел может достигать длины 2d1. При этом, если представлять такие произведения двоичными записями длины 2d1, то первые d компонент в них могут быть любыми двоичными последовательностями длины d.
Будем считать, что перемножаемые числа x и y, большее из которых представляется двоичной записью длины d, пополняются незначащими нулями и записываются в виде наборов длины 2d1.
Перемножаемые числа поступают на вход в виде последовательности пар значений одноименных двоичных разрядов, начиная с младших разрядов.
Пусть входное слово автомата , представляющее два перемножаемых числа x и y. Автомат заканчивает переработку первых d символов в некотором состоянии qi.
После этого на вход поступают остальные символы в виде последовательности d1 пар нулей.
Значения появляющихся при этом символов на выходе автомата образуют слово длины d1, определяемое только состоянием qi.
Поэтому значения первых d разрядов произведений произвольных чисел длины d могут принимать не более k различных значений.
Поэтому для любого значения d должно выполняться неравенство: k 2d-1.
Поскольку значение k является фиксированным, а d произвольное, то последнее неравенство неверно.
Следовательно, предположение о существовании автомата , вычисляющего функцию умножения пар чисел, неверно.
Доказательство окончено.
Упражнение.
Доказать, что для любого фиксированного натурального числа n существует конечный автомат, вычисляющий функцию f(x) = n x;
Доказать, что не существует конечного автомата, вычисляющего функцию f(x, y) = div(x,y).
Имеет место еще одно свойство, ограничивающее вычислительные возможности автоматов, следующее из конечности множеств состояний.
Пусть A = {a1, ... , an} некоторый алфавит. Всякая бесконечная последовательность символов этого алфавита называется сверхсловом в A.Множество всех сверхслов в алфавите A обозначается как .
Сверхслово называется периодическим, если оно может быть представлено в виде: = ( ). Здесь и слова в алфавите A. Сверхслово ( ) получается сцеплением слова и сверхслова ( ), получаемого последовательным выписыванием бесконечное число раз. Слово называется периодом, а ( ) периодической частью сверхслова .
Если автомат в момент t0 находится в начальном состоянии q0 и в моменты времени t0, t0+1, . . . на его вход поступают символы сверхслова , то в эти же моменты времени на выходе появляются символы выходного алфавита, образующие выходное сверхслово .
В этом случае будем говорить, что из начального состояния q0 перерабатывает входное сверхслово в выходное сверхслово .
ТЕОРЕМА 7.3
Если это периодическое сверхслово и автомат из состояния q0 перерабатывает в , то является периодическим сверхсловом.
Доказательство
Пусть = ( ), где = ai1, ... , aik и = aj1, ... , ajp, и автомат перерабатывает в из начального состояния q0.
Обозначим начальный момент времени как t0.
Рассмотрим последовательность q1, q2, . . . , qi, . . . (1)
состояний автомата в моменты времени:
t0+k, t0+k+p, . . . , t0 + k + (i 1)p, . . .
То есть это моменты времени, в которые на вход поступают первые символы первого, второго, . . . , i-го, . . . вхождений периода во входное сверхслово .
Поскольку множество состояний является конечным, то в последовательности состояний (1) имеются одинаковые состояния. Пусть это qs и qr, где s < r.
Тогда , начав работу в состоянии qs, заканчивает переработку слова ( )r-s переходом в исходное состояние. Следовательно, следующее слово ( )r-s в слове ( ) этот автомат перерабатывает так же, как и предыдущее такое слово.
Представим в виде ( )s - 1(( )r - s).
Тогда при переработке из начального состояния q0 последовательно идущие вхождения слова ( )r-s в части (( )r - s).перерабатывается автоматом в одинаковые фрагменты выходного сверхслова. Последнее утверждение верно, поскольку такая переработка всякий раз начинается из одного и того же состояния.
Следовательно, автомат перерабатывает в периодическое сверхслово
= ( ( )s - 1)( (( )r - s)).
Доказательство окончено.
Замечание. Если автомат , рассматриваемый в доказательстве теоремы, имеет n внутренних состояний, то можно считать, что r - s n. Поэтому длина кратчайшего периода выходного сверхслова не превосходит значения n | |.