Файл: Методические указания к решению задач по дисциплине Теория автоматов и алгоритмические языки.pdf

42
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
18. Алгоритм построения дерева анализа контактной схемы и вычисление еѐ пропускной способности.

43
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
7. Индивидуальные домашние задания
Задача 1
По номеру
№(x)= 1450 - 15 N

слова x (N – номер фамилии студента в журнале группы) в лексикографическом словаре позитивного языка над упорядоченным алфавитом
A = a, b, c, d, t, f определить это слово и проверить результат вычисления.
Задача 2
Найти СДНФ, СКНФ и полином Жегалкина булевой функции f от четырѐх переменных, заданной таблицей:
X
1
X
2
X
3
X
4
f
0 0
0 0
B
1
0 0
0 1
B
2
0 0
1 0
B
3
0 0
1 1
B
4
0 1
0 0
B
5
0 1
0 1
B
6
0 1
1 0
B
7
0 1
1 1
B
8
1 0
0 0
B
9
1 0
0 1
B
10
1 0
1 0
B
11
1 0
1 1
B
12
1 1
0 0
B
13
1 1
0 1
B
14
1 1
1 0
B
15
1 1
1 1
B
16
В таблице B
1
B
2
B
3
B
4
B
5
B
6
B
7
B
8
B
9
B
11
B
12
B
13
B
14
B
15
B
16
– двоичная запись натурального числа 2
15
+19N, где N – номер фамилии студента в журнале группы. Если возможно, сократить запись совершенной нормальной формы и сделать проверку, используя таблицу истинности.
Задача 3

44
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Синтезировать булеву функцию из предыдущей задачи 2 с помощью логической схемы из стандартных функциональных элементов (дублятора, дизъюнктора, конъюнктора и инвертора). Провести анализ результата и представить его в виде соответствующего орграфа.
Задача 4
Методом каскадов синтезировать контактную (переключательную) схему для булевой функции из задачи 2. Провести проверку результата, используя диаграмму дерева анализа, и представить его в виде соответствующего графа.
Задача 5
Для таблично заданного, инициального детерминированного автомата, с начальным состоянием 1 (см. Приложение, N – номер фамилии студента в журнале группы и номер его автомата), по входному слову AABCBBACCB найти соответствующее выходное слово и цепочку переходов состояний автомата при переработке этого входного слова (переходы по состояниям представить графически, отмечая дуги переходов по состояниям соответствующим входным символом).
Задача 6
Для таблично заданного автомата (см. Приложение, N – номер фамилии студента в журнале группы и номер его автомата), используя соответствующие булевы функции, написать канонические уравнения, его определяющие. Реализовать выход автомата в виде контактных схем из функциональных элементов, проиллюстрировав их графически и сделав их анализ с помощью дерева анализа.
Задача 7
Минимизировать по состояниям таблично заданный детерминированный автомат
(см. Приложение, N – номер фамилии студента в журнале группы и номер его автомата).
Результат проиллюстрировать графически, приведя диаграммы исходного и минимизированного автомата. Кроме того, выбрав входное слово, длины не менее 10, показать совпадение выходов исходного и минимизированного автомата, выбрав соответствующие начальные состояния.

45
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Приложение
1.
A
B
C
1 6
A
5
B
3
B
2 1
C
4
A
6
A
3 7
A
3
B
1
B
4 5
C
2
A
7
A
5 8
A
1
B
5
B
6 2
C
8
A
3
A
7 4
C
8
A
5
A
8 4
C
6
A
1
A
2.
A
B
C
1 3
B
6
C
1
A
2 8
C
7
B
2
A
3 5
B
8
C
3
A
4 8
C
1
B
5
A
5 3
B
8
C
4
A
6 8
C
7
B
3
A
7 5
B
2
C
1
A
8 8
A
6
B
3
C
3.
A
B
C
1 2
B
5
B
2
A
2 3
C
6
A
7
B
3 5
B
8
B
8
A
4 6
A
4
C
1
C
5 1
C
4
A
7
B
6 4
A
4
C
3
C
7 1
B
2
B
4
A
8 3
C
4
A
7
B
4.
A
B
C
1 8
C
2
B
4
B
2 5
A
1
C
8
A
3 4
B
8
A
3
A
4 7
B
1
A
5
A
5 3
B
1
A
4
A
6 7
A
8
C
1
A
7 5
B
8
A
7
A
8 1
C
6
B
3
B
5.
A
B
C
1 4
C
5
B
3
A
2 5
A
7
A
8
B
3 1
A
4
A
2
B
4 7
C
2
B
1
A
5 7
C
1
B
8
A
6 4
C
6
B
2
A
7 4
C
8
B
5
A
8 6
A
7
A
3
B
6.
A
B
C
1 3
A
4
C
7
B
2 3
A
5
C
6
B
3 1
B
2
A
5
C
4 6
A
1
C
7
B
5 3
A
5
C
8
B
6 5
B
2
A
1
C
7 4
B
6
A
2
C
8 1
B
3
A
2
C
7.

46
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
A
B
C
1 6
B
5
A
3
A
2 1
C
4
B
6
B
3 7
B
3
A
1
A
4 5
C
2
B
7
B
5 8
B
1
A
5
A
6 2
C
8
B
3
B
7 4
C
8
B
5
B
8 4
C
6
B
1
B
8.
A
B
C
1 3
C
6
B
1
A
2 8
B
7
C
2
A
3 5
C
8
B
3
A
4 8
B
1
C
5
A
5 3
C
8
B
4
A
6 8
B
7
C
3
A
7 5
C
2
B
1
A
8 8
A
6
C
3
B
9.
A
B
C
1 6
A
5
C
3
C
2 1
B
4
A
6
A
3 7
A
3
C
1
C
4 5
B
2
A
7
A
5 8
A
1
C
5
C
6 2
B
8
A
3
A
7 4
B
8
A
5
A
8 4
B
6
A
1
A
10.
A
B
C
1 3
B
6
A
1
C
2 8
A
7
B
3
C
3 5
B
8
A
2
C
4 8
A
1
B
5
C
5 3
B
8
A
4
C
6 8
A
7
B
3
C
7 5
B
2
A
1
C
8 8
C
6
B
3
A
11.
A
B
C
1 2
C
5
C
2
B
2 3
A
6
B
7
C
3 5
C
8
C
8
B
4 6
B
4
A
1
A
5 1
A
4
B
7
C
6 4
B
4
A
3
A
7 1
C
2
C
4
B
8 3
A
4
B
7
C
12.
A
B
C
1 8
B
2
A
4
A
2 5
C
1
B
8
C
3 4
A
8
C
3
C
4 7
A
1
C
5
C
5 3
A
1
C
4
C
6 7
C
8
B
1
C
7 5
A
8
C
7
C
8 1
B
6
A
3
A
13.
A
B
C
1 2
A
5
A
2
B

47
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
2 3
C
6
B
7
A
3 5
A
8
A
8
B
4 6
B
4
C
1
C
5 1
C
4
B
7
A
6 4
B
4
C
3
C
7 1
A
2
A
4
B
8 3
C
4
B
7
A
14.
A
B
C
1 8
A
2
B
4
B
2 5
C
1
A
8
C
3 4
B
8
C
3
C
4 7
B
1
C
5
C
5 3
B
1
C
4
C
6 7
C
8
A
1
C
7 5
B
8
C
7
C
8 1
A
6
B
3
B
15.
A
B
C
1 4
A
5
B
3
C
2 5
C
7
C
8
B
3 1
C
4
C
2
B
4 7
A
2
B
1
C
5 7
A
1
B
8
C
6 4
A
6
B
2
C
7 4
A
8
B
5
C
8 6
C
7
C
3
B
16.
A
B
C
1 3
B
4
C
7
A
2 3
B
5
C
6
A
3 1
A
2
B
5
C
4 6
B
1
C
7
A
5 3
B
5
C
8
A
6 5
A
2
B
1
C
7 4
A
6
B
2
C
8 1
A
3
B
2
C
Литература
1. Бояринцева Т.Е., Щетинин А.Н., Краснов И.К. Формальные языки и конечные автоматы: Учебное пособие/Под ред. Хомича. – М.: Изд. МГТУ им. Н.Э. Баумана, 2002.
– 35 сс.
2. Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов и вычислений, 2-е изд.: Пер. с англ. – М.: Издательский дом «Вильямс», 2008. –528 сс.
3. Белоусов А.И., Ткачев С.Б. Дискретная математика: Учеб. для вузов/под ред. В.С.
Зарубина, А.П. Крищенко. – М.: Изд-во МГТУ им. Н. Э. Баумана, 2006. – 744 сс. (Сер.
Математика в техническом университете, вып. XIX).
4. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике:
Учеб. Пособие. – М.:ФИЗМАТЛИТ, 2005. – 416 сс.

48
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев