On skeleton automata.pdf Под автоматом понимается тройка A = (S, X, 8), где S и X - конечные непустыемножества (состояний и входных сигналов соответственно); 8 : S х X ^ S - отобра-жение, называемое функцией переходов. Функция переходов продолжается на множе-ство S х X*, где X* - совокупность всех конечных слов над алфавитом X: по опре-делению, .(s,e) = s для любого s Е S и пустого слова e и .(s,px) = .(.(s,p),x) длялюбых s Е S, x Е X, p Е X*.Автомату A сопоставляется диаграмма переходов - мультиграф G(A), вершина-ми которого являются элементы множества S и дуги помечены элементами из X: извершины s в вершину s' ведет дуга с меткой x, если .(s,x) = s'.Говорят, что состояние s' достижимо в автомате A из состояния s, если существу-ет входное слово p Е X*, такое, что .(s,p) = s'. В этом случае пишут (s,s') Е т, итак определенное отношение т С S х S называют отношением достижимости в ав-томате A. Его симметричная часть а = т П т - 1 называется отношением взаимнойдостижимости в автомате A. Классы эквивалентности а называют слоями автома-та A. В [1] введено понятие каркаса автомата. Каркас автомата A - это упорядочен-ное множество (F(A), элементами которого являются слои автомата A, а порядкомна множестве слоев F(A) = A/а - отношение, обратное отношению достижимости т.Очевидно, что для любого автомата A выполняются неравенства 1 ^ |F(A)| ^ |S|.Если |F(A)| = 1, т. е. отношение а универсально, автомат A называется сильносвяз-ным. Если же |F(A)| = |S|, т. е. отношение а тождественно, а = А, автомат A назовемскелетным. В скелетном автомате отношение достижимости т является порядком намножестве состояний S.Поскольку в скелетном автомате A все слои одноэлементны, можно считать, чтов этом случае каркасом является множество S, упорядоченное обратной достижимо-стью т 1, так что s ^ s означает, что состояние s достижимо из состояния s.Нумерацией состояний автомата называется биективное отображение множестваего состояний S на начальный отрезок [1,m] натурального ряда. Нумерация, по опре-делению, является правильной, если состояния, достижимые из данного состояния,имеют меньшие, чем у него, номера.Теорема 1. В автомате A существует правильная нумерация состояний тогда итолько тогда, когда A - скелетный автомат.Подмножество S' С S называется устойчивым в автомате A, если .(s, x) Е S' длялюбых s Е S' и x Е X. Если S' устойчиво в A, то, ограничивая функцию переходов .на S' х X, получают подавтомат A' = (S', X, .). Совокупность SubA всех подавтоматовавтомата A, упорядоченная отношением A1 ^ A2 ^^ S1 С S2, где Aj = (Sj,X, .),i = 1, 2, является дистрибутивной решеткой. Это решетка подавтоматов автомата A.Известно [2], что для каждого автомата A существует автомат B с двумявходны-ми сигналами, такой, что SubA = SubB, и что не всегда найдется автономный (т. е.с | X| = 1) автомат B с такой же, как у A, решеткой подавтоматов. Минимизацию почислу состояний дает следующее предложение.Теорема 2. Пусть A = (S, X, .) и B = (T, Y, Y) -автоматы, такие, чтоSubA = SubB. Тогда |T | ^ |F (A)|. При этом существует скелетный автомат B, та-кой, что SubA = SubB и |T| = |F(A)|.Пусть K - некоторый класс автоматов и A Е K. Как можно путем в том или иномсмысле минимальных изменений в структуре автомата A получить из него автомат A'из класса K? В числе допустимых приемов реконструкции автомата можно рассмат-ривать, например, отождествление некоторых вершин (факторизация), введение до-полнительных состояний и/или входных сигналов (расширения), перенаправление дугдиаграммы переходов, удаление дуг (замена их петлями) и т. п.Показано, как путем удаления минимального числа дуг в диаграмме перехо-дов G(A) можно получить из данного автомата A скелетный автомат.Подробное изложение представленных результатов можно найти в [3].

Скачать электронную версию публикации