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

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. Кванторы 69

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Резюме по теме 92

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

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

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

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

Резюме по теме 97

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

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

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

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

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

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

Резюме по теме 108

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

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

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

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

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

Резюме по теме 114

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

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

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

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

Резюме по теме 121

10