Теория автоматов. Учебное пособие. Шпаргалка по теории автоматов (ТА) Основные понятия и определения

Вятский Государственный Университет

ФАКУЛЬТЕТ АВТОМАТИКИ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ

Кафедра Электронных Вычислительных Машин

Теория автоматов (часть 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. Введение

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

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

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

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

ВВОДНЫЕ ПОЛОЖЕНИЯ.

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

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

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

принятым уровнем абстракции (абстрактные и структурные автоматы)

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

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

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

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

Основные понятия теории автоматов

Абстрактный конечный автомат U - модель , представляющая устройство, которое преобразует информацию по правилам R в виде «черного ящика», имеющего входной А и выходной В алфавиты, а также некоторое множество внутренних состояний Q.

a i  A , b j  B, q k  Q

Когда на вход подается сигнал a i , то в зависимости от него и текущего состояния q k  Q автомат переходит в следующее состояние q l  Q и выдает сигнал на выход b j  B. Это – один такт действия автомата q k a i  q l b j . Затем подается следующий сигнал, наступает следующий такт и т.д. Изменение сигнала на входе меняет состояние автомата и его выходной сигнал означает элементарное преобразование поступающей в виде сигналов информации.

Бесконечный автомат – абстрактный автомат, хотя бы одно из определяющих множеств A, B, Q которого бесконечно.

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

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

Структурный автомат - конечный автомат, внутреннее устройство которого известно.

Формальная грамматика = - система правил построения P в заданном алфавите TH(T – терминальный алфавит, Н – нетерминальный алфавит, ТН=) конечных знаковых последовательностей, множество которых образует некоторый формальный язык () (JH, Н - аксиома).

Формальный язык - язык, построенный по правилам некоторого логического исчисления (иначе – язык, синтаксис которого определен формальной грамматикой ).

Слово – цепочка символов в некотором алфавите (принято цепочки в алфавите (TH) обозначать греческими буквами; так, например,  (TH)*).

Предложение – слово в терминальном алфавите.

Продукция (синтаксическое правило) – способ преобразования цепочки вида  (, ,  (TH)*) в цепочку вида  ((TH)*).

Дерево вывода (разбора) – форма наглядного представления вывода предложения в заданной грамматике.

АВТОМАТЫ И ФОРМАЛЬНЫЕ ЯЗЫКИ.

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

Классы языков по Хомскому являются иерархией, т.е. язык типа 3 является подклассом языка типа 2, т.е. ( 3) ( 2) ( 1)  ( 0). Следуя приведенной таблице, можно говорить, что

регулярный язык (т.е. язык, порождаемый грамматикой типа 3) распознается конечным автоматом и в этом плане является самым простым в математическом плане

бесконтекстный язык (т.е. язык ( 2)) распознается магазинным автоматом – бесконечным автоматом, внутренняя структура которого представляет собой стековую память

контекстный язык ( 1) распознается автоматом с линейно-ограниченной памятью, т.е. автоматом, которому для распознавания последовательности длины nN необходима память объемом не более k*n, где k – число, независящее от входного слова

произвольный формальный язык, т.е. ( 0), распознается машиной Тьюринга – математического понятия для формального уточнения интуитивного понятия «алгоритм»

Замечание : В синтаксическом правиле В являются контекстами (левый и правый), которые могут быть пустыми цепочками; ВН, а,, ,   (ТН).

ФОРМАЛЬНЫЕ ГРАММАТИКИ.

Формальные грамматики = как процедуры могут быть порождающими и распознающими. Порождающая грамматика по существу является частным случаем формальной системы FS / =<, D>-=. В этом случае A=TH, F(TH) * , JH, P= i  j  i , j  N ,  i ,  j (TH) * , т.е. правила вывода P позволяют получать слова в терминальном алфавите Т из единственной аксиомы J путем замещения нетерминальных символов цепочек в алфавите (TH).

Распознающая грамматика – алгоритм, распознающий по любой цепочке, является ли оно словом языка  T * .

Автомат для распознавания и порождения слов можно рассматривать как устройство обработки входных цепочек символов с целью:

определения их принадлежности формальному языку ()

порождений выходных цепочек символов

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

Пример 1 : Т=a, b, c, H=B, C, J=B, P=BaBС, BCc, Cb

Возможным выводом в этой грамматике может быть последовательность слов:

В, аВС, аСсС, аbсС, аbсbТ *

Эта грамматика порождает язык b, bc, abcb.

Пример 2 : множество нечетных чисел в унарном представлении – это множество терминальных слов вида а, ааа, ааааа….., т.е. язык =хТ * : ха 2 n -1 , nN. Этот язык порождается автоматной грамматикой  3 =<a, J, J, Ja, JaB, BaJ>.

Пример 3 : Язык =хТ * : х=a n b n  n  N порождается К.С. грамматикой, т.е.  2 =<a, b, J, J, JaJb, Jab>.

Пример 4 : Язык булевых формул с переменными x, y, z порождается К.С. грамматикой  2 =<x, y, z, , , , (,), J, J, J(JJ), J(JJ), JJ, Jx, Jy, JZ>.

ДЕРЕВЬЯ ВЫВОДА ПРЕДЛОЖЕНИЙ.

На практике вывод слов языка () в виде последовательности цепочек часто оказывается громоздким. Кроме того, такой способ не позволяет получить в удобном виде информацию о синтаксических конструкциях. Наилучшим способом компактного представления вывода слов в таком случае является дерево вывода (дерево синтаксического анализа, дерево грамматического разбора). Говорят, что задано стандартное дерево вывода, если правилу r i:  1 A 2  1  2 (здесь  1 ,  2 – контекст,  1 ,  2 (TH) *), АН, (TH) *) поставлено в соответствие элементарное поддерево t(r i) с вершиной А и кроной  1  2.

Пример 1 : Пусть 1=<a, b, c, A, B, C, D, J, J, JAAB, ABDBB, aBBabB, Aa, Da, BC, Cc>.

Вывод J, AAB, aAB, aDBB, aaBB, aabB, aaaBC, aabc представим деревом:

ЗдесьJ – корень дерева, J A , A a - поддеревья.

Каждый вопрос размещен на одной отдельной странице (кроме одного - "Алгебраическая и структурная теория КА", который занимает две страницы). Формат шпаргалки: doc.

Вопросы шпаргалки

1. Предмет теории автоматов
2. Классификация автоматов
3. Приложения теория автоматов
4. Двоичное умножение
5. Умножение в инверсных кодах
6. Деление
7. Деление в инверсных кодах. Особенности
8. Особенности выполнения операций в формате с плавающей запятой
9. Двоично-десятичные коды. Сложение в ДДК
10. Модель дискретного преобразователя Глушкова
11. Микропрограммирование
12. Структуры операционных автоматов
13. Синтез операционного автомата (ОА) процедурного типа
14. Синтез ОА структурного типа
15. Автоматные языки. Формальное задание Автомата
16. Модели автоматов Мили и Мура
17. Эквивалентность конечных автоматов (КА). Теорема Мура
18. Минимизация конечных автоматов
19. Эквивалентность автомата Мили и Мура
20. Виды управляющего автомата (УА)
21. Структурные схемы УА. Мили и Мура
22. Этапы синтеза управляющего автомата с жесткой логикой (УАЖЛ)
23. Примеры синтеза УАЖЛ
24. Гонки и способы борьбы с ними
25. УА с программируемой логикой (УАПЛ)
26. Алгебраическая и структурная теория КА
27. Объединение нескольких УА в один
28. Программная реализация КА. Варианты реализации. Шаблон Состояние
29. Назначение и краткая характеристика VHDL
30. Реализация УА на VHDL
31. Понятие о языке моделирования UML
32. Понятие о языках и формальных грамматиках
33. Классификация языков
34. Лемма о накачке
35. Понятие о НКА. Получение ДКА по НКА
36. Регулярные выражения. Синтаксические диаграммы. Теорема Клини
37. Применение РВ. Различные нотации РВ
38. КС-грамматики и магазинные автоматы
39. Машины Тьюринга
40. Использование МТ для анализа алгоритмов

Пример вопроса из шпаргалки

Предмет теории автоматов

Автомат – объект (идеальный, материальный или более конкретно – устройство), осуществляющий переработку информации.

Изучение способов преобразования информации является предметом теории автоматов в широком смысле.

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

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

С точки зрения абстрактной ТА автомат представляет собой совокупность множеств и отображений. Например, автомат может задаваться как шестерка объектов: А = , где:

• X – множество входных символов автомата
• Y – множество выходных символов автомата
• Q – множество состояний автомата
• q0 – начальные состояния автомата
• A – функция перехода: Q x X -> Q
• B – функция выхода: Q x X -> Y

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

Математический автомат рассматривается иногда как алгебра, при этом выделяется множество состояний автомата и операции над этим множеством.

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

Можно выделить следующие виды Теорий Автоматов:

• Абстрактные ТА (математические);
• Структурные ТА (технические);
• Общие ТА;
• Прикладные ТА;

ПТЦА - дискретный автомат – устройство, выполняющее преобразование цифровой информации по заданному алгоритму.

ТТ-автомат – устройство, выполняющее преобразование (распознавание) входных слов (текста).

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

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

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

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

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