Матричные методы оптимизации стохастических конечно-автоматных моделей тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи ИАСР Ясер Фахд

МАТРИЧНЫЕ МЕТОДЫ ОПТИМИЗАЦИИ СТОХАСТИЧЕСКИХ КОНЕЧНО-АВТОМАТНЫХ МОДЕЛЕЙ

Специальность: 01.01.09 - математическая кибернетика

АВТОРЕФЕРАТ диссертации па соискание ученой степени капдидата физико-математических наук

САНКТ-ПЕТЕРБУРГ 1992 г.

Работа выполнена на кафедре статистического моделирования математике-механического факультета Санкт-Петербургского государственного университета.

Научпый руководитель-капдидат физико-математических наук, доцент М.К.ЧИРКОВ

Официальные оппоненты: доктор физико-математических наук, профессор А.Х.ГЕЛИГ, кандидат физико-математических наук А.А.СОКОЛОВ

Ведущая организация-Сапет-Петербургский электротехнический институт им .В. И. У льянова( Ленина)

Защита состоится "ЯЛ 1992 г. в часов

на заседании специализированного совета К 063.57.49 по присуждению ученой степени кандидата физико-математических наук и Санкт- Петербургском государственном университете по адресу: 198904, г. Сапкт-Петербург, Старый Петергоф, Библиотечная площадь, дом 2, математико-механическнй факультет.

С диссертацией можно ознакомиться в библиотеке Санкт-Петербургского государственного университета по адресу: 199034, г.Санкт-Петербург, Университетская набережная, дом 7/9.

Автореферат разослан " С 9 "¿¡¿спЛ^^ 1992 г.

Ученый секретарь специализированного Совета К 063.57.49, капдидат физико-математических наук, доцент Л.И.ШЕПЕЛЯВЫЙ

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Азтеуалыгсеть темы. Интенсивное развитие различных аспектов теории математических моделей конечно-автоматного типа, продолжающееся уже несколько десятилетий и нашедшее отражение в целом ряде монографий (Айзерман М.А. и др., Бухараев Р.Г., Глушков В.М., Кудрявцев В.Б. и др., Трахтевброт Б.А. и Бардзиш, Я.М., Чирков М.К., Яблонский C.B., Gmzburg A., Kan-dell А. и Lee S.C., Paz A., Salomaa A., Starke Р.Н. и другие), обусловлено как чисто теоретическим интересом к решению новых математических задач дискретной математики, так и с тем, что конечные автоматы различного вида являются в ряде случаев весьма удобной математической моделью для описания определенного класса систем, устройств, процессов и явлений. Существенное место среди таких моделей занимают различные виды обобщенных и стохастических (вероятностных) автоматов, которые изучали Бухараез Р.Г., Варшавский В.И., Мучник A.A., Хунядвари Л., Чирков М.К., Шестаков A.A., Carlyle J.W., Chimel К., Gin^burg A., Kandel A., Lee S.C., Paz A., Salomaa A., Starke Р.Н., Topencharov V.V., Turakainen P., Wechler W., Dimitrov V. и многие другие. В том числе, понятие стохастического автомата широко используется в качестве математической модели целого ряда таких систем, устройств, процессов и явлений, которые содержат в себе элементы случайности (или, являясь по-существу детерминированными, подвергаются случайным воздействиям и т.п.) и допускают конечно-автоматную интерпретацию.

Одной из наиболее актуальных классических задач оптимизации математических моделей конечно-автоматного типа является проблема минимизации числа состояний автомата и построения его приведенных (или минимальных) форм. В том числе задача минимизации стохастического автомата рассматривалась в целом ряде работ (Бухараев Р.Г., Буй Мин Чи, Лазарев З.Г., Чен-цов Ö.M., Чирков М.К., Bacon G.C., Carlyle J.W., Even S., Paz A., Starke Р.Н. и др.) и были разработаны основы соответствующих методов, применимых именно к стохастическим автоматам, но часто содержащих довольно сложные для реализации на практике процедуры даже для систем с относительно небольшим чи-

слом состояний, входов и выходов. В то же время в последние годы для качественно более общего случая обобщенных автоматов над некоторыми алгебраическими структурами (в том числе, над произвольными полями) М.К.Чирковым и Л.А.Шестаковьш были обоснованы и разработаны аффективные матричные методы минимизации, которые, однако, напрямую неприменимы к стохастическим автоматам, так как могут нарушить корректность их задания. Позтому представляется весьма актуальным рассмотреть такую модификацию общего матричного метода, которая бы при применении к стохастическому автомату не нарушала бы его стохастичности.

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

Методика исследования базируется на использовании аппарата математической теории автоматов, линейной алгебры и теории матрип, выпуклого анализа.

Научная новизна работы состоит в дальнейшем развитии некоторых результатов теории стохастических автоматов и обобщенных автоматов над произвольными полями и доказательстве на этой основе ряда важных теоретических положений, позволивших теоретически обосновать и разработать новые, более эффективные методы оптимизации этих автоматов.

Практическая ценность работы заключается в создании на

основе ее теоретических результатов комплекса алгоритмов и программы для ПЭВМ IBM PC/AT, реализующих новый матричный метод построения минимальных форм стохастических автоматов, которые могут использоваться для практической оптимизации стохастических конечно-автоматных моделей.

Аппробадил работы. Основные результаты диссертации были опубликовали в работах [1,2,3], представлены на Третьем международном совещании но модельно-ориентированному анализу данных, докладывались и обсуждались на семинарах лаборатории математических проблем информатики НИИММ СПбГУ и кафедры статистического моделирования СПбГУ.

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения и приложения. Основной текст диссертации занимает 127страниц машинописного текста. Библиография содержит 53 наименования. Приложение содержит 32 страницы.

СОДЕРЖАНИЕ РАБОТЫ

Во введении показывается актуальность выбранной темы, дается краткий обзор литературы, посвященной этому вопросу, и приводится краткое содержание работы по главам с основными результатами.

В главе I работы приводятся основные определения и понятия, принятые в математической теории автоматов. Пусть X,A,Y есть соответственно алфавиты входов, состояний и выходов и |ЛГ| = п, |Л| = т, \Y\ = к. Конечным обобщенным автоматом А над полем Т называется система А — (X, A, Y,r,{R(x,y)},q)t где г - начальный вектор-строка, г G ; q - финальный вектор-столбец, q € •7гта,1) и {R(z,y)} - матрицы переходов, R(ac,y) € !Fm'm, х £ X, у € К. Автомат А индуцирует обобщенное отображение Фл : X" х У* —* определяемое выражением

где w = х\хг.~хи v = yi,v»>->l/<> G X, у; б У, и М>М ~ длина слов to,«.

А и томат А над нолем вещественных чисел будет стохастическим автоматом Арг =< X, А,У,р,{Р(л:,у)} >, если г* = р = = (рьР2,•••>Рт) - стохастический вектор-строка (начальных вероятностей состояний), q = е - вектор-столбец, все элементы которого единицы (в определении автомата Ар- обычно опускается); {К(г,у)} = {Р(х,у)} - совокупность матриц вероятностей переходов

р(х,у) = (Рф,у))т,т, Рц(х,у) - Рт{а}у](ьх),х е X, у € У.

В этом случае = Рг(и(ш).

Пусть

А =<Х,А,У,г,{Щх,у)},Ч>, Л =< X,А,У,г',{К(х,у)},я' >

есть обобщенные автоматы над Т. Автоматы А и А' называются инициально эквивалентными^ если для каждого г € Т1>т существует г' е такой, что для г, г' выполняется Фл(и>,и) = = Ф_д'(ш,и) при всех (ш, и) € X* х У*.

Любой автомат «Л', инициально эквивалентный автомату А и имеющий наименьшее число состояний среди всех автоматов инициально эквивалентных автомату А, н^ывается инициально приведенной формой автомата .4 (обозначим А — Яе<1.Д(я)). В теории стохастических автоматов условие равенства отображений должно выполняться только для стохастических г и г' и подобная приведенная форма обычно называется минимальной. Аналогичные определения существуют и для финальных векторов ч и ц.

В §2 изложены основы известной методики минимизации стохастических автоматов, а в §3 - основы общего матричного метода минимизации обобщенных автоматов. Все эти методы используют важное в теории автоматов понятие о ¿-базисных матрицах автомата, которое широко используется и в диссертации.

Правой базисной или С(ц)-6азисной матрицей автомата А называется матрица типа (т х ¿¡т£(.Др)), состоящая из системы линейно независимых векторов пространства С(Ац) , порожденного множеством векторов-столбцов

«

£(ЛЧ) = {!«,(», «)|Ь,(«/,») = ш 6 X*. о € У*, N = |«|}

¡»1

«

(для стохастических автоматов эту матрицу обычно' называют ¿-базисной).

Левой базисной или С(т)-6азиспой матрицей автомата А называется матрица Н(г.Л) типа (dim£(ivt)xrn), состоящая из системы линейно независимых ректоров-строк пространства С(гА), порожденного множеством векторов-строк

t

С(гА) = {Ьг(ш,о)|Ь,(ш,«) = гЦн(а,-,й), w G X*, v 6 Y\ \w\ = |»J>.

¿al

В §4 дана подробная формулировка основной задачи диссертации, состоящей в теоретическом обосновании и разработке новых, специальных, более аффективных матричных методов оптимизации стохастических автоматов и создании на их основе практических алгоритмов и программы построения минимальных форм таких автоматов, а также формулировка отдельных включающихся в нее этапов и проблем.

Глава II посвящена усовершенствованию матричного метода оптимизации обобщенных автоматов, ранее предложенного в работах М.КЧиркова и А.А.Шестахова.

В §1 этой главы вводится понятие о квазипсевдообратных матрицах и доказываются усиленные аналоги теорем оптимизации. Пусть H(«4q) есть правая базисная матрица размера (mx¿), d= dim£(^q), автомата Л. Квазипсевдообратной матрицей H'(Ai) к матрице H(.4q) назовем любую матрицу размера (d х то), удовлетворяющую условию: H'^qJH^q) = I(d). Улучшенный метод построения инициально приведенной формы автомата А, использующий вместо псевдообратных более широкий класс квазиасевдообратных матриц, обосновывается доказательством следующего утверждения.

Теорема 1.1(Гл.И). Пусть Д =< Х,А,У,гл, {R4(x,¡/)},q^ > есть обобщенный конечный автомат над полем F. H(.4q¿) есть любая его £(ед)-базисная матрица, а Н'(Лчд) - квазилсевдообрат-ная матрица к H(.Aqx). Тогда обобщенный конечный автомат В =< ЛГ, J3,У,гд, {R-fi(®,у)},Чв >, над полем F такой, что для

всех х £ X, у € У

тв = глН(Л<ц), Чв = Н'(Лсы){Ц,

имеет = тв = гапкН(Ля) состояний и является инициально приведенной формой автомата А, причем ее правая базисная матрица Н(0с[в) = I, а левая базисная матрица ЩгдВ) может быть образована системой линейно независимых строк матрицы Н(гЛЛ)Н(Лси) такой, что гапкН(гвЯ) = гапк(Н(гАИ)Н(Ляд)).

Аналогичное утверждение справедливо и для случая построения финально приведенной формы с помощью левой базисной матрицы Н(гЛ) и квазипсевдообратной к ней матрицы Н^гЛ).

В §2 исследуется вопрос о наиболее удобных формах представления ¿-базисных матриц с целью упрощения преобразований (1). Согласно ойределениго £(ч)-базисная матрица Н? автомата А имеет бесконечное множество форм представления Н^ = Н?а, где а - любая невырожденная квадратная матрица размера {Л х й), Л = (1лт£(с[), над Т. Выделяя в матрице Н, любые 6 линейно независимых строк Ь^, V — 1 ,<1, образуя матрицу а-1 = и находя обратную ей матрицу а, можно с по-

мощью преобразования Н? = Н,ог пайтн нормализованную форму представления £(ч)-базисной матрицы Н, такую, что ее строки с номерами ¿и, и = имеют пид = Ь(ь») = (0, ...,0,1,0, ...,0), где элемент " 1" стоит в у-ой нозпцип. В общем случае, в зависимости от выбора линейно независимых строк может быть построено несколько (не более, чем С*) различных нормализованных форм представления £(я)-базисной матрицы, а простейшую по форме квазинсевдообратную матрицу Н{ можно определить из соотношения = I тривиальный образом как матрицу размера (8 х т), у которой все столбцы с номерами < ф »„, V — пулевые, а столбцы с номерами

V = имеют вид Ьт(1/), V = 1Д Используя нормализованные формы представления ¿-базисных матриц обобщенного автомата А, можно таким образом существенно упростить процесс его минимизации в соответствии с методикой, рассмотренной в §1. В случае стохастического автомата Ар,, эта методика позволяет легко решить задачу построй-

ния в общем случае нестохастической (при d <т) минимальной формы автомата Afrt имеющей d состояний, т.е. такого обобщенного автомата А над полем вещественных чисел "Я, который находится в инициально приведенной форме и инициально эквивалентен (в смысле, определенном для обобщенных автоматов) автомату April §3 доказывается следующее утверждение, позволяющее при определенном свойстве левой базисной матрицы производить редукцию (уменьшение числа) состояний автомата АрТ, и приводится пример.

Теорема 3.1(Гл.Н). Пусть задан стохастический автомат Apr с m состояниями и Н? есть его левая базисная матрица . Тогда, если столбцы матрицы Нр = (hi,hj,...,hm) обладают свойством hj„ = a„h„ av > 0, v — l,d, то можно построить стохастический автомат А^, имеющий ra—d состояний и такой, что для каждого начального распределения вероятностей состояний р автомата Apr, обладающего свойством р,-„ = aypf, найдется эквивалентное ему начальное распределение вероятностей состояний в автомате Арг.

В главе 3 решается задача обоснования и разработки нового метода оптимизации, который сводит процесс минимизации стохастического автомата Арт к применению матричного преобразования вида

р' = рН, Р'(х,у) = Н'Р(®,у)Н, (2)

где Н - некоторая матрица, получаемая из ¿-базисной (т.е. правой базисной) матрицы Н. В §1 этой главы доказывается ряд свойств С-базисных матриц автомата AfT, обосновывающих следующий критерий его минимальности.

Теорема 1.2(Гя.Ш). Для того, чтобы стохастический автомат Ajt находился в минимальной форме, необходимо и достаточно чтобы не существовало такой нормализованной формы Н представления его ¿-базисной матрицы, в которой бы нашлась хот/ . бы одна строка с неотрицательными элементами, не входящая i выделенное при построении Н подмножество линейно независи мых строк.

На основании доказанных в §1 свойств ¿-базисной матрицы i

§2 предложен первый вариант метода - метод последовательной оптимизации, состоящий в следующем. Пусть Арт есть стохастический автомат и Н есть его С- базисная (m х d) матрица, где d < m. Выберем какую-либо систему d линейно независимых строк матрицы Н и построим ее нормализованную форму представления Н.

Пусть в матрице Н д строк имеют хотя бы по одному отрицательному элементу. Преобразуем матрицу Н к матрице Й размера (то х (d + д)) следующим образом. Каждая строка hj в матрице Н, имеющая хотя бы один отрицательный элемент, заменяется нулевой строкой, а затем в матрицу добавляется столбец, у которого i-ый элемент равен 1, а остальные 0, вставляемый между столбцами, которым соответствуют элементы "Iя в ближайших к h; сверху и снизу строках из выбранного подмножества линейно независимых строк. После этого i-я строка включается в выделенное подмножество линейно независимых строк. В результате такой последовательной замены строк и введения новых столбцов будет получена в нормализованной форме матрица Н с выделенным подмножеством d + д линейно независимых строк h,v = h(i/), v = l,d + g.

Для полученной матрицы Н строим простейшую квазипсевдо-обратную матрицу Н' как матрицу размера ((d+д) х т), у которой столбцы с номерами i ф \Vi v — \>d + д, нулевые, а столбцы с номерами »„, v — 1 ,d + g, имеют вид hr(f).

Применяя затем к автомату Afr матричное преобразование (2), получим автомат Л^ с удаленными всеми состояниями, которым в матрице Н соответствовали строки с неотрицательными элементами, не входящие в выбранную систему d линейно независимых строк. С- базисная матрица бГ построенного автомата «4^., находится из матрицы Н путем вычеркивания всех строк, соответствующих удаленным состояниям.

Ныбираем новую систему линейно независимых строк в матрице Н', повторяем изложенную процедуру уже для автомата А'рг и так далее, до тех пор, пока не будут выполнены условия теоремы 1.2 (Гл.Ш) и получен стохастический автомат Лрг, являющийся искомой минимальной формой автомата Арг.

В §3 предлагается второй, более совершенный вариант матричного метода - метод оптимизации с помощью единой преобразующей матрицы.

Теорема 3.1(Гл.Ш). Пусть Hi,H2,...,Hn есть последовательность преобразующих матриц, используемых на последовательных этапах построения стохастической минимальной формы стохастического автомата Арг с помощью матричного метода последовательной оптимизации. Тогда матрица

н=Пй*

находится в нормализованной форме и стохастическая минимальная форма Врт =< X, В, Y,f), {Р'(а;, у)} > автомата Арг определяется соотношениями (2).

В §2 и §3 также сформулированы алгоритмы, реализующие оба варианта метода, и даны примеры построения минимальных форм стохастического автомата.

Глава IV посвящена проблеме сравнительной оценки сложности представления стохастических автоматов стохастическими и нестохастическими минимальными формами.

В §1 обсуждаются особенности прямого применения к стохастическим автоматам общего матричного метода оптимизации обобщенных автоматов> приводящие к построению нестохастических минимальных форм и дается пример такого случая.

В §2 рассматриваются необходимые и достаточные условия того, что любая заданная вещественная (то х d) - матрица Н с линейно независимыми столбцами является ¿-базисной матрицей некоторого стохастического автомата. При этом дастся один из вариантов решения следующей задачи синтеза. Пусть задана такая матрица Н, удовлетворяющая требуемым условиям. Необходимо для заданных алфавитов X, |Х| = п, и У, |У| = к, построить какой-нибудь стохастический автомат Арг, имеющий m состояний и заданную ¿-базисную матрицу Н. Показано сле-' дующее утверждение.

Теорема 2.1(Гл.1У). Если Н = (hi,h2,...,hrf)

есть (т х d)- матрица, d<m, над полем вещественных чисел 1Z, столбцы которой

и

hy, j ~ l,d, липейпо независимы, и ¿, С С %т, есть векторное пространство, порожденное этими векторши-столбцами, то для существования стохастического конечного автомата Арт с входным алфавитом X, |Х| = n > 1, выходным алфавитом У, |У| > 2, m состояниями и ¿-базисной матрицей Н, необходимо и достаточно, чтобы е 6 С, где ет = (1,1,..., 1).

Основной результат §3 состоит в доказательстве следующего утверждения.

Теорема 3.1(Гл.1У). Для любого, сколь угодно большого целого ш, и любого целого d, 3 < d < m, существуют стохастические автоматы, стохастические минимальные формы которых имеют m состояний, а пестохастические минимальные формы -d состояний.

Приводится пример автомата Арг при d = 3, m = 5, удовлетворяющего условиям теоремы.

В главе 5 дается краткое описание комплекса алгоритмов, реализующих предлагаемые методы, и характеристика программы, основанной на этих алгоритмах, с помощью которой возможна практическая минимизация стохастических автоматов па ПЭВМ IBM PC/AT.

В заключении работы кратко перечислены основные ее результаты. Приложение содержит текст программы с подробными комментариями и результаты решения контрольного примера.

ЗАКЛЮЧЕНИЕ

Таким образом, можно кратко выделить следующие, полученные в рамках исследования основной главной задали данной работы, конкретные результаты:

1. Разработан усовершенствованный матричный метод оптимизации обобщенных автоматов над произвольными полями, основапный на использовании матриц, квазипсевдообратных к ¿ -базисным, и их нормализованных форм. На основе этого метода построен алгоритм нахождения нестохастических минимальных форм стохастических автоматов.

2. Исследовап ряд новых свойств ¿-базисных Матриц стохастического автомата, необходимых для обоснования новых ме-

тодов оптимизации. В том числе получены необходимые и достаточные условия, которым должны удовлетворять нормализованные формы ¿-базисной матрицы стохастического автомата, находящегося в минимальной форме, и необходимые и достаточные условия, которым должна удовлетворять ¿-базисная матрица любого стохастического автомата.

3. Разработаны два варианта нового матричного метода построения стохастической минимальной формы стохастического автомата: метод последовательной оптимизации и метод единой преобразующей матрицы.

4. Предложен один из вариантов метода синтеза стохастического автомата по заданной ¿-базисной матрице.

Б. Показано, что при определенных условиях стохастические минимальные формы стохастических автоматов могут иметь сколь угодно большое число состояний по сравнению с нестохастическими минимальными формами.

6. Разработан метод редукции одного класса состояний стохастического автомата при заданном начальном распределении вероятностей состояний.

7. Разработаны удобные для практической реализации алгоритмы оптимизации стохастического автомата и создана программа на языке Паскаль, реализующая эти алгоритмы па ПЭВМ IBM PC/AT.

Основные результаты диссертации опубликованы в работах:

а. НАСР Я., ЧИРКОВ М.К. Об относительной сложности приведенных форм стохастических автоматов // Вестник Ленинградского университета. Серия 1.1991. Вып.4, (N22). С.73-75.

2. НАСР Я., ЧИРКОВ М.К. О матричном методе оптимизации стохастических автоматов // Вестник С.-Петербургского университета, серия 1.1992. Вып.З,(Ш5). С.44-49.

3. NASRY..TCHIRKOV М.К, On optimization of stochastic finite automata // Third International Workshop on Model Oriented Data Ana. lysis (MODA-3),- St.Petersburg, 25-30 May 1992. P.24.