Раздел 5. Конечные автоматы»




 

Алан Тьюринг (фото на паспорт, 16 лет)

 

Алан Матисон Тьюринг родился 23 июня 1912 года в Лондоне в семье колониального чиновника, служившего в Индии. В 1935 году он защитил диссертацию «Центральная предельная теорема теории вероятности» (которую он самостоятельно переоткрыл, не зная об аналогичной предшествующей работе) и был избран членом Научного общества колледжа. В этом же году он впервые начал работать в области математической логики и проводить исследования, которые уже через год привели к выдающимся результатам. В своей работе «О вычислимых числах, с приложением к проблеме разрешимости» (1936) Тьюринг ввел математическое понятие абстрактного алгоритма, или вычислимой функции, получившее затем название «машины Тьюринга». Это был прообраз конечного автомата, устройства, имеющего все основные свойства современной информационной системы: программное управление, память и пошаговый способ действий. "Машина Тьюринга" открыла дискуссию по теории автоматов и создала теоретическую базу для работы цифровых компьютеров, которые появились в 1940-е годы. Тьюринг продолжил учебу в США – в Принстонском университете, где под руководством американского математика и логика Алонзо Чёрча в 1938 году получил степень доктора философии. Затем он вернулся в Великобританию и получил стипендию Кингз-колледжа для занятий логикой и теорией чисел.

В это же время началось его конфиденциальное сотрудничество с правительственной Школой кодов и шифров, где он еще до войны участвовал в работах по раскрытию немецких шифров. В 1939 году британское военное ведомство поставило перед Тьюрингом задачу разгадать секрет "Энигмы" – специального устройства, использовавшегося для шифровки радиограмм в германском военно-морском флоте и в "люфтваффе". Британская разведка раздобыла это устройство, но расшифровывать перехваченные радиограммы немцев не удавалось. Тьюринг пригласил в созданный им отдел нескольких друзей-шахматистов. Уже через полгода было разработано устройство, названное им «Бомбой», которое позволяло читать практически все сообщения «люфтваффе». А спустя ещё год был взломан и более сложный вариант «Энигмы», использовавшийся нацистскими подводниками. Это во многом предопределило военные успехи британского флота.

Тьюринг занимался также разработкой шифров для переписки премьер-министра Великобритании Уинстона Черчилля и президента США Франклина Рузвельта, проведя период с ноября 1942 года по март 1943 года в США. Заслуги Алана Тьюринга были по достоинству оценены: после разгрома Германии он был удостоен звания кавалера Ордена Британской империи 4-й степени.

Оказалось, что исследования Тьюринга явились одними из самых важных исследований XX века. То, что сейчас в разных устройствах – скажем, в телевизоре и в стиральной машине, – может использоваться одна и та же микросхема процессора, – это воплощение идей Тьюринга. И то, что одна и та же программа может использоваться в самых разных компьютерах, работать с самой разной аппаратурой и выглядеть одинаково, это тоже его идея. Тогда это называлось идеей хранимой программы (программа хранится в памяти и определяет поведение машины), и еще была идея универсальной машины, – то есть машины, которая может делать все, что может делать любая другая машина. Если бы не Тьюринг, пожалуй, это придумал бы кто-то другой, он не был единственным, кто над этим работал, но так или иначе абстрактное теоретическое устройство «конечный автомат» оказалось одним из самых важных изобретений в XX веке.

Современная теория автоматов – сравнительно молодая наука. Началом её возникновения считается середина 50-х годов прошлого столетия. В это время в нескольких научных центрах СССР и США велись исследования по созданию математической модели дискретного преобразователя с конечной памятью, осуществляющего последовательную переработку информации. За 50 лет своего существования теория автоматов превратилась в самостоятельную математическую дисциплину с широким кругом собственных проблем и методов и многочисленными связями с другими разделами математики и естествознания в целом. Оказалось, что идея дискретного преобразователя с конечной памятью – идея конечного автомата – находит применение в целом ряде математических дисциплин: математической логике и теории алгоритмов, алгебре, теории вероятностей, кибернетике, программировании, теории графов и теории формальных языков. Что касается современной техники, то едва ли не каждое достаточно сложное техническое устройство можно рассматривать как конечный автомат. В первую очередь это относится к устройствам, имеющим память. Однако многие промышленные и бытовые преобразователи (механические, электро-механические, электронные) также следует отнести к конечным автоматам. Само понятие конечного автомата представляется весьма простым и, по-видимому, в содержательном виде давно использовалось многими математиками и инженерами. В нём формализуется идея дискретного преобразователя информации, который работает над линйными последовательностями символов и в процессе работы использует конечную память (конечное число состояний). Как показала история рождения и развития теории автоматов, эту идею можно формализовать различными способами: чисто функционально с помощью систем уравнений, на языке теории графов (диаграммы Мура), а также с помощью логических сетей (схем) определённого вида. Простота и доступность понятия конечного автомата способствовали тому, что в короткое время основами теории конечных автоматов овладело большое число специалистов из различных областей естествознания. Это привело к проникновению идей и методов теории автоматов в различные математические (и не только!) дисциплины, к постановке и решению с их помощью задач, зачастую весьма далёких от конечных автоматов.


5.1. Основные понятия, определения и алгоритмы

Определение 1. Под конечным автоматом будем понимать математическую модель вычислительного устройства с фиксированным и конечным объемом памяти, которое «читает» последовательность входных символов из некоторого конечного множества.

Определение 2. Конечные автоматы, определяющие допустима или недопустима данная последовательность символов, называются конечными распознавателями. Конечный распознаватель задается следующим образом:

1. На вход конечного распознавателя подается цепочка символов из некоторого конечного множества, называемого входным алфавитом.

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

3. Одно из состояний автомата выделяется в качестве начального – S0.

4. При чтении очередного входного символа состояние автомата меняется, причем новое состояние зависит от входного символа и текущего состояния автомата. Этот переход задается с помощью функции переходов.

5. Некоторые состояния автомата выбираются в качестве допускающих. Если автомат, начав работу в состоянии S0, после прочтения всей цепочки переходит в одно из допускающих состояний, будем говорить, что входная цепочка допускается автоматом. Если последнее состояние не является допускающим, то цепочка отвергается.

Целиком конечный автомат задается с помощью матрицы переходов (или таблицы переходов), у которой столбцы помечаются символами входного алфавита, строки – символами состояний, первая строка всегда помечается начальным состоянием. Элементами матрицы являются символы новых состояний, соответствующие значению функции переходов для данной строки и данного столбца. Строки, соответствующие допускающим состояниям, помечаются справа единицей, а отвергающим – нулем.

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

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

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

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

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

Определение 4. Цепочка, под действием которой, одно из пары состояний переходит в допускающее, а другое – в отвергающее называется различающей для этих состояний.

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

Алгоритм поиска эквивалентных состояний основан на двух условиях:

а) условие подобия – состояния S и T подобны, если они оба или отвергающие, или допускающие;

б) условие преемственности – состояния S и T преемственны, если для любых входных символов они переходят в эквивалентные состояния.

Утверждение. Состояния S и T эквивалентны, если они подобны и преемственны.

Алгоритм поиска эквивалентных состояний (алгоритм а)

Этот алгоритм будем трактовать как алгоритм проверки на неэквивалентность, и искать различающую цепочку.

1. Строим таблицу эквивалентности для пары проверяемых состояний, отводя столбец под каждый входной символ, а проверяемую пару заносим в виде метки первой строки.

2. Выбираем в таблице строку, ячейки которой еще не заполнены и ставим справа знак «+», если проверяемые состояния подобны или знак «-» в противном случае. При появлении первого знака «-» процедуру заканчиваем.

Если для некоторой строки был поставлен знак «+», записываем в ячейки преемников для пары-метки строки.

3. Для каждой ячейки таблицы на шаге 2 существует три возможности:

a. получена пара одинаковых состояний – помечаем ее одним символом и никаких действий не производим.

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

c. если появилась пара новых различных состояний – заводим для нее новую строку.

4. Если все строки заполнены, то исходная пара состояний и все остальные, порожденные в ходе проверки, эквивалентны.

5. Если заполнены не все строки – возвращаемся к шагу 2.

6. Конец алгоритма.

 

Алгоритм поиска эквивалентных состояний (алгоритм б)

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

1. Строим разбиение P0, содержащее два подмножества состояний (или блока разбиения) так, что одно подмножество состоит из всех допускающих, а другое – из всех отвергающих состояний.

2. Исследуем все переходы каждого блока разбиения по каждому входному символу и если преемники двух состояний находятся в разных блоках, то эти состояния помещаем в разные блоки.

3. Повторяем шаг 2 до тех пор, пока он не перестанет давать разные результаты по всем входным символам.

4. Конец алгоритма

Эквивалентные состояния можно объединить в одно. Для этого нужно заменить все имена эквивалентных состояний одним символом.

Определение 5. Недостижимыми состояниями конечного автомата называются те состояния, в которые автомат не может перейти из начального ни при каких входных цепочках.

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



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-06-21 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: