Контрольная работа

Контрольная работа выдается после выполнения всех лабораторных работ.
Работа состоит из 4 вопросов.
Номер варианта определяется как увеличены на единицу остаток от деления увеличенных на 18 двух последних цифр индивидуального пароля на количество вариантов. Например, если последние две цифры составляют 15, а вариантов 40, то увеличив 15 на 18 получаем 32, остаток равен 32, увеличив его на 1 получаем номер варианта, т.е. 33. Если две последние цифры равны, например, 89, увеличиваем так же на 18 – получаем 107; остаток равен 27, а вариант -28.
Отчет по зачетной работе (Формулировка вопросов, ответы на вопросы) необходимо отправить на проверку через сайт.

Вариант 1

1. Опишите алгоритм построения графа перехода автомата Мили по его табличному представлению. Приведите пример.
2. Могут ли быть эквивалентными два конечных автомата, имеющие различное количество входных символов? Почему?
3. Что включает в себя понятие вероятностный конечный автомат?
4. При каких условиях могут возникать гонки?

Вариант 2

1. Опишите алгоритм построения табличного представления автомата Мили по его графическому представлению.
2. Могут ли быть эквивалентными два конечных автомата, имеющие различное количество финальных состояний? Почему?
3. Приведите пример вероятностного автомата в табличном виде.
4. В чем заключается идея противогоночного кодирования?

Вариант 3

1. Опишите алгоритм построения графа перехода автомата Мура по его табличному представлению. Приведите пример.
2. Опишите алгоритм удаления тупиковых состояний.
3. Опишите принцип работы вероятностного конечного автомата.
4. Что такое «смерть» автомата?

Вариант 4

1. Какие уравнения называются каноническими уравнения конечного автомата?
2. Опишите алгоритм удаления недостижимых состояний.
3. Чем вероятностный автомат отличается от обычного автомата?
4. Что является причиной гонок в автоматах?

Вариант 5

1. Чем отличается автомат Мили от автомата Мура при графическом представлении?
2. Опишите алгоритм удаления эквивалентных состояний.
3. В чем заключается проблема гонок в конечных автоматах?
4. В чем проявляется эффект гонок?

Вариант 6

1. Чем отличается работа автомата Мили от работы автомата Мура?
2. Что такое оптимальный автомат?
3. Приведите пример вероятностного автомата в виде графа.
4. При каких условиях могут возникать гонки?

Вариант 7

1. Опишите алгоритм построения табличного представления автомата Мура по его графическому представлению.
2. Что такое тупиковые состояния?
3. Опишите принцип работы машины Тьюринга.
4. Что такое «смерть» автомата?

Вариант 8

1. Что включает в себя понятие конечный автомат?
2. Могут ли быть эквивалентными два конечных автомата, имеющие различное количество выходных символов? Почему?
3. Приведите пример вероятностного автомата.
4. В каком случае автомата может «умереть»?

Вариант 9

1. Опишите принцип работы конечного автомата.
2. Что такое эквивалентность автоматов?
3. Каким образом реализуется работа вероятностного конечного автомата?
4. В чем заключается проблема гонок в конечных автоматах?

Вариант 10

1. Чем отличается система формул переходов от системы булевых функций?
2. Что такое история работы конечного автомата?
3. Из чего состоит математическое описание машины Тьюринга.
4. При каких условиях могут возникать гонки?

Вариант11

1. Укажите способы задания конечного автомата с кратким описанием.
2. Какие бывают виды недетерминированности?
3. Что такое конфигурация машины Тьюринга?
4. В каком случае автомата может «умереть»?

Вариант 12

1. Чем отличается система формул переходов от канонического представления автомата?
2. Что такое недетерминированность конечного автомата?
3. Что такое история работы машины Тьюринга?
4. В чем заключается проблема гонок в конечных автоматах?

Вариант 13

1. Чем отличается автомат Мили от автомата Мура при табличном представлении?
2. Могут ли быть эквивалентными два конечных автомата, имеющие различное количество финальных состояний? Почему?
3. Как составляются матрицы переходов вероятностного автомата?
4. В чем заключается идея противогоночного кодирования?

Вариант 14

1. Как связаны система формул переходов изакодированная в двоичном представлениитаблица переходов?
2. Могут ли быть эквивалентными два конечных автомата, имеющие различное количество рабочих состояний? Почему?
3. Кратко опишите способы задания машины Тьюринга.
4. При каких условиях могут возникать гонки?

Вариант 15

1. Как строится диаграмма Мили?
2. Могут ли быть эквивалентными два конечных автомата, имеющие различное количество входных символов? Почему?
3. Опишите принцип работы машины Тьюринга.
4. Что такое «смерть» автомата?

Вариант 16

1. Как связаны система булевых функций изакодированная в двоичном представлениитаблица переходов?
2. Какие бывают виды недетерминированности?
3. Как отмечаются дуги вероятностных автоматов?
4. В чем проявляется эффект гонок?

Вариант 17

1. Опишите алгоритм задания конечных автоматов булевыми функциями.
2. Могут ли быть эквивалентными два конечных автомата, имеющие различное количество рабочих состояний? Почему?
3. Поясните особенности вероятностных автоматов.
4. В каком случае автомата может «умереть»?

Вариант 18

1. Что такое каноническое представление автомата?
2. Могут ли быть эквивалентными два конечных автомата, имеющие различное количество выходных символов? Почему?
3. Как отмечаются дуги вероятностных автоматов?
4. Что является причиной гонок в автоматах?

Вариант 19

1. Покажите на примере программную реализацию автомата Мили.
2. Могут ли быть эквивалентными два конечных автомата, имеющие различное количество финальных состояний? Почему?
3. Функциональная схема машины Тьюринга.
4. При каких условиях могут возникать гонки?

Вариант 20

1. Опишите алгоритм задания конечных автоматов булевыми функциями.
2. Что такое недостижимые состояния?
3. Что такое тьюрингова команда?
4. Что является причиной гонок в автоматах?

Вариант 21

1. Чем отличается работа автомата Мили от работы автомата Мура?
2. Могут ли быть эквивалентными два конечных автомата, имеющие различное количество входных символов? Почему?
3. Что такое история работы машины Тьюринга?
4. В чем проявляется эффект гонок?

Вариант 22

1. Изложите алгоритм задания конечного автомата системой булевых функций.
2. Могут ли быть эквивалентными два конечных автомата, имеющие различное количество выходных символов? Почему?
3.Опишите принцип работы вероятностного конечного автомата.
4.При каких условиях могут возникать гонки?

Вариант 23

1. Покажите на примере программную реализацию автомата Мура.
2. Что такое недостижимые состояния?
3. Приведите пример вероятностного автомата в табличном виде.
4. В каком случае автомата может «умереть»?

Вариант 24

1. Что включает в себя понятие конечный автомат?
2. Дайте определение эквивалентных автоматов?
3. Функциональная схема машины Тьюринга.
4. В чем проявляется эффект гонок?

Вариант 25

1. Опишите алгоритм построения табличного представления автомата Мура по его графическому представлению.
2. Что такое тупиковые состояния?
3. Что такое история работы машины Тьюринга?
4. Что такое «смерть» автомата?

Вариант 26

1. Каким образом доопределяются недостающие пустые строки таблицы переходов?
2. Что такое оптимальный автомат?
3. Каким образом реализуется работа вероятностного конечного автомата?
4. В чем проявляется эффект гонок?

Вариант 27

1. Как связаны система формул переходов изакодированная в двоичном представлениитаблица переходов?
2. Опишите алгоритм удаления тупиковых состояний.
3. Приведите пример вероятностного автомата в табличном виде.
4. В чем заключается проблема гонок в конечных автоматах?

Вариант 28

1. Каким образом доопределяются недостающие пустые строки таблицы переходов?
2. Опишите алгоритм удаления недостижимых состояний.
3. Что такое история работы машины Тьюринга?
4. В каком случае автомата может «умереть»?

Вариант 29

1. Опишите алгоритм построения графа перехода автомата Мура по его табличному представлению. Приведите пример.
2. Опишите алгоритм удаления эквивалентных состояний.
3. Поясните особенности вероятностных автоматов.
4. Что такое «смерть» автомата?

Вариант 30

1. Опишите алгоритм построения графа перехода автомата Мили по его табличному представлению. Приведите пример.
2. Что такое тупиковые состояния?
3. Каким образом реализуется работа вероятностного конечного автомата?
4. Что является причиной гонок в автоматах?

Вариант 31

1. Опишите принцип работы конечного автомата.
2. Могут ли быть эквивалентными два конечных автомата, имеющие различное количество выходных символов? Почему?
3. Чем вероятностный автомат отличается от обычного автомата?
4. В чем проявляется эффект гонок?

Вариант 32

1. Как строится диаграмма Мили?
2. Опишите алгоритм удаления недостижимых состояний.
3. Функциональная схема машины Тьюринга
4. При каких условиях могут возникать гонки?

Вариант 33

1. Как строится диаграмма Мура?
2. Опишите алгоритм удаления эквивалентных состояний.
3. Из чего состоит математическое описание машины Тьюринга.
4. В чем заключается идея противогоночного кодирования?

Вариант 34

1. Как построить каноническое уравнение конечного автомата?
2. Опишите алгоритм удаления тупиковых состояний.
3. Что включает в себя понятие вероятностный конечный автомат?
4. Что такое «смерть» автомата?

Вариант 35

1. Какие уравнения называются каноническими уравнения конечного автомата?
2. Что такое оптимальный автомат?
3. Что такое история работы машины Тьюринга?
4. В чем проявляется эффект гонок?

Вариант 36

1. Как связаны система формул переходов изакодированная в двоичном представлениитаблица переходов?
2. Дайте определение эквивалентных автоматов?
3. Из чего состоит математическое описание машины Тьюринга.
4. При каких условиях могут возникать гонки?

Вариант 37

1. Как связаны система булевых функций изакодированная в двоичном представлениитаблица переходов?
2. Что такое недетерминированность конечного автомата?
3. Приведите пример вероятностного автомата в виде графа.
4. В чем заключается проблема гонок в конечных автоматах?

Вариант 38

1. Как построить каноническое уравнение конечного автомата?
2. Что такое эквивалентность автоматов?
3. Опишите принцип работы машины Тьюринга.
4. В каком случае автомата может «умереть»?

Вариант 39

1. Как строится диаграмма Мура?
2. Какие бывают виды недетерминированности?
3. Каким образом реализуется работа вероятностного конечного автомата?
4. Что такое «смерть» автомата?

Вариант 40

1. Изложите алгоритм задания конечного автомата системой булевых функций.
2. Что такое история работы конечного автомата?
3. Как отмечаются дуги вероятностных автоматов?
4. В чем проявляется эффект гонок?
=============================================

Лабораторная работа 1.«Машина Тьюринга» Цель работы.На примере работы машины Тьюринга научится моделировать конечный автомат.
Порядок выполнения работы (Задание).1. Изучить теорию.
2. Составить графическое представление машины Тьюринга.
3. Составить табличное представление машины Тьюринга.
4. Составить логическое представление машины Тьюринга.
5. Составить схему алгоритма моделирования.
6. Написать программу.
7. Исследовать работоспособность модели при различных вариантах исходных данных, обеспечивающих проверку работы всех ветвей программы.
8. Провести анализ полученных результатов и сделать выводы по работоспособности модели.
9. Написать отчет о проделанной работе.
Правило выбора варианта задания.Вар Например, для номера 89 и количества вариантов 23, остаток будет 20, а вариант для выполнения 21.
Варианты заданий.
№ варианта Подстановка № варианта Подстановка № варианта Подстановка № варианта Подстановка
01 AAAA-AAAB 26 AAAB-BABB 51 AABB-ABBA 76 ABAB-AAAA
02 AAAA-AABA 27 AAAB-BBAA 52 AABB-ABBB 77 ABAB-AAAB
03 AAAA-AABB 28 AAAB-BBAB 53 AABB-BAAA 78 ABAB-AABA
04 AAAA-ABAA 29 AAAB-BBBA 54 AABB-BAAB 79 ABAB-AABB
05 AAAA-ABAB 30 AAAB-BBBB 55 AABB-BABA 80 ABAB-ABAA
06 AAAA-ABBA 31 AABA-AAAA 56 AABB-BABB 81 ABAB-ABBA
07 AAAA-ABBB 32 AABA-AAAB 57 AABB-BBAA 82 ABAB-ABBB
08 AAAA-BAAA 33 AABA-AABB 58 AABB-BBAB 83 ABAB-BAAA
09 AAAA-BAAB 34 AABA-ABAA 59 AABB-BBBA 84 ABAB-BAAB
10 AAAA-BABA 35 AABA-ABAB 60 AABB-BBBB 85 ABAB-BABA
11 AAAA-BABB 36 AABA-ABBA 61 ABAA-AAAA 86 ABAB-BABB
12 AAAA-BBAA 37 AABA-ABBB 62 ABAA-AAAB 87 ABAB-BBAA
13 AAAA-BBAB 38 AABA-BAAA 63 ABAA-AABA 88 ABAB-BBAB
14 AAAA-BBBA 39 AABA-BAAB 64 ABAA-AABB 89 ABAB-BBBA
15 AAAA-BBBB 40 AABA-BABA 65 ABAA-ABAB 90 ABAB-BBBB
16 AAAB-AAAA 41 AABA-BABB 66 ABAA-ABBA 91 ABBA-AAAA
17 AAAB-AABA 42 AABA-BBAA 67 ABAA-ABBB 92 ABBA-AAAB
18 AAAB-AABB 43 AABA-BBAB 68 ABAA-BAAA 93 ABBA-AABA
19 AAAB-ABAA 44 AABA-BBBA 69 ABAA-BAAB 94 ABBA-AABB
20 AAAB-ABAB 45 AABA-BBBB 70 ABAA-BABA 95 ABBA-ABAA
21 AAAB-ABBA 46 AABB-AAAA 71 ABAA-BABB 96 ABBA-ABAB
22 AAAB-ABBB 47 AABB-AAAB 72 ABAA-BBAA 97 ABBA-ABBB
23 AAAB-BAAA 48 AABB-AABA 73 ABAA-BBAB 98 ABBA-BAAA
24 AAAB-BAAB 49 AABB-ABAA 74 ABAA-BBBA 99 ABBA-BAAB
25 AAAB-BABA 50 AABB-ABAB 75 ABAA-BBBB 100 ABBA-BABA

Лабораторная работа 2. Работа с автоматами Мили и Мура. Часть 1. Цель работы.Изучить алгоритмы сокращения автоматов на примере автомата Мили.
Порядок выполнения работы.1. Построить диаграмму Мили.
2. Удалить недостижимые состояния.
3. Удалить непродуктивные состояния.
4. Удалить эквивалентные состояния.
5. Построить диаграмму Мили сокращенного автомата.
6. Написать программу работы исходного автомата Мили. В исходном автомате предусмотреть «аварийный» останов автомата в непродуктивных состояниях.
7. Построить программу имитации работы сокращенного автомата Мили.
8. Исследовать работоспособность модели при различных вариантах исходных данных, обеспечивающих проверку работы всех ветвей программы.
9. Провести анализ полученных результатов и сделать выводы по работоспособности модели.
10.Написать отчет о проделанной работе.

Правило выбора варианта.Номер варианта определяется как увеличенный на единицу остаток от деления последних двух цифр индивидуального номера (пароля) на количество вариантов. Например, для номера 89 и количества вариантов 23, остаток будет 20, а вариант для выполнения21.

Варианты заданий.Для всех вариантов начальным состоянием является состояние S0.
В.1 a b c
S0 S2/b S1/a
S1 S3/a S1/c
S2 S6/b S1/a
S3 S3/b
S4 S5/a S2/c S3/a
S5 S7/c S3/c
S6 S3/a S7/c
S7 конечное состояние
В.2 a b c
S0 S2/a S6/b
S1 S4/c S7/c
S2 S4/a S2/c
S3 S4/a S7/c
S4 S4/b
S5 S1/a S4/a S6/c
S6 S2/a S3/b
S7 конечное состояние
В.3 a b c
S0 S1/a S6/b
S1 S3/a S1/c
S2 S3/a S7/c
S3 S3/b
S4 S3/c S7/c
S5 S4/a S3/a S6/c
S6 S1/a S2/b
S7 конечное состояние

В.4 a b c
S0 S5/b S4/a
S1 S1/b
S2 конечное состояние
S3 S2/c S1/a
S4 S4/c S1/a
S5 S3/b S4/a
S6 S5/c S1/a S7/a
S7 S2/c S1/c
В.5 a b с
S0 S6/b S3/a
S1 конечное состояние
S2 S2/b
S3 S3/c S2/a
S4 S1/c S2/a
S5 S1/c S2/c
S6 S4/b S3/a
S7 S2/c S5/a S2/a
В.6 a b c
S0 S3/a S2/b S1/a
S1 S3/a S1/c
S2 S6/b S1/a
S3 S3/b
S4 S3/a S2/c S1/c
S5 S7/c
S6 S3/a S7/c S3/c
S7 конечное состояние

В.7 a b c
S0 S2/a S6/b
S1 S7/c
S2 S4/a S4/d S2/c
S3 S4/a S7/c
S4 S4/b
S5 S1/a S4/a S6/c
S6 S4/b S2/a S3/b
S7 конечное состояние
В.8 a b c
S0 S1/a S6/b
S1 S3/a S3/a S1/c
S2 S3/a S7/c
S3 S3/b
S4 S3/c S7/c
S5 S4/a S7/c
S6 S1/a S2/b
S7 конечное состояние
В.9 a b c
S0 S5/b S4/a
S1 S1/b S1/a
S2 конечное состояние
S3 S2/c S1/a
S4 S1/a S1/a
S5 S3/b S4/a
S6 S1/a S7/a
S7 S2/c S1/c

В.10 a b с
S0 S6/b S2/b S3/a
S1 конечное состояние
S2 S2/c S2/b
S3 S3/c S2/a
S4 S1/c S2/a
S5 S1/c S2/a S2/c
S6 S4/b S3/a
S7 S5/a
В.11 a b c
S0 S2/b S1/a
S1 S3/a S1/c S3/a
S2 S6/b S1/a
S3 S3/a S3/b
S4 S2/c S3/a
S5 S7/c
S6 S3/a S7/c
S7 конечное состояние
В.12 a b c
S0 S2/a S6/b
S1 S4/c S7/c
S2 S4/a S2/c
S3 S4/a S4/a S7/c
S4 S4/b
S5 S7/b S4/a S6/c
S6 S2/a S3/b
S7 конечное состояние

В.13 a b c
S0 S1/a S6/b
S1 S3/a S1/c
S2 S7/c
S3 S3/b
S4 S3/a S7/c
S5 S4/a S6/a S6/c
S6 S1/a S2/b
S7 конечное состояние
В.14 a b c
S0 S5/b S4/a
S1 S1/b
S2 конечное состояние
S3 S2/c S1/a
S4 S4/c S1/b S1/a
S5 S3/b S4/a
S6 S6/c S1/a S2/a
S7 S2/c S1/c
В.15 a b с
S0 S6/b S3/a
S1 конечное состояние
S2 S2/a S2/b
S3 S3/c S2/a
S4 S1/c
S5 S1/c S2/c
S6 S4/b S3/a
S7 S5/a

Лабораторная работа 3. Работа с автоматами Мили и Мура. Часть 2. Цель работы.Изучить алгоритмы построения автоматов Мили и Мура по ГСА.
Порядок выполнения работы.1. Минимизировать формулы в СФП, например, картами Карно.
2. По заданной СФП построить ГСА.
3. Преобразовать ГСА в автомат Мили.
4. Преобразовать ГСА в автомат Мура.
5. Удалить эквивалентные состояния.
6. Написать программы работы автомата Мили и автомата Мура.
7. Исследовать работоспособность модели при различных вариантах исходных данных, обеспечивающих проверку работы всех ветвей программы.
8. Провести анализ полученных результатов и сделать выводы по работоспособности модели.
9. Написать отчет о проделанной работе.

Правило выбора варианта. Номер варианта определяется как увеличенный на единицу остаток от деления последних двух цифр индивидуального номера на количество вариантов.
Варианты заданий.Во всех вариантах микрооперациями являются вывод на экран номера текущего состояния.
Вариант 1.{█(&Y1→a ̄b ̄Y1∨a ̄bY3∨ab ̄Y1∨abY2@&Y2→a ̄b ̄Y1∨a ̄bY3∨ab ̄Y1∨abY2@&Y3→a ̄b ̄Y2∨a ̄bY1∨ab ̄Y3∨abY1@&Y4→a ̄b ̄Y4∨a ̄bY4∨ab ̄Y1∨abY1)┤

Вариант 2.{█(&Y1→a ̄b ̄Y1∨a ̄bY1∨ab ̄Y1∨abY2@&Y2→a ̄b ̄Y2∨a ̄bY4∨ab ̄Y1∨abY2@&Y3→a ̄b ̄Y2∨a ̄bY2∨ab ̄Y3∨abY3@&Y4→a ̄b ̄Y4∨a ̄bY2∨ab ̄Y1∨abY1)┤
Вариант 3. {█(&Y1→a ̄b ̄Y1∨a ̄bY4∨ab ̄Y1∨abY2@&Y2→a ̄b ̄Y2∨a ̄bY3∨ab ̄Y3∨abY2@&Y3→a ̄b ̄Y2∨a ̄bY3∨ab ̄Y3∨abY1@&Y4→a ̄b ̄Y4∨a ̄bY4∨ab ̄Y1∨abY4)┤
Вариант 4. {█(&Y1→a ̄b ̄Y1∨a ̄bY4∨ab ̄Y1∨abY2@&Y2→a ̄b ̄Y1∨a ̄bY3∨ab ̄Y1∨abY3@&Y3→a ̄b ̄Y2∨a ̄bY3∨ab ̄Y3∨abY1@&Y4→a ̄b ̄Y2∨a ̄bY4∨ab ̄Y2∨abY2)┤
Вариант 5. {█(&Y1→a ̄b ̄Y1∨a ̄bY3∨ab ̄Y2∨abY2@&Y2→a ̄b ̄Y1∨a ̄bY3∨ab ̄Y1∨abY4@&Y3→a ̄b ̄Y1∨a ̄bY2∨ab ̄Y3∨abY3@&Y4→a ̄b ̄Y1∨a ̄bY4∨ab ̄Y3∨abY1)┤
Вариант 6. {█(&Y1→a ̄b ̄Y1∨a ̄bY3∨ab ̄Y1∨abY1@&Y2→a ̄b ̄Y1∨a ̄bY3∨ab ̄Y3∨abY2@&Y3→a ̄b ̄Y3∨a ̄bY1∨ab ̄Y3∨abY1@&Y4→a ̄b ̄Y1∨a ̄bY4∨ab ̄Y2∨abY1)┤
Вариант 7. {█(&Y1→a ̄b ̄Y2∨a ̄bY3∨ab ̄Y4∨abY2@&Y2→a ̄b ̄Y2∨a ̄bY3∨ab ̄Y1∨abY3@&Y3→a ̄b ̄Y3∨a ̄bY3∨ab ̄Y3∨abY2@&Y4→a ̄b ̄Y4∨a ̄bY4∨ab ̄Y4∨abY1)┤
Вариант 8. {█(&Y1→a ̄b ̄Y1∨a ̄bY3∨ab ̄Y1∨abY2@&Y2→a ̄b ̄Y3∨a ̄bY3∨ab ̄Y4∨abY4@&Y3→a ̄b ̄Y2∨a ̄bY2∨ab ̄Y3∨abY4@&Y4→a ̄b ̄Y4∨a ̄bY4∨ab ̄Y1∨abY3)┤
Вариант 9. {█(&Y1→a ̄b ̄Y3∨a ̄bY3∨ab ̄Y1∨abY2@&Y2→a ̄b ̄Y1∨a ̄bY2∨ab ̄Y1∨abY1@&Y3→a ̄b ̄Y3∨a ̄bY1∨ab ̄Y3∨abY1@&Y4→a ̄b ̄Y4∨a ̄bY4∨ab ̄Y4∨abY1)┤
Вариант 10. {█(&Y1→a ̄b ̄Y1∨a ̄bY2∨ab ̄Y1∨abY1@&Y2→a ̄b ̄Y1∨a ̄bY2∨ab ̄Y3∨abY2@&Y3→a ̄b ̄Y2∨a ̄bY2∨ab ̄Y3∨abY1@&Y4→a ̄b ̄Y4∨a ̄bY2∨ab ̄Y4∨abY1)┤