Основные положения и методы теории автоматов. Автоматов теория. Пример вопроса из шпаргалки

Федеральное агентство по образованию

Государственное образовательное учреждение высшего профессионального образования

«МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ПРИБОРОСТРОЕНИЯ И ИНФОРМАТИКИ»

Кафедра ИТ-4 «Персональные компьютеры и сети»

«УТВЕРЖДАЮ»

Заведующий кафедрой ИТ-4

Михайлов Б.М.

«___»__________________2007г.

ЛЕКЦИИ

По дисциплине 1425 «Теория автоматов»

Для студентов 2 курса факультета ИТ

Специальности 230101

«Вычислительные машины, комплексы, системы и сети»

Обсуждены на заседании кафедры

«___»________________2007г.

Протокол № _____

Москва 2007

^ Общие положения

Цели и задачи дисциплины

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

^ Требования к уровню освоения содержания дисциплины

Знания, приобретенные в результате освоения дисциплины:

Принципы и основные понятия теории автоматов;
Применение теории автоматов для построения трансляторов алгоритмических языков;
Применение теории автоматов при разработке устройств и дискретной аппаратуры в рамках персональных ЭВМ;

Умения и навыки, приобретенные в результате освоения дисциплины:

Применение теории автоматов для решения прикладных задач;
Проектирование дискретных устройств;
Проектирование трансляторов;

Основная литература

1. Савельев А.Я. Основы информатики: учебник для вузов.-М.:Издательство МГТУ им. Н.Баумана,2001.-328с.

2. Карпов Ю.Г.Теория автоматов:СПб.:Питер,2003.-224 с.:ил.

3. Зайцев Е.И. Теория автоматов: Учебное пособие.-М.:МГАПИ,2002.-59с.

Дополнительная литература

1. Хопкрофт Д., Мотвани Р., Введение в теорию автоматов, языков и вычислений: пер с англ.-М.:Издат. Дом Вильямс,2002.-528с.

Лекция №1.

Основные понятия и определения

Продолжительность: 2 часа (90) минут

1.1. Ключевые (основные) вопросы (моменты)

Место дисциплины «Теория автоматов» в ряду дисциплин, читаемых на кафедре

Объекты Теории автоматов

Задачи Теории автоматов

Основные понятия и определения.

^ ТЕОРИЯ АВТОМАТОВ.

1.2.1. Основные положения теории автоматов. До 20 минут

Автомат (от греческого   - самодействующий) - управляющая система , являющаяся конечным автоматом или некоторой его модификацией, полученной путем изменения его компонент или функционирования. Основное понятие - конечный автомат - возникло в середине 20 века в связи с попытками описать на математическом языке функционирование нервных систем, универсальных вычислительных машин и других реальных автоматов. Характерной особенностью такого описания является дискретность соответствующих математических моделей и конечность областей значений их параметров, что приводит к понятию конечного автомата.

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

Большинство задач теории автоматов - общие для основных видов управляющих систем. К ним относятся задачи анализа и синтеза автоматов, задачи полноты, минимизации, эквивалентных преобразований автоматов и другие. Задача анализа состоит в том, чтобы по заданному автомату описать его поведение или по неполным данным об автомате и его функционированию установить те или иные его свойства. Задача синтеза автоматов состоит в построении автомата с наперед заданным поведением или функционированием. Задача полноты состоит в выяснении, обладает ли множество M"  M автоматов свойством полноты, т.е. совпадает ли с M множество всех автоматов, которые получаются путем конечного числа применений некоторых операций к автоматам из заданного подмножества автоматов M" . Задача эквивалентных преобразований в общем виде состоит в том, чтобы найти систему правил преобразований (так называемую полную систему правил) автоматов, которые удовлетворяют определенным условиям и позволяют преобразовать произвольный автомат в любой эквивалентный ему автомат (два автомата эквивалентны, если они имеют одинаковое поведение автомата. Поведение автомата - математическое понятие, описывающее взаимодействие автомата с внешней средой. Примером внешней среды конечного автомата является множество входных слов, а поведением - словарная функция, реализуемая автоматом, или событие, представимое автоматом.)

Помимо перечисленных, в теории автоматов имеются специфические проблемы, характерные для автоматов. Так, в зависимости от условий задачи поведение автомата удобно задавать на разных языках, в связи с чем важными задачами являются выбор достаточно удобного адекватного языка и перевод с одного языка на другой. В тесной связи с задачами синтеза и эквивалентных преобразований находится задача минимизации числа состояний автомата, а также получение соответствующих оценок. Близкий круг вопросов возникает в связи с моделированием поведения автоматов одного класса автоматами другого класса. Здесь также представляют интерес вопросы минимизации моделирующих автоматов и оценки их сложности. Специальный раздел теории автоматов связан с так называемыми экспериментами с автоматами (т.е. способами получения информации о внутренней структуре автоматов по их поведению). Основная задача здесь состоит в том, чтобы получить определенные сведения о строении автомата путем наблюдения его реакции на те или иные внешние воздействия. При этом возникает большой круг задач, связанный с классификацией экспериментов и с вопросами разрешимости задач определенными видами экспериментов, а также с оценками длин минимальных экспериментов, достаточных для решения тех или иных задач. Понятие эксперимента с автоматами используется также в задачах надежности и контроля управляющих систем, в частности контроля автоматов. Многие из перечисленных выше задач могут рассматриваться как алгоритмические проблемы. Для конечных автоматов большинство из них имеют положительное решение.

Теория автоматов находит применение как и в других областях математики, так и в решении практических задач. Например, средствами теории автоматов доказывается разрешимость некоторых формальных исчислений. Применение методов и понятий теории автоматов к изучению формальных и естественных языков привело к возникновению математической лингвистики (математическая лингвистика - математическая дисциплина, предметом которой является разработка формального аппарата для описания строения естественных и некоторых искусственных языков.) Понятие автомата может служить модельным объектом в самых разнообразных задачах, благодаря чему возможно применение теории автоматов в различных научных и прикладных исследованиях.

^ 1.2.2. Проблемы и задачи, решаемые теорией автоматов. До 30 минут

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

В этой теории достаточно четко выявляются ее направления, обусловленные:

выбором изучаемых типов автоматов (конечные, бесконечные, детерминированные, вероятностные, автономные, комбинационные, без выхода)
принятым уровнем абстракции (абстрактные и структурные автоматы)
спецификой применяемых математических (алгебраическая теория автоматов)

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

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

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

верификация систем взаимодействующих процессов;

Языки описания документов и объектно-ориентированных программ;

Оптимизация логических программ др.

Об этом можно судить по выступлениям на семинаре " Software 2000…" ученых и специалистов.

Дуг Росс: "…80 или даже 90 % информатики ( Computer Science ) будет в будущем основываться на теории конечных автоматов…"

Herver Gallaire: "Я знаю людей из "Боинга", занимающихся системами стабилизации самолетов с использованием чистой теории автоматов. Даже трудно себе представить, что им удалось с помощью этой теории. "

Brian Randell: "Большая часть теории автоматов была успешно использована в системных программах и текстовых фильтрах в ОС UNIX . Это позволяет множеству людей работать на высоком уровне и разрабатывать очень эффективные программы".

1.1. Основные понятия и определения.

Простейший преобразователь информации (рис.1.1,а) отображает некоторое множество элементов информации Х , поступающее на вход, в некоторое множество на выходе Y . Если множества Х и Y являются конечными и дискретными, то есть преобразование осуществляется в дискретные моменты времени, то такие преобразователи информации называются конечными преобразователями. Элементы множеств Х и Y в этом случае предварительно кодируют двоичными кодами и строят преобразование одного множества в другое.

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

Рис. 1.1.

Таким образом, существуют более сложные преобразователи информации (ПИ), реакция которых зависит не только от входных сигналов в данный момент, но и от того, что было раньше, от входной истории. Такие ПИ называются автоматами (схемами с памятью). В этом случае говорят об автоматном преобразовании информации (рис.1.1,б). На один и тот же входной сигнал автомат может реагировать по-разному, в зависимости от состояния, в котором он находился. Автомат меняет свое состояние с каждым входным сигналом.

Рассмотрим несколько примеров.

Пример 1 1Карпов Ю.Г. Теория автоматов-СПб.:Питер, 2003 . Автомат , описывающий поведение "умного" отца.

Опишем поведение отца, сын которого учится в школе и приносит двойки и пятерки. Отец не хочет хвататься за ремень каждый раз, как только сын получит двойку, и выбирает более тонкую тактику воспитания. Зададим такой автомат графом , в котором вершины соответствуют состояниям, а дуга из состояния s в состояние q , помеченное x/y , проводится тогда, когда автомат из состояния s под воздействием входного сигнала х переходит в состояние q с выходной реакцией y . Граф автомата , моделирующего умное поведение родителя, представлен на рис.1.2. Этот автомат имеет четыре состояния , два входных сигнала - оценки и выходные сигналы , которые будем интерпретировать как действия родителя следующим образом:

Брать ремень;

Ругать сына;

Успокаивать сына;

Надеяться;

Радоваться;

Ликовать.

Рис. 1.2.

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

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

Рис. 1.3.

Аппаратную реализацию автомата рассмотрим во второй части этого раздела.

Пример 2. "Студент"

Автомат , модель которого представлена на рис.1.4 , описывает поведение студента и преподавателей.

Рис. 1.4.

Состояния;

- входные сигналы: "н", "2" и "5".

Выходные реакции:

Пример 3 1 . Электронные часы (рис.1.5).

Электронные часы разнообразных функциональных возможностей являются одним из наиболее широко применяемых в быту электронных приборов, управление которыми построено на основе конечноавтоматной модели. Они обычно показывают: время, дату; у них имеется функции такие как "установка времени и даты", "Секундомер", "Будильник"и т.п. Упрощенная структурная схема электронных часов показана нарис.1.5

Рис. 1.5.

Регистры отображают либо время, либо дату, либо секундомер в зависимости от "Управления". Устройство управления построено на основе модели конечного автомата . Конечный автомат реагирует на нажатия кнопки "а" на корпусе переходом в состояние "Установка минут", в котором событие нажатия кнопки "b" вызовет увеличение числа.

Все рассмотренные выше устройства относятся к классу комбинационных схем, то есть дискретных устройств без памяти. Наряду с ними в цифровой технике широкое распространение получили последовательностные автоматы, или, иначе, комбинационные схемы, объединенные с элементами памяти.

Под термином автомат можно понимать некоторое реально существующее устройство, функционирующее на основании как сигналов о состоянии внешней среды, так и внутренних сигналов о состоянии самого автомата. В этом плане ЭВМ может быть рассмотрена как цифровой автомат. Под цифровым автоматом понимается устройство, предназначенное для преобразования цифровой информации. С другой стороны, под термином автомат можно понимать математическую модель некоторого устройства. Общая теория автоматов подразделяется на две части: абстрактную и структурную теорию автоматов. Различие между ними состоит в том, что абстрактная теория абстрагируется от структуры как самого автомата, так и входных и выходных сигналов. В абстрактной теории анализируются переходы автомата под воздействием абстрактных входных слов и формируемые на этих переходах абстрактные выходные слова.

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

В соответствии с этим принято различать две модели автоматов: структурную и абстрактную. Абстрактная модель применяется при теоретическом рассмотрении автоматов. Структурная модель служит для построения схемы автомата из логических элементов и триггеров и предназначена для выполнения функции управления.

Абстрактный автомат – это математическая модель цифрового автомата, задаваемая шестикомпонентным вектором S=(A,Z,W,d,l,a 1), где А={a a ,…,a m } – множество внутренних состояний абстрактного автомата; Z=}