- •Н.А. Ююкин
- •Введение
- •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.4. Автоматные функции и эксперименты с автоматами
2.4.1. Понятие ограниченной детерминированной функции\
Пусть даны— входной алфавит и— выходной алфавит. Обозначимикак множества все возможных последовательностей в алфавитахAиBсоответственно.
Определение 1. Отображение→называетсядетерминированной функцией, еслиb(t)для любогоt=1,2,… однозначно определяется поa(1),a(2),…,a(t).
Функция такая, что
будет g-функцией, если, тои если,то.
Определение 2. Пусть заданаg-функция→. Рассмотрим произвольное входное слово.Определим функциюследующим образом: пустьa(1),a(2),…,a(t)— произвольная входная последовательность. Рассмотрим. Тогда положивпри этом называетсяостаточной функциейφ по слову.
Определение 3. Детерминированная функция→называетсяограниченно-детерминированной функцией, если у нее имеется лишь конечное число различных остаточных функций. Рассмотрим автомат (A,S,B,φ,,) гдеA,S,B— конечные алфавиты (входной, выходной и состояния),- переходная функция,- выходная,- начальное состояние.
Входом автомата служит последовательность a(1),a(2),…,a(t)ϵ(конечная или бесконечная), выходом автомата служит последовательность, при этом автомат задаетсясистемой канонических уравнений:
Определение 4. Отображение→называетсяавтоматной функцией, если существует автомат, который реализует это отображение. Справедливо утверждение. Справедливоутверждение: функция является автоматной тогда и только тогда, когда она ограниченно детерминированная.
Пример:Пусть, а система канонических уравнений выглядит следующим образом:
Такой автомат осуществляет отображение и называетсяединичной задержкой.
2.4.2. Моделирование автоматной функции с помощью схемы из функциональных элементов и задержки
Определение.Схемой из функциональных элементов и элементов задержки(СФЭЗ) называется схема, содержащая элементы некоторой функциональной системы, к функции которой добавлены элементы, реализующие функцию единичной задержки. В СФЭЗ допускаются ориентированные циклы, но любой ориентированный цикл должен проходить хотя бы через одну задержку.
Теорема 1. Схема из функциональных элементов и задержки осуществляет автоматное отображение.
Определение. Пусть автоматная функция отображает последовательность конечного базиса в последовательность конечного базиса. Пусть СФЭЗΣ осуществляет преобразование последовательностей булевых векторов длиныnв последовательность с булевыми векторами длиныm. Говорят, чтоΣмоделируетφ, если существуют отображения (кодирования)и, которые сопоставляют разным элементам алфавита разные векторы. Эти отображения обладают свойством: для любой последовательностив алфавите, если
, где.
Теорема 2. Для любой автоматной функции существует моделирующая ее СФЭЗ в функционально полной системе, состоящая из элементов дизъюнкции, конъюнкции, отрицания, а также элемента задержки.
2.4.3. Эксперименты с автоматами
Эксперимент с автоматами— это способ получений информации о внутренней структуре автоматов по их поведению. Основная задача экспериментов — получить сведения о строении автомата путем наблюдения его реакции на внешние воздействия.
Рассмотрим автоматы, в которых не выделены начальные состояния. В этом случае автомат задается пятеркой(A,S,B,φ,).обозначается множество всех конечных слов в алфавите. Пусть автомат (A,S,B,φ,)находится в состоянии и на вход подаются слова. Тогда на выходе будет некоторое словои после подачи всего слова автомат оказывается в состоянии. Раcширяя функциииψ, положим.
Определение 1.Два состоянияиавтомата (A,S,B,φ,)называются отличимыми, если существует входное словотакое, что. При этом словоназывается экспериментом, отличающим оти, а длину словаI() называют длиной эксперимента.
Теорема 3 (Мури). Если в автомате (A,S,B,φ,)состоянияиотличимы и |S|=r, то существует эксперимент, отличающийидлины.
Определение 2. Пусть два автоматаи, т.е. автоматы, имеющие одинаковые входной и выходные алфавиты. Пустьи. Говорят, что экспериментотличает состояния, если.
Теорема 4. Даны два автоматаипричем
и. Тогда, если состоянияиотличимы, то существует отличающий их эксперимент, длины которого.