Резюме по теме. Вопросы для повторения

Вопросы для повторения

1.Недетерминированный конечный автомат это?

2.Отличие детерминированного конечного автомата от недетерминированного?

3.О чем говорится в теореме о детерминизации НКА?

4.Докажите теорему о детерминизации НКА?

Рассмотрен класс недетерминированный конечных автоматов. Приведено отличие от детерминированных автоматов. Для обработки недетерминированного конечного автомата приведен алгоритм перевода его к детерминированному виду.

Введение в дискретный анализ................................................................................................... 1

Глава 1. Введение в теорию множеств....................................................................................... 4

Тема 1.1. Множества и операции над ними........................................................................... 5

1.1.1. Основные понятия...................................................................................................... 5

1.1.2. Операции над множествами...................................................................................... 7

1.1.3. Векторы и прямые произведения.............................................................................. 9

Вопросы для повторения.................................................................................................... 10

Резюме по теме.................................................................................................................... 10

Тема 1.2. Отношения............................................................................................................... 11

1.2.1. Основные понятия и определения.......................................................................... 11

1.2.2. Бинарные отношения. Основные определения..................................................... 12

1.2.4. Эквивалентность и порядок..................................................................................... 14

Вопросы для повторения.................................................................................................... 15

Резюме по теме.................................................................................................................... 16

Тема 1.3. Соответствия и функции....................................................................................... 17

1.3.1. Соответствия и их свойства..................................................................................... 17

1.3.2. Взаимно однозначные соответствия и мощности множеств............................... 18

1.3.3. Функции и отображения.......................................................................................... 20

1.3.4. Операции................................................................................................................... 21

1.3.5. Гомоморфизмы и изоморфизмы.............................................................................. 23

Вопросы для повторения.................................................................................................... 26

Резюме по теме.................................................................................................................... 27

Глава 2. Математическая логика............................................................................................... 28

Тема 2.1. Логика высказываний............................................................................................ 28

2.1.1. Логические связки.................................................................................................... 29

2.1.2. Основные схемы логически правильных рассуждений....................................... 31

Вопросы для повторения.................................................................................................... 34

Резюме по теме.................................................................................................................... 34

Тема 2.2. Алгебра логики. Булева алгебра........................................................................... 36

2.2.1. Алгебра логики......................................................................................................... 36

2.2.2. Булева алгебра.......................................................................................................... 37

2.2.3. Эквивалентные преобразования............................................................................. 39

Вопросы для повторения.................................................................................................... 41

Резюме по теме.................................................................................................................... 41

Тема 2.3. Полнота и замкнутость........................................................................................... 42

2.3.1. Функционально полные системы.......................................................................... 42

2.3.2. Алгебра Жегалкина и линейные функции............................................................. 43

2.3.3. Замкнутые классы и монотонные функции.......................................................... 44

2.3.4. Теоремы о функциональной полноте.................................................................... 45

Вопросы для повторения.................................................................................................... 47

Резюме по теме.................................................................................................................... 47

Тема 2.4. Нечеткая логика...................................................................................................... 48

2.4.1. Основные понятия теории нечетких множеств.................................................... 50

2.4.2. Логические операции над нечеткими множествами............................................ 53

2.4.3. Свойства логических операций над нечеткими множествами............................ 56

Вопросы для повторения.................................................................................................... 57

Резюме по теме.................................................................................................................... 57

Тема 2.5. Нечеткие модели управления................................................................................ 59

2.5.1. Нечеткие операторы................................................................................................. 60

2.5.2. Нечеткая и лингвистическая переменные.............................................................. 61

2.5.3. Нечеткий логический вывод................................................................................... 62

Вопросы для повторения.................................................................................................... 65

Резюме по теме.................................................................................................................... 65

Тема 2.6. Логика предикатов................................................................................................. 66

2.6.1. Предикаты. Основные понятия............................................................................... 67

2.6.2. Кванторы................................................................................................................... 68

2.6.3. Выполнимость и истинность................................................................................... 69

2.6.4. Эквивалентные соотношения. Префиксная нормальная форма......................... 70

Вопросы для повторения.................................................................................................... 71

Резюме по теме.................................................................................................................... 72

Глава 3. Комбинаторика............................................................................................................. 73

Тема 3.1. Комбинаторные конфигурации............................................................................ 75

3.1.1. Принципы сложения и умножения......................................................................... 75

3.1.2. Перестановки............................................................................................................. 76

3.1.3. Размещения................................................................................................................ 77

3.1.4. Сочетания................................................................................................................... 78

Вопросы для повторения.................................................................................................... 80

Резюме по теме.................................................................................................................... 80

Тема 3.2. Разбиения. Включения и исключения.................................................................. 81

3.2.1. Разбиения................................................................................................................... 81

3.2.2. Полиномиальная формула........................................................................................ 83

3.2.3. Формула включений и исключений....................................................................... 83

Вопросы для повторения.................................................................................................... 84

Резюме по теме.................................................................................................................... 84

Глава 4. Теория графов............................................................................................................... 86

Тема 4.1. Основные понятия и операции на графах........................................................... 87

4.1.1. Основные понятия.................................................................................................... 88

4.1.2. Способы задания графов.......................................................................................... 90

4.1.3. Операции над частями графа. Графы и бинарные отношения............................ 91

Вопросы для повторения.................................................................................................... 93

Резюме по теме.................................................................................................................... 93

Тема 4.2. Маршруты и деревья............................................................................................... 94

4.2.1. Маршруты, пути, цепи, циклы................................................................................ 94

4.2.2. Дерево и лес............................................................................................................... 96

Вопросы для повторения.................................................................................................... 98

Резюме по теме.................................................................................................................... 98

Глава 5. Основы теории конечных автоматов....................................................................... 100

Тема 5.1. Переработка информации с помощью конечных автоматов........................... 100

5.1.1. Понятие абстрактного автомата............................................................................ 100

5.1.2. Способы задания автоматов................................................................................... 102

5.1.3. Взаимосвязь между моделями Мили и Мура....................................................... 106

Вопросы для повторения.................................................................................................. 109

Резюме по теме.................................................................................................................. 109

Тема 5.2. Детерминированные конечные автоматы.......................................................... 110

5.2.1.Основные понятия детерминированных конечных автоматов.......................... 110

5.2.2. Схема доказательства правильности конечного автомата................................. 113

5.2.3. Произведение автоматов........................................................................................ 114

Вопросы для повторения.................................................................................................. 114

Резюме по теме.................................................................................................................. 115

Тема 5.3. Недетерминированные конечные автоматы..................................................... 116

5.3.1. Основные понятия недетерминированных конечных автоматов..................... 116

5.3.2. Детерминизация НКА............................................................................................ 118

Вопросы для повторения.................................................................................................. 122

Резюме по теме.................................................................................................................. 122