- •Часть 2
- •Часть 2
- •Введение
- •1. Элементы комбинаторики
- •1.1. Простейшие комбинаторные конфигурации
- •Основные правила комбинаторики
- •Выборки элементов без повторений
- •Выборки элементов с повторениями
- •Латинские прямоугольники, конечные проективные плоскости и блок-схемы
- •1.2.1. Латинские прямоугольники
- •1.2.2. Конечные проективные плоскости
- •1.2.3. Блок-схемы
- •Формула включений и исключений
- •Объединение комбинаторных конфигураций
- •1.3.2. Принцип включения и исключения
- •1.3.3. Число булевых функций, существенно зависящих от всех своих переменных
- •1.3.4. Решето Эратосфена
- •Рекуррентные уравнения
- •1.4.1. Определение рекуррентного уравнения
- •1.4.2. Решение линейного однородного рекуррентного уравнения
- •1 (2) .4.3. Решение линейного неоднородного рекуррентного уравнения
- •1.5. Производящие функции
- •1.5.1. Общие сведения о производящих функциях
- •1.5.2. Производящая функция для биноминальных коэффициентов
- •1.5.3. Производящая функция для чисел Фибоначчи
- •1.6.1. Определение z – преобразования
- •1.6.2. Обратное z – преобразование
- •В правой части этого равенства стоит контурный интеграл в z-плоскости по любому замкнутому контуру в области сходимости, охватывающему начало координат.
- •1.6.3. Свойства z-преобразования
- •1.6.4. Использование z-преобразований для решения рекуррентных уравнений
- •1.6.5. Таблица односторонних z-преобразований
- •1.7. Трансверсали и перманенты
- •1.7.1. Множества и мультимножества
- •1.7.2. Трансверсали
- •1.7.3. Пермамент матрицы
- •1.7.4. Число трансверсалей
- •1.8. Матрицы Адамара
- •1.8.1. Определение матрицы Адамара и ее свойства
- •1.8.2. Эквивалентные преобразования матриц Адамара
- •1.8.3. Построение матриц Адамара
- •2. Основы теории конечных автоматов
- •2.1. Понятие конечного автомата
- •2.1.1. Общие сведения о конечных автоматах
- •2.1.2. Абстрактное определение конечного автомата
- •2.2. Эквивалентности в автоматах
- •2.2.1. Основные определения
- •2.2.2. Покрытия и морфизмы
- •2.2.3. Эквивалентные состояния автоматов
- •2.3. Процедура минимизации конечных автоматов
- •2.4. Автоматные функции и эксперименты с автоматами
- •2.4.1. Понятие ограниченно детерминированной функции
- •2.4.2. Моделирование автоматной функции с помощью схемы из функциональных элементов и задержки
- •2.4.3. Пример реализации конечного автомата с помощью сфэз
- •2.4.4. Эксперименты с автоматами
- •2.5. Автоматные языки
- •2.5.1. Представление о формальных языках
- •2.5.2. Алфавит, слово, язык
- •2.5.3. Классификация грамматик и языков
- •2.5.4. Понятие формальной грамматики
- •2.5.5. Автоматные грамматики
- •2.6. Модификации конечных автоматов
- •2.6.1. Частичные автоматы
- •2.6.2. Понятия недетерминированного и вероятностного автоматов
- •2.7. Процедура минимизации частичного автомата
- •2.7.1. Совместимые состояния
- •2.7.2. Техника определения совместимых состояний
- •2.7.3. Построение минимального автомата
- •3. Введение в нечеткую математику
- •3.1. Нечёткие множества
- •3.2. Нечеткие отношения
- •3.3. Нечеткая логика
- •Заключение
- •Библиографический список
- •Оглавление
- •2.7.3. Построение минимального автомата 98
- •Часть 2
- •394026 Воронеж, Московский просп., 14
- •Часть 2
2.6.2. Понятия недетерминированного и вероятностного автоматов
Недетерминированный автомат – это такой, который при данном входном символе и определенном состоянии может переходить в несколько различных внутренних состояний. Формально недетерминированный автомат это пятерка такая что, отображение - не является однозначным. Справедливо утверждение. Если недетерминированный автомат является конечным, то существует алгоритм, позволяющий построить конечный автомат, эквивалентный исходному недетерминированному автомату. При этом детерминированный автомат имеет больше состояний, чем исходный недетерминированный автомат.
Вероятностный автомат представляет собой набор , где - конечные множества. Функция определена на множестве и принимает в качестве своих значений вероятностные меры на множестве . Функция определена на и принимает в качестве своих значений вероятностные меры на множестве . Т.к. множества S и B конечны, то соответствующие вероятностные меры задаются векторами и где , ,
Для задания функции использовано множество стохастических матриц , размерности , где причем - вероятность перехода автомата из состояния в состояние под действием последовательности .
Аналогично, для задания функции использована система стохастических матриц размерности где , - вероятность появления на входе символа , если автомат находится в состоянии в и на его вход поступает /
2.7. Процедура минимизации частичного автомата
2.7.1. Совместимые состояния
Определение. Состояние называется совместимым по выходу с состоянием , если для всех . В этом случае пишется .Если состояния не совместимы по выходу, то пишут
Например для автомата
Таблица 20
Текущее состояние |
Следующее состояние |
Выход |
|||
0 |
1 |
0 |
1 |
||
|
|
|
0 |
1 |
|
|
|
|
- |
1 |
|
|
|
|
1 |
1 |
, т.е. отношение не транзитивно
Определение. Состояния и являются совместимыми, если для всех допустимых как для , так и для , имеем , в этом случае используется запись .Если и совместимы не для всех , то пишется . Если и совместимы для всех строк фиксированной длины k, то они называются k – совместимыми и обозначаются
Таким образом, если автомат, начав работу в состоянии или , для любой входной строки , дает одинаковые выходы в тех позициях, которые определены. Тогда состояния и совместимы и их можно склеить в одно состояние. Эта операция не изменит выходы в определенных позициях и даст безразличный выход в тех позициях, которые ранее давали безразличные выходы, хотя бы для одного из состояний. Таким образом, новый выход будет покрывать оба старых. Обозначается новое состояние через s. Тогда для всех , допустимых для , и для всех , допустимых для .
Отношение совместимости указывает возможность комбинирования состояний для их склеивания, но не указывает точного способа склеивания этих состояний.