- •Н.А. Ююкин
- •Введение
- •1. Элементы комбинаторики
- •1.1. Простейшие комбинаторные конфигурации
- •Основные правила комбинаторики
- •Выборки элементов без повторений
- •Выборки элементов с повторениями
- •Латинские прямоугольники, конечные проективные плоскости и блок-схемы
- •1.2.1. Латинские прямоугольники
- •1.2.2. Конечные проективные плоскости
- •1.2.3. Блок-схемы
- •Формула включений и исключений
- •1.3.1. Объединение комбинаторных конфигураций
- •1.3.2. Принцип включения и исключения
- •1.3.3. Число булевых функций, существенно зависящих от всех своих переменных
- •1.3.4. Решето Эратосфена
- •1.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-плоскости по любому замкнутому контуру в области сходимости, охватывающему начало координат.
- •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.2. Моделирование автоматной функции с помощью схемы из функциональных элементов и задержки
- •2.4.3. Эксперименты с автоматами
- •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. Нечеткая логика
- •Заключение
- •Библиографический список
- •Оглавление
- •1. Элементы комбинаторики 7
- •2. Теория автоматов 58
- •3. Введение в нечеткую математику 106
2.2. Эквивалентности в автоматах
2.2.1. Основные определения
Пусть на вход конечного автомата подается последовательность символов из входного алфавита A. Эту последовательность обозначают, и называютстрокойиливектором.
На выходе конечного автомата печатается выходная строка
,
состоящая из символов алфавита .
Строка внутренних состояний .
Для некоторого автомата по любой входной строки длины, и по любому начальному состояниюоднозначно определяется строка длины внутренних состояний., которая получается применением отображения, т.е.
Аналогично, выходная строка определяется последовательным применением отображения, т.е.
Поэтому рассматривая конечный автомат, как устройство, перерабатывающее пары ив строкии,
Можно определить функции
Эти функции рекурсивно строятся по известным φиψ, задающихся в описании автоматаM.
Здесь Ar- множество всех строк длиныrиз алфавитаA, а
BrиSr- множества всех строк длиныr из алфавитовBиS соответственно
Пример. Рассмотрим автомат с двумя устойчивыми состояниями, изображенный на рисунке
Здесь заданы - входная строка и начальное состояние. Отсюда получим:
.
В реальных устройствах увеличение числа внутренних состояний автомата приводит к росту числа электронных схем и следовательно к уменьшению надёжности, к усложнению ремонта и т.д. Поэтому число необходимых состояний автомата стремятся уменьшить, не ограничивая его возможностей. В связи с этим важна следующая задача.
Пусть фиксированы входной и выходной алфавиты. Можно ли заменить автоматавтоматом с меньшим числом состояний, но с той же функцией, переводящей входы в выходы.
Определение. Автоматпокрываетавтомат, если входной и выходной алфавиты у этих автоматов общие и существует функция, такая что для любого положительного числаr
Указанный факт записывается в виде .
Автомат, который нельзя покрыть меньшим автоматом называется минимальным. Можно проверить, что отношение покрытия является рефлексивным и транзитивным.
Автоматы иназываютсяэквивалентными, еслипокрываети одновременно с этимпокрывает. В этом случае пишут.
Эквивалентность автоматов означает, что существуют функции fиgтакие, что
со свойством
со свойством.
СледствиеОтношение эквивалентности автоматов симметрично, транзитивно, рефлексивно.
2.2.2. Покрытия и морфизмы
Отношения покрытия и эквивалентности тесно связаны с понятием морфизма.
Пусть имеются автоматы ис общими входными и выходными алфавитами.
Морфизмомназывают отображение, такое, чтои
Если θ сюрьективно, то морфизм называетсяэпиморфизмом. Еслиθ биективно, то морфизм называетсяизоморфизмом(автоматом).
Пусть отображение θ- эпиморфизм автоматана. Тогда для любой входной строкии начального состояниявыходная строкаавтоматасовпадает с выходной строкой, если начальное состояниеудовлетворяет условию.
Таким образом, любой эпиморфизм автоматов определяет покрытие автоматаавтоматом.
Определение.Автоматыи, имеющие общие алфавитыиизоморфны, если: 1) у них одинаковое число внутренних состояний и 2)существует биекциятакая, что любая входная строка перерабатывается в одну и ту же выходную строку автоматамиис начальными состояниямии .соответственно.
Например, автоматы, представленные на рисунке
изоморфны, так как имеет место биекция и .