АВТОМАТОВ ДЕКОМПОЗИЦИЯ

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

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

Для уточнения постановки задачи введем понятие моделирования. Привлекая аналогии из алгебры, можно определить, что автомат А моделирует автомат В в том и только том случае, когда В изоморфен некоторому подавтомату автомата А (моделирование 1-го рода). Однако такое заимствованное из алгебры понятие, где главный интерес представляют элементы алгебры и отношения между ними, является слишком сильным и не отражает специфики автоматов теории. В теории автоматов интересуются гл. образом поведением «вход—выход» автомата. Эквивалентными считаются два автомата, имеющие одинаковое поведение (но, возможно, различное число состояний). Тогда естественно определить, что автомат А моделирует автомат В, если его поведение, с точностью до переименования входных и выходных букв, совпадает с поведением автомата В. Или точнее, автомат А моделирует автомат В в том и только том случае, когда В является гомоморфным образом некоторого подавтомата автомата А (моделирование 2-го рода).

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

Более всего изучено А. д. в параллельнопоследовательные соединения. Для объяснения некоторых полученных при этом результатов достаточно рассмотреть только Мура автоматы без выхода (аналогичные результаты имеют место и для Мили автоматов с выходом). Удобно рассматривать конечные автоматы как конечные унарные алгебры. Автомату соответствует алгебра где основное мн-во алгебры 91 — это мн-во состояний автомата Q и каждой букве входного алфавита X соответствует одна (унарная) ф-ция из сигнатуры так, что и наоборот: каждую такую конечную алгебру можно считать конечным автоматом. Каждая алгебра имеет две тривиальные конгруэнции: «О» (каждый класс этой конгруэнции содержит точно один элемент множества Q) и «1» (конгруэнция, имеющая единственный класс, состоящий из всего Q). Кроме этих двух тривиальных конгруэнций, алгебра 91 может иметь и др. конгруэнции. Если на мн-ве всех конгруэнций данной алгебры ввести естественное отношение порядка, то это мн-во станет конечной решеткой, причем указанные тривиальные конгруэнции будут соответственно нулем и единицей решетки. Если принять понятие моделирования 1-го рода и один автомат считать проще другого, когда он имеет меньшее число внутр. состояний, то можно сформулировать следующие теоремы: 1) автомат А можно представить в виде последовательного соединения двух меньших автоматов тогда и только тогда, когда алгебра имеет хотя бы одну нетривиальную конгруэнцию; 2) автомат А можно представить в виде параллельного соединения двух меньших автоматов тогда и только тогда, когда алгебра имеет две нетривиальные конгруэнции такие, что (умножение конгруэнций определяется указанным выше отношением порядка: если , то состоит из всех непустых пересечений вида Приведенные теоремы полностью решают для этого случая задачу декомпозиции. В самом деле, если то конгруэнция определяет некоторую конгруэнцию алгебры следовательно, можно также подвергнуть декомпозиции. Т. о., решетка конгруэнций несет осн. информацию о всех декомпозициях автомата А.

Во многом аналогичные результаты получают и при моделировании 2-го рода. Назовем квазиконгруэнцией алгебры такую систему подмножеств мн-ва что: 1) если то и 3) для каких-либо найдется такое s, что Очевидно, что каждая

конгруэнция является квазиконгруэнцией. Тривиальными квазиконгруэнциями назовем те же два отношения конгруэнтности 0 и 1, которые были определены выше. Верны следующие теоремы: 1) автомат А, имеющий состояний, можно представить в виде последовательного соединения двух меньших автоматов тогда и только тогда, когда существует нетривиальная квазиконгруэнция алгебры 21, имеющая меньше, чем подмножеств ) пусть — квазиконгруэнции алгебры , имеющие соответственно подмножеств, и Тогда автомат А можно представить в виде параллельного соединения двух автоматов, имеющих состояний. Здесь разработан аппарат т. н. алгебры пар, позволяющей описывать А. д.

Для формулировки дальнейших результатов требуется следующее определение: конечный автомат наз. перестановочным, если каждая буква его входного алфавита определяет некоторую перестановку мн-ва внутренних состояний. С каждым перестановочным автоматом связана группа перестановок, порожденная перестановками, соответствующими всем его входным буквам. Доказано следующую теорему: любой конечный автомат можно представить в виде параллельно-последовательного соединения автоматов, имеющих не более двух внутренних состояний, и перестановочных автоматов, группы перестановок которых делят группу перестановок исходного автомата. Более того, если группа перестановок исходного автомата имеет некоторый простой нормальный делитель, то в любом его разложении найдется автомат, группа перестановок которого имеет тот же простой нормальный делитель. Т. о., если простая группа «заложена» в исходном автомате Л, то она должна «содержаться» в одной из компонент, которые используются для представления А в виде композиции. Здесь понятие простоты можно связать с ф-цией переходов. Перестановочные автоматы считаются более простыми, чем не перестановочные, а из двух перестановочных А считается проще если группа перестановок А делит группу перестановок В. Наиболее простыми при таком подходе считаются автоматы, у которых группы перестановок — простые. Они дальше не разлагаются в параллельно-последовательные соединения.

Приведенные выше теоремы позволяют сформулировать следующий результат, относящийся также и к полноты проблеме в теории автоматов: любой конечный автомат можно представить в виде параллельно-последовательного соединения автоматов, имеющих не более двух внутр. состояний, и перестановочных автоматов, перестановки которых порождают простые группы. Если ф-ции алгебры логики или многозначных логик рассматривать как автоматы с одним состоянием, то определения простоты через число внутр. состояний или сложность ф-ции переходов, как это было сделано выше, для них теряют смысл. Здесь один автомат можно считать проще другого, если он имеет меньшее число входных каналов (т. е. одна ф-ция проще другой, если она является ф-цией от меньшего числа аргументов). Здесь также получены многочисленные результаты. См. Булевы функции.

Лит.: Krohn К., Rhodes J. Algebraic theory of machines. I. Prime decomposition theorem for finite semigroups and machines. «Transactions of the American mathematical society», 1965, v. 116; Hartma-nis J., Stearns R. E. Algebraic structure theory of sequential machines. Englewood Cliffs, 1966 [библиогр. с. 206-208]; Zeiger H. P. Cascade synthesis of finite-state machines. «Information and control», 1967, v. 10, Я» 4; Muller D. E. , P ut z о 1 u G. R. Frequency of decomposability among machines with a large number of states. «Journal computer and system sciences», 1968, v. 2, M 3. М. И. Кратко.