ПОНЯТИЕ О КОНЕЧНОМ АВТОМАТЕ. СИНТЕЗ КООМБИНАЦИОННЫХ АВТОМАТОВ

Сентябрь 3, 2022

Главная
Алгебра
ПОНЯТИЕ О КОНЕЧНОМ АВТОМАТЕ. СИНТЕЗ КООМБИНАЦИОННЫХ АВТОМАТОВ

Содержание

2. ТЕОРИЯ АВТОМАТОВ Автома́т (греч. αυτόματος — самодействующий, самодвижущийся) — устройство, выполняющее определённые функции без помощи человека.
3. ЧТО ТАКОЕ АВТОМАТ? АВТОМАТ – в средние века это механизм. Особенную известность приобрели в XVIII веке
4. Автоматоны Дро Пьер Жаке Дро (1721—1790), известный пионер часового искусства, родился в 1721 году в городе
5. Автоматоны Автоматоны Дро по праву считаются первыми компьютерами (?) в мире, настолько искусно они были выполнены.
6. Автоматоны Музыкант — это девушка, играющая на органе и состоящая из 2500 деталей. Музыка не поддельная,
7. Художник Художник — это автоматон, созданный в 1773 году и состоящий из 2000 деталей. Он может
8. Калиграф Калиграф — это самый сложный автоматон, завершенный в 1772 году и состоящий из 6000 деталей.
9. Автома́т-оружие Автома́т (от греч. αυτόματος — самодействующий, самодвижущийся — русское название применительно к оружию) — ручное
10. ТЕОРИЯ АВТОМАТОВ ТЕОРИЯ АВТОМАТОВ - раздел дискретной математики и математической кибернетики, изучающий математические модели преобразователей дискретной
11. Автоматизация Автоматизация — одно из направлений научно-технического прогресса, применение технических средств, методов и систем управления, освобождающих
12. Автоматизированные системы Требует дополнительного применения датчиков (сенсоров), устройств ввода, управляющих устройств (контроллеров), исполнительных устройств, устройств вывода,
13. Автоматизация Автоматизация, за исключением простейших случаев, требует комплексного, системного подхода к решению задачи, поэтому решения стоящих
14. АСУ и САУ Системы управления разделяют на два больших класса: Автоматизированные Системы Управления (АСУ) (с участием
15. АСУ
16. СИСТЕМЫ АВТОМАТИЗАЦИИ
17. Робот-гуманоид ASIMOРобот-гуманоид ASIMO, производство Honda Робот
18. Космические аппараты
19. Военная техника Ракеты
20. Военная техника Тополь-М
21. Военная техника
22. Данный прототип показывает лишь примерный облик того искусственного сердца, которое должно быть создано в следующие четыре
23. Учёные взялись за дело всерьёз, и затянувшаяся пьеса "В ожидании искусственного интеллекта" не означает, что он
24. Япония готовится принять на работу 3,5 миллиона роботов Роботы
25. 1.ПОНЯТИЕ О КОНЕЧНОМ АВТОМАТЕ. Конечным автоматом (просто автоматом) называется система (пятерка): S= , в которой Х={х1,х2,...,хi}
26. Функция переходов Функция переходов представляет собой отображение ϕ: или в другом виде: y(t+1)=ϕ[x(t),y(t)], где x(t), y(t),
27. Функция выходов Функция выходов представляет собой отображение ψ: Х×Y→Z или в другом виде: z(t)=ψ[x(t),y(t)], где x(t),
28. Автоматы Мили и Мура Функция выходов: z(t)=ψ[x(t),y(t)] – функция так называемого автомата Мили. В теории конечных
29. «Чёрный» ящик КДА
30. Таблицы переходов и выходов Поскольку функции ϕ и ψ определены на конечных множествах, их можно задавать
31. Техническая интерпретация автоматов Конечный автомат представляет собой хотя и абстрактную, но с функциональной точки зрения довольно
32. Техническая интерпретация автоматов Входной символ (буква) – это входной сигнал, точнее комбинация (набор) сигналов на всех
33. Техническая интерпретация автоматов Входное слово – последовательность входных векторов, поступающих в дискретные моменты времени (такты) t=1,2,3...
34. 2.Комбинационный автомат Автомат называется комбинационным, если для любого входного символа х и любых состояний yi, yj
35. Комбинационный автомат Такой автомат задается тройкой: S= , где X – множество входных символов, Z –
36. Комбинационный автомат Комбинационный автомат интерпретируется некоторой переключательной схемой или схемой из функциональных элементов:
37. 3.Задачи теории конечных автоматов Задачами теории конечных автоматов являются: 1) изучение возможностей автоматов в терминах множеств
38. Синтез автоматов При синтезе автоматов выделяют следующие этапы: 1) абстрактный синтез, или формализация условий работы, когда
39. Синтез автоматов 2) структурный синтез – производится минимизация переключательных функций, описывающих автомат, выполняется их представление в
40. Синтез автоматов 3) физический синтез – решаются вопросы построения принципиальной схемы (например, принципиальной электрической схемы), создания
41. Абстрактный синтез На этапе абстрактного синтеза осуществляется формализация условий работы, когда от некоторого высокоуровневого описания автомата
42. 4. Пример абстрактного синтеза КА Выполнить абстрактный синтез автомата по следующей словесной формулировке: «Автомат имеет входы
43. Пример абстрактного синтеза КА Из формулировки ясно, что автомат имеет четыре входа и один выход
44. Пример абстрактного синтеза КА Строим соответствующую таблицу истинности 1) при отсутствии или неодновременном поступлении сигналов на
45. Пример абстрактного синтеза КА Получаем символическую форму требуемой ПФ: f(abcd)=0,1,2,4,5,6,8,9,10,12,14 [3,7,11,13,15]. Абстрактный синтез завершён.
46. 5.Структурный синтез КА Минимизация
47. Получение схемы И,ИЛИ,НЕ
48. Моделирование в Electronics Workbench И,ИЛИ,НЕ
49. Верификация проекта: Используем логический конвертор:
50. Минимизация ПФ с помощью логического конвертора:
51. Генерация схемы И,ИЛИ,НЕ
53. Скачать презентацию

Слайд 2

ТЕОРИЯ АВТОМАТОВ
Автома́т
(греч. αυτόματος — самодействующий, самодвижущийся)
— устройство, выполняющее определённые

функции без помощи человека.

Слайд 3

ЧТО ТАКОЕ АВТОМАТ?
АВТОМАТ – в средние века это механизм.
Особенную известность приобрели

в XVIII веке автоматы Вокансона из Гренобля, которые он показывал в Париже в 1738 г. (человек, игравший на флейте, на свирели, утка, принимавшая пищу), а также произведения мастеров Дро, отца и сына из Лашо-де-Фон в 1790 г.

Слайд 4

Автоматоны Дро
Пьер Жаке Дро (1721—1790), известный пионер часового искусства, родился

в 1721 году в городе Ла Шо-де-Фон и положил начало одной из самых престижных торговых марок.

Слайд 5

Автоматоны
Автоматоны Дро по праву считаются первыми компьютерами (?) в мире,

настолько искусно они были выполнены. Где бы их ни показывали, они всегда производили сенсацию.
Сегодня автоматоны можно увидеть в музее Истории и Искусства в Нёвшателе (Швейцария).
Jaquet Droz (Жаке́ Дро) — марка швейцарских часов престижной категории

Слайд 6

Автоматоны
Музыкант — это девушка, играющая на органе и состоящая из 2500 деталей.

Музыка не поддельная, она не записана и не проигрывается музыкальной шкатулкой: кукла в самом деле касается пальцами клавиш инструмента, изготовленного по специальному заказу и состоящего из 24 труб. Кукла даже «дышит» (можно увидеть, как двигается грудь), её глаза следят за тем, куда двигаются пальцы, и совершает некоторые движения, как настоящий музыкант.

Слайд 7

Художник
Художник — это автоматон, созданный в 1773 году и состоящий из 2000

деталей. Он может рисовать три картинки: портрет Людовика XV и его собаку с надписью «Mon toutou» (мой пёсик), королевскую чету Марию Антуанетту и Людовика XVI, а так же сцену с Купидоном, управляющим колесницей, запряженной бабочками.
Механизм состоит из системы кулачков, которые управляют движением руки в двух измерениях, а так же отвечают за подъем карандаша. Помимо этого, автоматон ёрзает на стуле и периодически сдувает пыль с карандаша.

Слайд 8

Калиграф
Калиграф — это самый сложный автоматон, завершенный в 1772 году и

состоящий из 6000 деталей. Используя механизм, схожий с рисующим мальчиком, он может писать текст, состоящий из 40 букв. Текст закодирован на колесе и буквы выбираются последовательно друг за другом. Мальчик использует гусиное перо, которое он периодически макает в чернильницу, при этом встряхивает перо, чтобы предотвратить кляксы. Глаза автоматона двигаются вслед за текстом, и голова поворачивается к чернильнице, когда он макает в неё перо.

Слайд 9

Автома́т-оружие
Автома́т (от греч. αυτόματος — самодействующий, самодвижущийся — русское название применительно к оружию) —

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

Слайд 10

ТЕОРИЯ АВТОМАТОВ
ТЕОРИЯ АВТОМАТОВ - раздел дискретной математики и математической кибернетики, изучающий

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

Слайд 11

Автоматизация
Автоматизация — одно из направлений научно-технического прогресса, применение технических средств, методов

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

Слайд 12

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

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

Слайд 13

Автоматизация
Автоматизация, за исключением простейших случаев, требует комплексного, системного подхода к решению

задачи, поэтому решения стоящих перед автоматизацией задач обычно называются системами, например:
система автоматического управления (САУ);
система автоматизации проектных работ (САПР);
автоматизированная система управления технологическим процессом (АСУ ТП).

Слайд 14

АСУ и САУ
Системы управления разделяют на два больших класса:
Автоматизированные Системы Управления

(АСУ) (с участием человека в контуре управления);
Системы Автоматического Управления (САУ) (без участия человека в контуре управления).

Слайд 15

АСУ

Слайд 16

СИСТЕМЫ АВТОМАТИЗАЦИИ

Слайд 17

Робот-гуманоид ASIMOРобот-гуманоид ASIMO, производство Honda
Робот

Слайд 18

Космические аппараты

Слайд 19

Военная техника
Ракеты

Слайд 20

Военная техника
Тополь-М

Слайд 21

Военная техника

Слайд 22

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

быть создано в следующие четыре года техасскими учёными

Слайд 23

Учёные взялись за дело всерьёз, и затянувшаяся пьеса "В ожидании искусственного

интеллекта" не означает, что он совсем не придёт.

роботы

Слайд 24

Япония готовится принять на работу 3,5 миллиона роботов
Роботы

Слайд 25

1.ПОНЯТИЕ О КОНЕЧНОМ АВТОМАТЕ.
Конечным автоматом (просто автоматом) называется система (пятерка):

S=,
в которой Х={х1,х2,...,хi} – конечное входное множество (входной алфавит); Y={y1,y2,...,yj} – конечное множество внутренних состояний автомата (алфавит состояний); Z={z1,z2,...,zk} – конечное выходное множество (выходной алфавит); ϕ – функция переходов (из состояния в другие состояния); ψ – функция выходов.

Слайд 26

Функция переходов
Функция переходов представляет собой отображение ϕ: или в другом виде:
y(t+1)=ϕ[x(t),y(t)],
где

x(t), y(t), y(t+1) – конкретные символы алфавитов Х и Y соответственно в моменты автоматного времени t, t+1 (в тактах t и t+1); y(t) – называется текущим внутренним состоянием при соответствующем х(t), а y(t+1) – последующим внутренним состоянием.
Иначе говоря, функция переходов определяет последующее состояние автомата по заданному текущему и входному символу.

Слайд 27

Функция выходов
Функция выходов представляет собой отображение ψ: Х×Y→Z или в другом

виде:
z(t)=ψ[x(t),y(t)],
где x(t), y(t), z(t) – конкретные символы алфавитов X,Y,Z соответственно. Мы не будем особо выделять последующие значения x(t+1) и z(t+1), поэтому зависимость от t будем указывать только для внутреннего состояния, чтобы отделять y(t) от y(t+1).

Слайд 28

Автоматы Мили и Мура
Функция выходов: z(t)=ψ[x(t),y(t)] – функция так называемого автомата

Мили.
В теории конечных автоматов рассматривается также автомат Мура, у которого функция выходов проще – ψ: или z(t)=ψ[y(t)].

Слайд 29

«Чёрный» ящик
КДА

Слайд 30

Таблицы переходов и выходов
Поскольку функции ϕ и ψ определены на конечных

множествах, их можно задавать таблицами. Обычно две таблицы сводят в одну таблицу ϕ×ψ: и называют таблицей переходов-выходов или просто таблицей переходов (автоматной таблицей).

Слайд 31

Техническая интерпретация автоматов
Конечный автомат представляет собой хотя и абстрактную, но с

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

Слайд 32

Техническая интерпретация автоматов
Входной символ (буква) – это входной сигнал, точнее комбинация

(набор) сигналов на всех входах x1,x2,...,xn (это не буквы алфавита Х) устройства. Эта комбинация сигналов на дискретных входах еще называется входным вектором (набором) . Выходной сигнал (буква) – комбинация (набор) сигналов на дискретных выходах z1,z2,...,zm (это не буквы алфавита Z) – выходной вектор (набор) .

Слайд 33

Техническая интерпретация автоматов
Входное слово – последовательность входных векторов, поступающих в дискретные

моменты времени (такты) t=1,2,3...
Состоянию автомата соответствует вектор – текущее, – последующее. Этот вектор задает комбинация (набор) состояний y1,y2,...,ys (это не буквы алфавита Y) элементов памяти автомата.
Выходное слово – последовательность выходных векторов в дискретные моменты времени.

Слайд 34

2.Комбинационный автомат
Автомат называется комбинационным, если для любого входного символа х

и любых состояний yi, yj значения функций ϕ переходов одинаковы: ϕ(х,yi)=ϕ(х,yj)=z, где z – выходной символ. Иначе говоря, выходной символ z не зависит от состояния и определяется текущим входным символом. Говорят, что у такого частного класса автомата все состояния эквивалентны и, следовательно, комбинационный автомат имеет одно состояние.

Слайд 35

Комбинационный автомат
Такой автомат задается тройкой:
S=,
где X – множество входных символов, Z

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

Слайд 36

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

элементов:

Слайд 37

3.Задачи теории конечных автоматов
Задачами теории конечных автоматов являются:
1) изучение возможностей автоматов

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

Слайд 38

Синтез автоматов
При синтезе автоматов выделяют следующие этапы:
1) абстрактный синтез, или формализация

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

Слайд 39

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

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

Слайд 40

Синтез автоматов
3) физический синтез – решаются вопросы построения принципиальной схемы (например,

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

Слайд 41

Абстрактный синтез
На этапе абстрактного синтеза осуществляется формализация условий работы, когда от

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

Слайд 42

4. Пример абстрактного синтеза КА
Выполнить абстрактный синтез автомата по следующей словесной

формулировке:
«Автомат имеет входы abcd и выход z, который активируется (включается):
1) при отсутствии или неодновременном поступлении сигналов на каналы a и b – тогда, когда отсутствуют или поступают не одновременно сигналы на каналы c и d;
2) при одновременном поступлении сигналов на каналы a и b – тогда, когда не поступает сигнал на канал d.
В остальных случаях выход z не активируется (не включается)».

Слайд 43

Пример абстрактного синтеза КА
Из формулировки ясно, что автомат имеет четыре входа

и один выход

Слайд 44

Пример абстрактного синтеза КА
Строим соответствующую таблицу истинности
1) при отсутствии или

неодновременном поступлении сигналов на каналы a и b – тогда, когда отсутствуют или поступают не одновременно сигналы на каналы c и d;
2) при одновременном поступлении сигналов на каналы a и b – тогда, когда не поступает сигнал на канал d.

Слайд 45

Пример абстрактного синтеза КА
Получаем символическую форму требуемой ПФ:
f(abcd)=0,1,2,4,5,6,8,9,10,12,14 [3,7,11,13,15].
Абстрактный синтез

завершён.

Слайд 46

5.Структурный синтез КА
Минимизация

Слайд 47

Получение схемы
И,ИЛИ,НЕ

Слайд 48

Моделирование в Electronics Workbench
И,ИЛИ,НЕ

Слайд 49

Верификация проекта:
Используем логический конвертор:

Слайд 50

Минимизация ПФ с помощью логического конвертора:

Слайд 51

ПОНЯТИЕ О КОНЕЧНОМ АВТОМАТЕ. СИНТЕЗ КООМБИНАЦИОННЫХ АВТОМАТОВ

Содержание

ТЕОРИЯ АВТОМАТОВАвтома́т (греч. αυτόματος — самодействующий, самодвижущийся) — устройство, выполняющее определённые

ЧТО ТАКОЕ АВТОМАТ?АВТОМАТ – в средние века это механизм.Особенную известность приобрели

Автоматоны Дро Пьер Жаке Дро (1721—1790), известный пионер часового искусства, родился

Автоматоны Автоматоны Дро по праву считаются первыми компьютерами (?) в мире,

АвтоматоныМузыкант — это девушка, играющая на органе и состоящая из 2500 деталей.

ХудожникХудожник — это автоматон, созданный в 1773 году и состоящий из 2000

КалиграфКалиграф — это самый сложный автоматон, завершенный в 1772 году и

Автома́т-оружиеАвтома́т (от греч. αυτόματος — самодействующий, самодвижущийся — русское название применительно к оружию) —

ТЕОРИЯ АВТОМАТОВТЕОРИЯ АВТОМАТОВ - раздел дискретной математики и математической кибернетики, изучающий

Автоматизация Автоматизация — одно из направлений научно-технического прогресса, применение технических средств, методов

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

АвтоматизацияАвтоматизация, за исключением простейших случаев, требует комплексного, системного подхода к решению

АСУ и САУСистемы управления разделяют на два больших класса:Автоматизированные Системы Управления

АСУ

СИСТЕМЫ АВТОМАТИЗАЦИИ

Робот-гуманоид ASIMOРобот-гуманоид ASIMO, производство HondaРобот

Космические аппараты

Военная техникаРакеты

Военная техникаТополь-М

Военная техника

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

Учёные взялись за дело всерьёз, и затянувшаяся пьеса "В ожидании искусственного

Япония готовится принять на работу 3,5 миллиона роботов Роботы

1.ПОНЯТИЕ О КОНЕЧНОМ АВТОМАТЕ. Конечным автоматом (просто автоматом) называется система (пятерка):

Функция переходовФункция переходов представляет собой отображение ϕ: или в другом виде:y(t+1)=ϕ[x(t),y(t)],где

Функция выходовФункция выходов представляет собой отображение ψ: Х×Y→Z или в другом

Автоматы Мили и МураФункция выходов: z(t)=ψ[x(t),y(t)] – функция так называемого автомата

«Чёрный» ящикКДА

Таблицы переходов и выходовПоскольку функции ϕ и ψ определены на конечных

Техническая интерпретация автоматовКонечный автомат представляет собой хотя и абстрактную, но с

Техническая интерпретация автоматовВходной символ (буква) – это входной сигнал, точнее комбинация

Техническая интерпретация автоматовВходное слово – последовательность входных векторов, поступающих в дискретные

2.Комбинационный автомат Автомат называется комбинационным, если для любого входного символа х

Комбинационный автоматТакой автомат задается тройкой:S=,где X – множество входных символов, Z

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

3.Задачи теории конечных автоматовЗадачами теории конечных автоматов являются:1) изучение возможностей автоматов

Синтез автоматовПри синтезе автоматов выделяют следующие этапы:1) абстрактный синтез, или формализация

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

Синтез автоматов3) физический синтез – решаются вопросы построения принципиальной схемы (например,

Абстрактный синтезНа этапе абстрактного синтеза осуществляется формализация условий работы, когда от

4. Пример абстрактного синтеза КАВыполнить абстрактный синтез автомата по следующей словесной

Пример абстрактного синтеза КАИз формулировки ясно, что автомат имеет четыре входа

Пример абстрактного синтеза КАСтроим соответствующую таблицу истинности 1) при отсутствии или

Пример абстрактного синтеза КАПолучаем символическую форму требуемой ПФ: f(abcd)=0,1,2,4,5,6,8,9,10,12,14 [3,7,11,13,15].Абстрактный синтез

5.Структурный синтез КАМинимизация

Получение схемыИ,ИЛИ,НЕ

Моделирование в Electronics WorkbenchИ,ИЛИ,НЕ

Верификация проекта: Используем логический конвертор: