пользователей: 21252
предметов: 10461
вопросов: 177855
Конспект-online
зарегистрируйся или войди через vk.com чтобы оставить конспект.
РЕГИСТРАЦИЯ ЭКСКУРСИЯ


Теория автоматов

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
хиты: 310
рейтинг:0
Точные науки
информатика
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2016. All Rights Reserved. помощь