Теория автоматов.docx - Теория автоматов. Общие понятия
Раздел теоретической кибернетики, в котором изучаются математические модели (называемые автоматами, машинами) реально существующих (технических, биологических и т. п.) или принципиально возможных устройств, перерабатывающих дискретную информацию дискретными временными тактами. А. т. возникла гл. образом под влиянием запросов техники цифровых вычислительных и управляющих машин, а также внутренней потребности теории алгоритмов и математической логики. Понятие «автомата» заметно варьирует в зависимости от характера названных устройств, от принятого уровня абстракции и целесообразной степени общности (автоматы конечные, бесконечные, растущие, вероятностные, детерминированные, автономные и т. п.).
Вопрос же о выработке такого понятия «автомат», которое обладало бы макс. степенью общности и вместе с тем могло бы служить основой для постановки и решения достаточно содержательных задач, нельзя считать еще полностью решенным. Вместе с тем его можно рассматривать как частный случай общего понятия управляющей системы.
Термин «А. т.» вошел в обиход в 50-е годы 20 ст., хотя соответствующая проблематика в значительной мере начала складываться еще в 30-е годы в рамках теории алгоритмов и теории релейных устройств. Еще тогда в алгоритмов теории были сформулированы достаточно общие понятия вычисл. автомата (см. Тьюринга машина) и (неявно) понятие автомата конечного (головка машины Тьюринга). Было установлено, что для осуществления
всевозможных эффективных преобразований информации вовсе не обязательно строить каждый раз специализированные автоматы; в принципе все это можно сделать на одном универсальном автомате при помощи подходящей программы и подходящего кодирования. Этот теор. результат позже получил инженерное воплощение в виде современных универсальных вычисл. машин. Однако развернутое изучение процессов, протекающих в автоматах различного рода, и общих закономерностей, которым они подчинены, началось позднее лишь в рамках А. т. Различие в постановках между задачами теории алгоритмов и А. т. можно кратко охарактеризовать как различие между вопросами о том, что могут делать автоматы и как они это делают. Поскольку привлечение др. типов автоматов (отличных от машин Тьюринга) заведомо не расширяет запаса вычислимых преобразований информации, то для теории алгоритмов такое привлечение носит лишь эпизодический характер и связано только с применяемой техникой доказательств. С другой стороны, для А. т. такое рассмотрение становится уже самоцелью. Теор. и прикладные задачи автоматики, вычисл. техники и программирования, моделирования биол. поведения и др. продолжают стимулировать проблематику А. т. Однако наряду с этим, А. т. уже вырабатывает собственную внутреннюю проблематику. В А. т. широко применяется аппарат алгебры, логики математической, комбинаторного анализа (включая графов теорию) и вероятностей теории.
В А. т. достаточно четко вырисовываются отдельные ее направления, обусловленные выбором изучаемых типов автоматов (конечных, вероятностных и т. п.), принятым уровнем абстракции (см. Абстрактная теория автоматов, Структурная теория автоматов) или спецификой применяемых матем. методов (см. Алгебраическая теория автоматов). Наряду с этим родственные задачи и методы интенсивно развиваются в теории релейных устройств, в теории ЦВМ ив теории программирования, поэтому зачастую трудно бывает различать сферы действия этих теорий и А. т.
Поведение и структура. В основе А. т. лежат точные матем. понятия, формализующие интуитивные представления о функционировании и поведении автомата, а также о его структуре (внутреннем устройстве). С точки зрения их поведения, автоматы чаще всего рассматриваются как преобразователи словарной информации, т. е. преобразователи последовательностей букв в последовательности букв. Реализуемое преобразование интерпретируется обычно как вычисление значений некоторой ф-ции (оператора) по заданным значениям аргументов или как преобразование записей условий задач некоторого типа в записи соответствующих решений. В частности, т. н. распознающие автоматы, воспринимая входную информацию, реагируют на нее так, что некоторые входные последовательности сигналов они принимают, а другие - отвергают. В этом смысле они распознают или, как говорят еще, представляют мн-ва входных последовательностей. Наконец, порождающий автомат функционирует как автономная система, не связанная со входной информацией, его поведение определяется тем, какие выходные последовательности он способен порождать. Приведенная классификация в терминах преобразования, распознавания и порождения зависит от правил функционирования автомата, т. е. от программы взаимодействия его внутренних состояний со входными (поступающими из внешней среды) и выходными (вырабатываемыми во внешнюю среду) сигналами. Пусть Q, X, Y - соответственно мн-ва внутренних состояний входных и выходных сигналов автомата. Если это детерминированный автомат, его программа формализуется в терминах ф-ции переходов Ч и ф-ции выходов Ф, указывающих для каждого входного сигнала х и каждого состояния состояние в которое переходит автомат, и вырабатываемый им при этом выходной сигнал
Абстрактная А. т. характеризуется более высоким уровнем абстракции: в ней понятие автомата отождествляется с понятием программы автомата, т. е. с пятеркой (), при полном отвлечении от его структуры. Структура автомата отражает способ его организации из более простых взаимодействующих компонент (элементарных автоматов или просто - элементов), надлежащим образом соединенных в единую систему. Напр., вычисл. машина составлена из элементарных ячеек типа триггеров, инверторов и т. п.; нервная система построена из нейронов. Структурная классификация автоматов определяется характером допускаемых соединений (соединения могут быть жесткими или же изменяться в процессе работы, подвергнуты тем или иным геом. ограничениям), а также спецификой функционирования и взаимодействия употребляемых элементов (напр., элементы могут только обмениваться информацией или же они могут порождать новые элементы, наращивая структуру). Формализация структурных понятий осуществляется в терминах различного рода схем (см. Сеть логическая). А. Н. Колмогоров наметил подход, приведший к формулировке весьма общего, но все еще конструктивного понятия структуры автомата (см. Автоматы растущие), которое, по-видимому, охватывает все известные типы структур автоматов и все те, которые можно предвидеть на современном уровне науки. Вполне очевидно, что имеется тесная связь между структурой автомата и его поведением. Однако раздельное изучение каждого из этих двух аспектов при значительном отвлечении от другого не только возможно, но зачастую и полезно при постановке и решении многих важных проблем. Такое изучение производится соответственно в абстрактной (поведенческой) и структурной теории автоматов.
Типы автоматов. Наиболее распространенной является классификация автоматов и со-отв. разделов А. т., посвященных различным
типам автоматов, по следующим признакам.
1) Объем памяти. Конечные и бесконечные автоматы характеризуются соотв. конечностью и бесконечностью объема памяти (числа внутренних состояний). Конечными автоматами являются отдельные блоки современных вычисл. машин и даже машина в целом. Мозг также можно рассматривать как конечный автомат. Бесконечные автоматы представляют собой естественную матем. идеализацию, вырастающую из представления об автомате с конечным, но необозримо большим числом состояний. При этом имеется в виду лишь потенциальная бесконечность памяти, проявляющаяся в том, что память, хотя и остается конечной в каждый момент времени, может неограниченно возрастать. Такая идеализация возникла впервые в рамках теории алгоритмов в процессе уточнения интуитивного представления об алгоритме. Структурно-растущий автомат представляют в виде соединения элементов, способных к размножению и наращиванию схемы. Современные ЭВМ можно рассматривать как растущие (а вместе с тем и потенциально бесконечные) автоматы в следующем смысле: чтобы вычисления во всех случаях могли быть доведены до конца, приходится допускать возможность неограниченного наращивания внешней (ленточной) памяти.
2) Механизм случайного выбора. В детерминированных автоматах поведение и структура в каждый момент времени однозначно определены текущей входной информацией и состоянием автомата, сложившимся в непосредственно предшествующий момент. В вероятностных (стохастических) автоматах они зависят еще и от некоторого случайного выбора. Стохастические автоматы не следует смешивать с недетерминированными, в которых так же нарушено условие однозначности (однако без участия к.-л. механизма случайного выбора).
Проблемы и методы. К центр, проблемам А. т. относятся проблемы анализа, т. е. описания поведения автомата, исходя из заданной его программы или структуры, и синтеза - т. е. конструирования автоматов, поведение которых удовлетворяло бы заранее предъявляемым требованиям. С этими проблемами тесно связаны и многие др. задачи, которые интенсивно исследуются (полнота и универсальность, минимизация, языки, асимптотические оценки и др.). Более всего анализ и синтез исследованы в теории конечных детерминированных автоматов, причем они по-разному трактуются в абстрактной и в структурной теориях автоматов. Так, напр., в структурной теории под синтезом (см. Синтез автоматов структурный) подразумевается построение схемы из заданного ассортимента элементов, которая была бы оптим. (или близка к оптим.) в смысле некоторого выдвигаемого критерия сложности схем. Здесь преобладают комбинаторно-информационные методы и асимптотические оценки (К. Шэннон, С. В. Яблонский, О. Б. Лупанов и др.). В абстрактной теории автоматов довольствуются построением программы функционирования автомата (см. Синтез автоматов абстрактный), напр., в виде ф-ций перехода и выхода для конечного автомата, которая обычно служит исходным материалом для дальнейшего развертывания структурного синтеза. Здесь используются преимущественно алгебраические (С. К. Клини, В. М. Глушков и др.), математико-логич. (Б. А. Трахтенброт, Р. Бюхи и др.) и игровые (Р. Мак-Нотоп) методы и понятия. Проблема анализа и синтеза конечных детерминированных автоматов занимает видное место и в теории релейных устройств.
В теории экспериментов с автоматами (Э. Мур) разрабатываются методы, которые позволяют по сведениям, получаемым при внешнем наблюдении за поведением автомата, восстанавливать программу его функционирования или по крайней мере некоторые ее свойства. Эти методы можно рассматривать как своеобразный прием абстрактного синтеза и расшифровки автоматов (Я. М. Барздинь). Работы К. Шэннона, М. Рабина и др. послужили толчком к развитию теории вероятностных автоматов в следующих направлениях: 1) в какой мере понятия и методы теории детерминированных автоматов переносятся на стохастические автоматы; 2) какие упрощения вычисл. процесса достижимы при выходе из более узкого класса детерминированных автоматов в более широкий класс автоматов вероятностных. Изучение растущих автоматов сосредоточено в основном на следующих проблемах: 1) разработка моделей растущих автоматов и изучение отдельных их классов (автоматы итеративные - Ф. Хенни, автоматы регистровые - В. М. Глушков, автоматы самовоспроизводящиеся - Дж. фон Нейман, обобщенные растущие автоматы - А. Н. Колмогоров, Я. М. Барздинь); 2) оценка вычисл. способности и сложности вычислений растущих автоматов (Я. М. Барздинь, Б. А. Трахтенброт, Ю. Хартманис, Г. С. Цейтин, М. Рабин и др.).
Связь с другими научными направлениями.
Значение теории алгоритмов и теории релейных устройств для А. т. уже было разъяснено выше. Следует указать и на обратную отдачу А. т., методы которой позволили решить ряд задач, возникших в матем. логике и теории алгоритмов (Р. Бюхи). Проблематика, складывающаяся в теории растущих автоматов (напр., сложность вычислений), лежит по существу на стыке теории алгоритмов и асимптотических закономерностей структурного синтеза автоматов. Сильное взаимное проникновение А. т. и лингвистики математической, одним из важных понятий которой является грамматика порождающая, - объект весьма близкий к порождающему автомату. Поэтому отдельные довольно важные положения теории грамматик могут быть в принципе отнесены к А. т. В абстрактной теории автоматов матем. вопросы обучения, а также целесообразного поведения одного индивидуума или коллектива были уточнены и исследованы в терминах автоматов игр (М. Л. Цетлин). Полезной
оказалась также связь теории конечных автоматов с теорией проектирования ЦВМ и теорией программирования (В. М. Глушков, А. А. Летичевский).
Лит.: Гаврилов М А. Теория релейно-контактных схем. М.- Л., 1950 [библиогр. с. 298-299]; «Труды математического института им. В. А. Стеклова АН СССР», 1958, т. 51; Глушков В. М. Синтез цифровых автоматов. М., 1962 [библиогр. с. 464- 469]; Кобр инский Н. Е., Трахтенброт Б. А. Введение в теорию конечных автоматов. М., 1962 [библиогр. с. 399-402]; Цетлин М. Л. Исследования по теории автоматов и моделированию биологических систем. М., 1969 [библиогр. с. 306-316]; Трахтенброт Б. А., Барздинь Я. М. Конечные автоматы (Поведение и синтез). М., 1970 [библиогр. с. 389-395]; Автоматы. Пер. с англ. М., 1956. Б. А, Трахтенброт.
АВТОМАТОВ ТЕОРИЯ, раздел дискретной математики, изучающий математические модели преобразователей дискретной информации, называемых автоматами. Примерами таких преобразователей являются как реальные системы (вычислительные машины, технические автоматы, живые организмы), так и абстрактные системы (абстрактные вычислительные машины, аксиоматические теории). Автоматов теория возникла в середине 20 века в связи с изучением автоматов как математических моделей биологических систем и вычислительных машин. В дальнейшем проблематика автоматов теории существенно расширилась.
Автоматов теория тесно связана с теорией алгоритмов, в частности с теорией абстрактных вычислительных машин, поскольку автоматы можно рассматривать как случай их аппроксимации.
Автомат можно охарактеризовать как устройство, имеющее входной и выходной каналы и находящееся в каждый дискретный момент времени в одном из внутренних состояний. По входному каналу в такой момент поступают сигналы-воздействия. В те же моменты по выходному каналу устройство выдаёт сигналы-реакции. Состояния автомата, сигналы-воздействия и сигналы-реакции задаются буквами соответствующих алфавитов: алфавита состояний, а также алфавитов входных и выходных сигналов. Законы взаимодействия букв этих алфавитов задаются двумя функциями - функцией переходов и функцией выходов, отображающими пары (состояние - входная буква), в состояния и выходные буквы соответственно. Входной средой для автомата является множество слов во входном алфавите, а внутренней и выходной его средами являются множества слов в алфавите состояний и выходном алфавите. Автомат побуквенно перерабатывает слова из входной среды в слова двух других сред. Этот процесс называется поведением автомата. Свойства алфавитов и функций определяют различные типы автоматов. В случае, когда все алфавиты конечны, получают конечный автомат, в противном случае автомат называют бесконечным. Замена функций на отношения приводит к частичным и недетерминированным автоматам; использование случайных функций приводит к вероятностному автомату. При интерпретации входной среды термами или графами приходят к автоматам над термами и автоматам в лабиринтах.
Большинство задач автоматов теории являются общими для основных видов управляющих систем, к ним относятся задачи анализа и синтеза автоматов, задачи о полноте, минимизации, а также задачи, связанные с эквивалентными преобразованиями автоматов. Задача анализа состоит в том, чтобы по заданному автомату описать его поведение или по неполным данным об автомате и его функционированию установить те или иные его свойства. Задача синтеза состоит в построении автомата с заданным поведением, или функционированием. К этой задаче примыкают проблемы, связанные с оценкой сложности автоматов, обладающих заданным поведением, а также с построением оптимальных в определённом смысле автоматов. Задача о полноте состоит в том, чтобы выяснить, можно ли данное множество автоматов получить из меньшего множества с помощью некоторых операций над автоматами. Задача минимизации автоматов состоит в минимизации значений параметров автоматов (например, числа состояний), при которой получается автомат, эквивалентный в том или ином смысле исходному. Помимо задач, общих для основных видов управляющих систем, в автоматов теории рассматриваются специфические проблемы, характерные для автоматов. Так, в зависимости от условий задачи поведение автоматов удобно задавать на разных языках (регулярные выражения, канонические уравнения, язык логики предикатов и т.п.), в связи, с чем важными задачами являются выбор достаточно удобного адекватного языка и перевод с одного языка на другой. С задачами синтеза и эквивалентных преобразований связана задача минимизации числа состояний автомата. В связи с моделированием поведения автоматов одного класса автоматами другого класса возникают задачи минимизации моделирующих автоматов и оценки их сложности. Специальный раздел автоматов теории связан с так называемыми экспериментами с автоматами. Основная задача этого раздела состоит в том, чтобы получить определённые сведения о строении автомата путём наблюдения его реакции на те или иные внешние воздействия. При этом возникают задачи, связанные с классификацией экспериментов и с вопросами разрешимости задач определёнными видами экспериментов, а также с оценками длин минимальных экспериментов, достаточных для решения тех или иных задач. Понятие эксперимента с автоматами используется также в задачах контроля автоматов. Специальными разделами автоматов теории являются игры автоматов и поведение автоматов в случайной среде, в которых рассматриваются вопросы взаимодействия автоматов друг с другом и с определёнными внешними средами. Многие из перечисленных выше задач могут рассматриваться как массовые проблемы (смотри Алгоритмическая проблема). Для конечных автоматов большинство из них имеет положительное решение.
Автоматов теория находит применение во многих областях. Например, средствами автоматов теории доказывается разрешимость некоторых формальных исчислений. Методы и понятия автоматов теории существенно используются в математической лингвистике. Понятие автомата может служить модельным объектом в разнообразных задачах, благодаря чему возможно применение автоматов теории в различных прикладных исследованиях.
Лит.: Кудрявцев В. Б., Алешин С. В., Подколзин А. С. Введение в теорию автоматов. М., 1985.
Федеральное агентство по образованию
Государственное образовательное учреждение высшего профессионального образования
«МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ПРИБОРОСТРОЕНИЯ И ИНФОРМАТИКИ»
Кафедра ИТ-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" вызовет увеличение числа.
Вятский Государственный Университет
ФАКУЛЬТЕТ АВТОМАТИКИ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ
Кафедра Электронных Вычислительных Машин
Теория автоматов (часть I) Конспект лекций
Теория автоматов (часть I). Конспект лекций /Киров, Вятский государственный университет, 2010, 56с.
В конспекте лекций по курсу «Теория автоматов» (Часть I) приведен необходимый теоретический материал, включающий основы прикладной теории цифровых автоматов, основные определения и правила синтеза абстрактных конечных автоматов, схема дискретного преобразователя В.М. Глушкова и три основных модели конечных автоматов: модель Мили, модель Мура и модель С-автомата. Далее рассмотрены методы кодирования элементов памяти, минимизация автоматов с памятью, канонический метод синтеза структурных автоматов. Особое внимание уделено правилам построения оптимальной комбинационной схемы автомата по каноническим уравнениям с учётом выбранных элементов памяти. Указана соответствующая литература.
Курс лекций предназначен для студентов очного обучения специальности 230101 - "Вычислительные машины, комплексы, системы и сети", а также бакалавров направления 230100.62 – "Информатика и вычислительная техника".
Составитель: к.т.н., доцент каф. ЭВМ В.Ю. Мельцов.
Вятский государственный университет, 2010
Мельцов В.Ю.
1. Введение 4
2. Задачи анализа и синтеза 4
3. Абстрактный управляющий автомат 7
4. Синтез абстрактных автоматов 9
5. Синхронный автомат 10
6. Асинхронные автоматы 11
7. Автоматы Мили и Мура 12
8. Способы задания автоматов 14
8.1 Табличный способ задания автоматов 15
8.2. Задание автомата с помощью графа 17
8.3. Матричный способ задания автоматов 19
9. Переход от автомата Мили к автомату Мура и обратно 19
10. Этапы синтеза автоматов 23
11. Минимизация числа внутренних состояний автомата 26
12. Минимизация полностью определённых автоматов. 27
13. Совмещённая модель автомата (C-автомата) 31
14. Структурный синтез автомата 32
14.1. Канонический метод структурного синтеза автомата 32
14.2. Структурный синтез С-автомата 35
15. Кодирование состояний автомата 41
15.1. Метод противогоночного кодирования состояний автомата 42
15.2. Соседнее кодирование состояний автомата 45
15.3. Кодирование состояний автомата для минимизации комбинационной схемы 47
16. Элементарные автоматы памяти 50
17. Синтез автоматов на ПЛМ и ПЗУ 54
1. Введение
В последние годы с большой интенсивностью ведутся исследования и работы по созданию и применению различных автоматических систем для обработки информации. Такие системы обычно реализуются в виде блоков, образующих систему управления и переработки информации. В соответствии с этим возникла новая научная дисциплина, которая получила название «Теория систем».
Целью теории систем является задача создания арсенала идей и средств, которые были бы в равной степени полезны специалистам в самых различных областях (электротехника, механика, физика, химия, социология и т.п.). Данная цель достигается путем рассмотрения системы не через ее внутреннюю структуру, а через математические законы, определяющие ее наблюдаемое поведение. При этом наиболее часто используется подход, называемый методом «черного ящика» (т.е. метод, в котором анализируются входные данные и данные, получаемые на выходе автомата, при этом внутренние процессы не рассматриваются). Было доказано, что все системы могут быть охарактеризованы в одинаковых терминах и проанализированы с помощью одного и того же набора правил.
Составной частью теории систем является теория автоматов. Она имеет дело с математическими моделями, предназначенными для в той или иной степени приближенного отображения физических явлений. Применение модели теории автоматов не ограничивается какой-либо частной областью, а возможно для решения проблем практически в любой области исследования.