В настоящем издании предпринимается попытка восполнить пробел, существующий в обобщающей научной литературе по вероятностным автоматам. Книга написана на основе монографин автора «Вероятностные автоматы», изданной Казанским университетом в 1970 и 1977 гг. (второе издание). Как содержание упомянутых книг, так и методология изложения подверглись су-щественнъш изменениям, дополнениям и переработке в соответствии с поставленной задачей — подготовить руководство, систематизирующее современное состояние теории вероятностных автоматов на уровне важнейших результатов и методов. Создание такого руководства по теории вероятностных автоматов, опирающейся на разнообразный арсенал математических методов, оказалось трудной задачей, и автор не уверен в том, что решил ее вполне удовлетворительно. Все замечания по улучшению содержания книги будут приняты с благодарностью.
В подготовке настоящего издания автору оказали значительную помощь сотрудники кафедры теоретической кибернетики Казанского университета Ф. М. Лблаев, Ю. А. Алъпин, Н. 3. Габ-басов, Ф. И. Салимов, Иль. Р. Яасыров, Иск. Р/ Насыров и Н. Р. Нигматуллип. Всем им автор выражает искреннюю признательность. Автор выражает свою благодарность также Р. С. Степановой, при самоотверженном участии которой протекала кропотливая п трудоемкая работа по технической подготовке рукописи,
Р. Г. Бухарае&
ВВЕДЕНИЕ
Ячя ценности математической теории важны потенциальные возможности ее развития — как в соответствии с внутренней логикой самой теории, так и в направлении практических и теоретических приложений ее результатов. Вероятностный автомат представляет в этом смысле благодатный объект для изучения. Тип физической системы, которая может быть адекватно описана математической моделью вероятностного автомата, широко распространен. К этой категории относятся все дискретно описываемые системы, поведение которых индетерминировано, но описывается статистическими законами. Даже детерминированные конструкции из-за случайных сбоев компонент практически ведут себя как вероятностные системы. Можно привести примеры систем, вероятностных по существу,— скажем, биологическая популяция в развитии, система массового обслуживания, физический источник случайности и т. п. Посредством конструирования вероятностной модели мы в состоянии- учесть фактор неточности или неопределенности наших знаний о действительных состояниях физической системы, вызванный несовершенством процесса измерения или принципиальными причинами.
Из способов использования вероятностных моделей, получивших широкое распространение, остановимся подробнее на методе статистического моделирования. Идея метода состоит в использовании связи вероятностных характеристик различных случайных процессов с решениями некоторых математических задач. К известным примерам подобного рода относятся задачи вычисления определенного интеграла как математического ожидания пеко горой случайной величины, вычисления значения гармонической функции внутри области по се значениям на, границе области как среднего времени блуждания некоторой случайной точки до ее выхода на границу, моделирования поглощения частиц в толще вещества в ядерной физике, моделирования ситуаций массового-оослуживания и др. Наиболее эффективным способом реализации метода статистического моделирования является аппаратурное-моделирование заданного случайного процесса, что связано с необходимостью конструирования специализированных устройств — вероятностных процессоров. Конечный вероятностный автомат является математической моделью подобных устройств, и методы синтеза вероятностных автоматов имеют непосредственное приложение в конструировании вероятностных процессоров.
ОГЛАВЛЕНИЕ
Предисловие.........]....... 5
Введение ...........
Глава 1. Элементарная теория........... Ц
§ 1 Модель вероятностного автомата......... У
I 2 Инициальная эквивалентность вероятностных автоматов . . ^0
I 3 Свойства семейств стохастических матриц...... Ж
Упражнения и дополнительные теоремы........ At
Глава 2. Многотактные каналы и словарные функции .... 39
§ 1. Автоматные каналы............ 39
8 2 Конечно-автоматные каналы.......... 4Ь
§ 3. Свойства замкнутости классов рациональных и положительно-рациональных словарных функций........ 59
§ 4 Конечно-автоматная представимость словарных функций . . 70 § 5. Эквивалентность вероятностных автоматов. Приведение и минимизация............... 78
§ 6. Общая теория гомоморфизма и эквивалентности .... 89
УпразЕ""т:ия и дополнительные теоремы
Глава 3. Стохастические языки
106
§ 1. Определение представимости языков........ 106
§ 2. Алгебраические свойства класса стохастических языков . . ИЗ §• 3. Примеры непредставимых языков. Соотношения представимо-
стей................. 121
§ 4. Конечно-автоматная представимость языков..... 134
§ 5. Рациональные вероятностные автоматы....... 145
§ 6. Стохастические языки в однобуквенном алфавите. Однородные стохастические языки.......... 153
Упражнения и дополнительные теоремы........ 171
Глава 4. Некоторые специальные проблемы теория вероятностных
автоматов................. 173
§ 1. Проблема редукции............ 173
§ 2. Проблема идентификации. Продолжение минимального ранга 183
§ 3. Проблема устойчивости........... 195
§4. Представимость последовательностей пар случайных кодов 203
Упражнения и дополнительные теоремы........ 216
Глава 5. Структурная теория вероятностных автоматов .... 218
| J- Беспетельная декомпозиция.......... 218
| Г Декоип°зиция с расщеплением состояний...... 229
s о. Декомпозиция с выделением случайности. Задача синтеза им-
плицирующего вектора........... 240
Упражнения и дополнительные теоремы........" 254
Дополнение. Вероятностные и детерминированные вычисления 256
Список литературы.............. 265
Предметный указатель............." . 286
Цена: 150руб.
