Конечные автоматы

• Конечные автоматы

Конечный автомат можно представить как “черный ящик”, внутреннее устройство которого нам неизвестно, но известно, что он может находиться в одном из некоторого конечного числа состояний (неважно, что это означает с точки зрения устройства конечного автомата). Время от времени через входные устройства происходит воздействие (подается входной сигнал) на конечный автомат. Число этих воздействий тоже конечно. При воздействии автомат переходит (или не переходит) в новое состояние и генерирует некоторый выходной сигнал, число которых также должно быть конечно.

Можно считать, что время в нашей модели дискретно, то есть “жизнь и поведение” автомата целиком описываются последовательностями входных сигналов, состояний автомата и выходных сигналов.

Пример. Компьютер является конечным автоматом. Действительно, можно считать, что он состоит из набора простейших (битовых элементов). Пусть N – число этих элементов. Каждый элемент может находиться в двух состояниях (0 и 1), тогда, например, компьютер из двух элементов (таких, конечно, на практике не бывает) может находиться в 4 состояниях, а компьютер из N элементов в 2^N различных состояниях. Заметим, что число это может быть очень большим.

Способы описания конечных автоматов

Так как структура конечного автомата нам неизвестна, то мы не можем ее описать. Можно описать только, как он функционирует.

Все способы описания конечного автомата – это описание его функционирования.

Входные и выходные сигналы конечного автомата для удобства можно обозначать символами. В связи с этим часто говорят о входном и выходном алфавите конечного автомата. То же можно сделать и с состояниями. В простых случаях удобно использовать для их обозначения просто целые числа 0, 1, 2, 3 и т.д.

Задание конечного автомата таблицей

Любой конечный автомат можно описать таблицей. В ней для каждого входного символа и для каждого состояния автомата указывается, в какое состояние автомат переходит и какой выходной символ он генерирует.

Пример. Опишем функционирование автомата, который запоминает один символ (или осуществляет задержку сигнала).

Состояние автомата до входного сигнала (то, что он «помнил»)	Входной сигнал	Состояние автомата  после входного сигнала (запоминает поступивший сигнал)	Выходной сигнал (автомат выдает то, что он «помнил» до входного сигнала)
0	0	0	0
0	1	1	0
1	0	0	1
1	1	1	1

Задание конечного автомата графом

Сопоставим каждому состоянию автомата точку или кружок на плоскости – вершину графа, а каждому переходу автомата из одного состояния в другое – дугу, соединяющую эти вершины. Направление дуги соответствует ходу «времени». Рядом с дугой напишем входной символ, вызывающий такой переход, а в скобочках выходной символ, порождаемый автоматом.

Пример. Для элементарного запоминающего автомата граф будет таким.

Задача 1.

Опишите конечный автомат проверки на четность числа подающихся на вход единиц, если, как и в предыдущем примере, входной и выходной алфавиты состоят из 0 и 1, причем выходной сигнал 0 означает, что число всех поступивших на вход 1 было четным, а 1 - нечетным. Сколько состояний имеет придуманный конечный автомат. Является ли число состояний минимальным?

Задача 2.

Представьте придуманный автомат в виде таблицы и в виде графа.

Работа конечного автомата

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

Пример. Рассмотрим протокол работы запоминающего автомата. Начальным его состоянием естественно считать 0. Пусть автомат работает на следующей последовательности входных сигналов: 11001.

Заполним табличку протокола работы автомата:

Время	0	1	2	3	4
Входной сигнал	1	1	0	0	1
Состояние	0	1	1	0	0
Выходной сигнал		0	1	1	0

В начале выходной последовательности появился 0, который хранился в памяти автомата перед началом его работы.

Обратите внимание на задержку сигнала автоматом и на потерю на выходе последней 1 (она сохраняется в памяти автомата).

 

Задача 3.

 В условиях предыдущего упражнения напишите протокол работы построенного конечного автомата на последовательности 0101100111.

 

Это интересно.

Самообучающийся автомат Клода Шеннона для игры в чет-нечет 

Случай, о котором будет рассказано, давно стал легендой, поэтому мы расскажем его, не претендуя на точность деталей.

Произошел он в те времена, когда информатика называлась кибернетикой, а программисты (кибернетики), вместо написания программ, строили исполнителей прямо в "железе".

Однажды кибернетики решили посоревноваться в искусстве программирования и договорились сделать автоматы для игры в чет-нечет и устроить между ними турнир. Чей автомат выиграет, тот и будет самым искусным кибернетиком.

В день турнира все соревнующиеся принесли большие автоматы, а Клод Шеннон принес маленький. В современных терминах это означает, что его программа была небольшой и изящной. Началось соревнование. Каждая партия протекала так: противники называли 0 или 1, если у обоих автоматов цифры оказывались равными, выигрывал один из них (по предварительной договоренности их создателей), если разные - другой. После этого ходы противников и результат партии (1- выиграл, 0 - проиграл) вводились в автоматы. Это делалось для того, чтобы у автоматов была возможность анализа сыгранных партий и учета полученных результатов в следующих партиях. Когда турнир закончился, оказалось, что с завидным преимуществом выиграл автомат Клода Шеннона.

Кибернетикам не терпелось узнать, что же придумал Клод Шеннон. Оказалось, что его автомат имел две стратегии: одна заключалась в том, что называлось число, совпадающее с ходом противника в предыдущей партии, вторая - в том, что называлось противоположное число. Все обучение заключалось в правиле переключения с одной стратегии на другую. Если в очередных трех партиях автомат одерживал две или три победы, он сохранял стратегию, если нет - менял.

Проанализируем автомат Клода Шеннона. Если считать, что переключение стратегий делает не сам автомат, а, например, его создатель, то автомат Клода Шеннона можно представить в виде двух простых конечных автоматов. Один - просто осуществляет задержку сигнала, то есть передает входной сигнал на выход в следующем такте работы, второй - инвертирует сигнал.

Если мы хотим описать автомат Клода Шеннона  как единый конечный автомат, то число состояний будет гораздо большим. Действительно, автомат имеет две стратегии, для каждой стратегии нужно помнить сколько партий сыграно и сколько из них закончилось победой (это достигается переходами в новые состояния). Кроме того, в начальный момент автомат должен сделать ход, не зная предыдущего хода противника. Так набирается более десятка различных состояний. 

Задача 4.

Опишите в терминах таблиц и графов автомат Клода Шеннона.

Задача 5.

 Напишите программу для игры в чет-нечет, моделирующую автомат Клода Шеннона. Попробуйте модернизировать его, меняя число стратегий (например, возможна стратегия "называть всегда 1") и число партий, после которых осуществляется переключение стратегий. Устройте соревнование между различными версиями программ и определите лучшую из них.

Занимательная деятельность.

Сыграем с автоматом в простую игру. Правила игры такие. На игровом столе лежит кучка предметов (для простоты будем считать, что число предметов не больше 10). За один ход игрок может взять 1, 2 или 3 предмета. Проигрывает взявший последний предмет. Первый ход делаем мы. Ниже в виде таблицы представлен конечный автомат для игры по этим правилам.

Состояние (число предметов в кучке)	1	2	3	4	5	6	7	8	9	10
Взят 1 предмет	-	1	1	2	3	1	1	2	3	1
Взято 2 предмета	-		1	1	2	3	1	1	2	3
Взято 3 предмета	-	-	-	1	1	2	3	1	1	2

В таблице представлены только выходные сигналы - ходы автомата. Определить новое состояние автомата несложно - нужно из текущего состояния вычесть числа, определяющие ходы противников (то есть входной и выходной сигналы).

 Задача 6.

 Проследите за выигрышными путями в графе. Отметьте выигрышные состояния автомата, то есть такие, попав в которые автомат обязательно выигрывает. Опишите стратегию поведения автомата в невыигрышных ситуациях.

 

Двоичный последовательный сумматор

 У конечного автомата число состояний, входной и выходной алфавиты конечны, но, несмотря на это, он может оперировать и с бесконечными объектами. Например, на вход автомата можно подать сколь угодно длинную непериодическую последовательность символов.

Опишем конечный автомат для сложения натуральных чисел сколь угодно большой длины.

Вводить цифры слагаемых будем поразрядно и попарно (одну цифру от одного числа, другую - от другого), начиная с младших разрядов.

Рассмотрим для простоты слагаемые в двоичной записи, тогда входной алфавит будет максимально простым. Он будет состоять из четырех символов: (00), (01), (10), (11), которые включают все возможные комбинации складываемых цифр. Число состояний складывающего автомата будет равно двум, независимо от того, в двоичном или десятичном преставлении вводятся числа. Одно из состояний соответствует тому, что к складываемым единицам разряда надо добавить 1 (один в "уме"). Другое - тому, что этого делать не нужно.

Ниже приведены табличное и графическое представления двоичного последовательного сумматора.

 

Складываемые единицы разряда	Результат сложения (новое состояние)
	Состояние   0 "в уме"	Состояние   1 "в уме"
(00)	0 (0)	1 (0)
(10)	1 (0)	0 (1)
(01)	1 (0)	0 (1)
(11)	0 (1)	1 (1)

 Пример. Рассмотрим протокол сложения чисел 30 и 7.

 В двоичной записи это числа 11110 и 111. Дополним двоичную запись меньшего числа нулями впереди для того, чтобы они стали равной длины. Чтобы получить все цифры результата, нужно учесть возможный перенос разряда и задержку во времени при выдаче цифр результата. Поэтому добавим еще по паре нулей впереди обоих чисел.

Ниже представлен протокол работы автомата. Цифры чисел записаны в обратном порядке.

такты	0	1	2	3	4	5	6
вход	(01)	(11)	(11)	(10)	(10)	(00)	(00)
состояние	0	0	1	1	1	1	0
выход	-	1	0	1	0	0	1

 Прочитаем результат сложения в последней строке справа налево. Получим 100101, или в десятичной системе 37.

 Задача 7.

 Опишите конечный автомат для сложения натуральных чисел в обычной десятичной записи. Сколько символов будет во входном алфавите этого автомата?   Сколько в выходном? 

 Задача 8.

Разработайте и опишите автомат для вычитания двоичных чисел.

Границы возможностей конечного автомата

Конечный автомат является моделью и человеческого мозга и компьютера. Поэтому очень важно понять, каковы же принципиальные ограничения возможностей конечных автоматов. Тогда мы можем узнать принципиальные ограничения человеческих возможностей и возможностей компьютера.

Теорема 1. Если на вход конечного автомата подается постоянный сигнал, то последовательность выходных символов будет периодической.

Доказательство. Поскольку число состояний конечно, автомат в некоторый момент перейдет в одно из уже пройденных ранее состояний. С этого момента начнется зацикливание, так как, по определению конечного автомата, новое состояние и выходной символ определяются только текущим состоянием и входным символом. Но входной символ не изменился, значит, автомат оказался в условиях, идентичных уже имевшимся.

У этой теоремы есть образная формулировка - "предоставленный самому себе конечный автомат зацикливается".

Рассуждение при доказательстве теоремы тоже имеет образную формулировку - "конечный автомат не помнит своей предыстории".

Следствие 1. Не существует конечного автомата, который мог бы вычислить корень из 2 с любой заданной точностью.

Доказательство. Известно, что корень из 2 - число иррациональное. Десятичное представление иррационального числа - непериодическая дробь. На вход автомата, кроме  числа 2, ничего не поступает, следовательно, по теореме 1, конечный автомат не сможет породить бесконечную непериодическую дробь.

Следствие 2. Если входной сигнал постоянен, то период выходной последовательности не превышает числа состояний конечного автомата.

Справедливость этого утверждения следует непосредственно из доказательства теоремы.

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

Доказательство. Докажем теорему в предположении, что числа вводятся парами цифр, начиная с младших разрядов. Предположим, что такой автомат построен и имеет N состояний. Перемножим, например, два одинаковых числа вида 100..00, оканчивающихся N нулями. Тогда результат должен иметь такой же вид, но с 2N нулями. После ввода N цифр произведения автомат должен проработать еще, по крайней мере, N+1 такт, чтобы выдать произведение. При этом на его вход уже ничего не подается (точнее, подается пустой символ). По теореме 1, автомат будет генерировать периодическую последовательность с периодом не больше N. Поэтому, выдав следующие N нулей, он уже не сможет выдать последнюю единицу.