|
|
Теория автоматов
|
1
|
Значение теории автоматов в дискретной математике. Области применения теории автоматов.
|
|
2
|
2. Определение абстрактного автомата. Понятие автомата как «черного ящика». Понятие состояния. Входной и выходной алфавит автомата. Функции переходов и выходов автомата. Начальное состояние автомата.
|
|
3
|
X, Y, S, δ, λ, s0
|
|
4
|
x1, ... , xn
|
|
5
|
y1, ... , yk
|
|
6
|
s1, ... , sm
|
|
7
|
Автоматы Мура и Мили. Детерминированные и детерминированные автоматы.
|
|
8
|
Синхронный и асинхронный автомат.
|
|
9
|
5. Табличный способ задания автоматов Мили и Мура.
|
|
10
|
6. Графовый способ задания автоматов Мили и Мура.
|
|
11
|
7. Автомат, проверяющий двоичную последовательность на четность.
|
|
12
|
0, 1
|
|
13
|
0,1
|
|
14
|
s0, s1
|
|
15
|
8. Автоматы, выполняющие задержку двоичного сигнала.
|
|
16
|
0, 1
|
|
17
|
0,1
|
|
18
|
s0, s1
|
|
19
|
9. Автомат, реализующий двоичный сумматор.
|
|
20
|
10. Понятие изолированного автомата. Циклы изолированного автомата. Проблема умножения произвольных чисел.
|
|
21
|
11. Основные принципы автоматного программирования. Достоинства и недостатки автоматного программирования.
|
|
22
|
12. Программная реализация автомата по графу переходов. Достоинства и недостатки.
|
|
23
|
13. Switch-технология программной реализации автомата. Достоинства и недостатки.
|
|
24
|
14. If-Table-Switch-технология программной реализации автомата. Достоинства и недостатки.
|
|
25
|
A = 0, B = 1, C = 2
|
|
26
|
Проблема выбора состояний автомата. Понятие расширенных функции переходов и выходов автомата.
|
|
27
|
X, S, Y, δ, λ
|
|
28
|
16. Эквивалентность и различимость состояний автомата.
|
|
29
|
17. K-эквивалентность и K-различимость стояний автомата, их свойства. K-эквивалентное разбиение автомата и его свойства.
|
|
30
|
18. Эквивалентное разбиение автомата. Метод таблиц построения эквивалентного разбиения автомата.
|
|
31
|
19. Минимальная форма автомата и способ ее построения.
|
|
32
|
X, Y, S,δ, λ, s0
|
|
33
|
20. Эквивалентность автоматов. Теорема Мура.
|
|
34
|
X, YA, SA,δA, λA, s0A
|
|
35
|
X, YB, SB,δB, λB, s0B
|
|
36
|
X, YA, SA,δA, λA, s0A
|
|
37
|
X, YB, SB,δB, λB, s0B
|
|
38
|
21. Эквивалентность классов автоматов Мура и Мили.
|
|
39
|
yi1,yi2….,yik
|
|
40
|
(s1/yi1)(s2/yyi2),…,(sk/yik)
|
|
41
|
22. Алфавит. Цепочки. Операции над цепочками. Понятие языка. Свойства языков. Примеры языков. Конструкторы и распознаватели языка.
|
|
42
|
x·y|xÎL1, yÎL2
|
|
43
|
λ
|
|
44
|
e
|
|
45
|
23. Определение порождающей грамматики. Терминальные и нетерминальные символы, правила, целевой (начальный) символ. Понятия вывода, выводимости, сентенциальной формы грамматики. Язык, порождаемый грамматикой.
|
|
46
|
24. Дерево вывода грамматики. Алгоритм построение дерева вывода.
|
|
47
|
25. Однозначность и эквивалентность грамматик.
|
|
48
|
26. Классификация грамматик по Хомскому.
|
|
49
|
27. Формулировка задачи разбора. Построение дерева разбора.
|
|
50
|
28. Автоматные языки и грамматики. Язык, принимаемый КА. Дерево разбора для автоматных грамматик.
|
|
51
|
29. Теорема Клини. Алгоритм построения ДКА для заданного НКА.
|
|
52
|
30. Способы создания программы - распознавателя с использованием КДА. Синтаксические диаграммы.
|
|
53
|
31. Определение регулярного множества и регулярного выражение. Эквивалентность регулярных выражений. Свойства регулярных выражений.
|
|
54
|
e
|
|
55
|
a
|
|
56
|
32. Построение синтаксической диаграммы по регулярному выражению.
|
|
57
|
33. Лемма о разрастании (накачке) регулярных языков.
|
|
58
|
34. Леммы о разрастании КС-языков.
|
|
59
|
35. Определение автомата с магазинной памятью (МП-автомата). Язык, допускаемый МП-автоматом. Расширенный МП-автомат.
|
|
60
|
e
|
|
61
|
36. Варианты реализации алгоритма работы недетерминированного МПА.
|
|
62
|
37. Метод рекурсивного спуска.
|
|
63
|
38. LL(k) и LL(1) грамматики и их свойства.
|
|
64
|
39. Детерминированные МП-автоматы.
|
|
65
|
40. Синтаксические диаграммы для КС - языков.
|
|
66
|
41. Правила построения распознавателя по синтаксической диаграмме.
|
|
67
|
множество состояний
|
|
68
|
множество входных символов
|
|
69
|
таблица переходов
|
|
70
|
множество конечных состояний
|
|
71
|
начальное состояние
|
|
72
|
задается текущее состояние
|
|
73
|
входной символ
|
|
74
|
читать (Ch);
Cond = tJump [Cond, Ch]
|
|
04.03.2016; 15:10
хиты: 14089
рейтинг:-1
|
|
Точные науки
информатика
|
|
