Задачи синтеза и анализа перечислителей в некоторых классах конечных автоматов

• Автор: Посохина, Наталия Игоревна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2000
• Место защиты: Саратов
• Количество страниц: 98 с.

Содержание
Введение
ГЛАВА 1. Математические модели поведения дискретных систем
§ 1 Моделирование и восстановление поведения сложных систем: некоторые методологические аспекты
§ 2 Содержательная постановка задачи восстановления поведения сложной системы
§ 3 Математический аппарат, используемый при моделировании и восстановлении поведения
1.3.1. Основные определения
1.3.1.1. Элементы теории полугрупп
1.3.1.2. Элементы теории автоматов
1.3.1.3. Элементы теории чисел 31 § 4 Введение числовой модели конечного детерминированного автомата
1.4.1. Числовая модель
1.4.2. Исследование полугруппы преобразований
§ 5 Нахождение коэффициентов моделирующих функций
ГЛАВА 2. Оценка ранга матрицы Вандермонда, рассматриваемой над целочисленным кольцом
§ 1. Матрица Вандермонда в кольце вычислений по простому модулю
§ 2 Ранг матрицы Вандермонда в случае простейшего составного модуля и свойства некоторых целочисленных функций
ГЛАВА 3. Приложение числовой модели в области теории автоматов
§ 1 Построение числовой модели автомата по заданному автомату
§ 2 Моделирование поведения автомата на слове
§ 3 Построение автомата по его числовой модели
§ 4 Частично определенные, частично моделируемые автоматы и автоматы изоморфные моделируемым
Заключение
Список использованной литературы

Введение
В процессе эксплуатации сложных технических систем неизбежно возникают неисправности, они связаны с материальной природой систем и, следовательно, изменением во времени, поэтому устранить вероятность появления дефекта принципиально нельзя. Однако можно предусмотреть своевременную амортизацию неполадок, то есть быстрое и достоверное обнаружение неисправностей и устранение их последствий. Организация восстановления поведения (ВП) сложной системы включает как обеспечение восстанавливаемости поведения объекта на этапе его проектирования, а также самодиагностирование и самовосстановление объекта в процессе функционирования, так и применение спектра восстановительных процедур, основанных на том или ином виде резервирования. Традиционные методы структурного восстановления поведения сохраняют изначальную преобразовательную форму поведения за счет подключения исправного дубля-резерва. Невозможность или нецелесообразность их реализации инициирует применение функционального восстановления, которое опирается на принцип обучения Я.З.Цыпкина [48] и переход к перечислительной форме представления текущего поведения. Математические модели сложных систем позволяют оценить поведение системы с двух точек зрения: если закон функционирования задан как отображение множества последовательностей входных сигналов в множество последовательностей выходных сигналов, то есть представляет собой преобразование некоторого множества, то говорят, что реализуется модель поведения в преобразовательной форме. Если закон функционирования задан как перечисление всех последовательностей входных сигналов индуцирующих данный выходной сигнал, то говорят о реализации модели поведения в перечислительной форме. Автоматы, реализующие эти две

модели, называются автоматами-преобразователями и автоматами-перечислителями соответственно. В случае функционального ВП текущий закон функционирования выступает как "обучающаяся" система, которая после приложения специальных "обучающих" последовательностей должна генерировать сигналы, эквивалентные реакциям исправного поведения -"необученной" системы. В процессе "обучения" (функционального восстановления) происходит отход от точного соблюдения изначального преобразовательного соотношения между входными и выходными сигналами, хотя последние в точности совпадают с реакциями исправной технической системы. Анализ перехода от автоматов-преобразователей к автоматам-перечислителям и обратно позволяет выявить весь спектр функциональных особенностей поведения рассматриваемой системы. Вместе с тем, задача функционального ВП не сводится только к проблеме собственно восстановления поведения, в более общем ключе это задача приведения произвольного текущего поведения сложной системы (возможно, неисправного) к заданному виду. Формальная постановка задачи ВП была сделана A.A. Сытником и В.А. Твердохлебовым.
В общем случае (для произвольной сложной системы) задача ВП алгоритмически неразрешима, но она может быть решена при наложении на поведение системы (и, соответственно на математическую модель ее поведения) определенных ограничений. Однако, знание, что в данном конкретном случае задача ВП разрешима еще не дает ответа на вопрос, каким методом ВП следует воспользоваться. Поэтому несомненно важно установить связь между методами моделирования и восстановления поведения и условиями, накладываемыми на систему. Математические модели функционального восстановления поведения должны адекватно описывать в формальных терминах изменения в принципах обработки, синтеза и анализа вход-выходных соответствий. Целью исследования математической модели является получение информации о наличии или отсутствии предпосылок в

С, - подполугруппа состоящая ю всех классов вычетов, взаимно простых с т,
[а] - класс вычетов по модулю т, содержащий а,
Ре - подполугруппа Рт, состоящая из всех элементов, принадлежащих идемпотенту е, то есть (.у е Ре с £и) о (3п е М: $п = е).
Тогда:
1) Полугруппа Ят содержит в точности 2Г различных идемпотентов, из них г являются примитивными,
2) Всякий примитивный идемпотент полугруппы 8т имеет вид: е = [р1а'...р1-1а‘-'р1+1а’'1...рга'а},[а]еС1,
3) Полугруппа 5га является объединением своих подполугрупп Ре,
4) Если идемпотент имеет ВИД е - [д“'1 , то Ре содержит точно
Рн' /?; 1 в'1+1 ---Р,'а‘г) различных элементов,
5) Максимальная подгруппа Се с5ж, для которой е является единицей, имеет вид С,е и содержит точно (р(рк-1 Р,“‘г) различных элементов.