Математический аппарат инженера
Шрифт:
Аналогичные определения можно дать для некоторых совокупностей состояний, рассматриваемых как подавтоматы. Если начальное состояние автомата М принадлежит непустому множеству Si состояний, которое составляет тупиковый или изолированный подавтомат, то M можно упростить исключением всех состояний, которые не принадлежат множеству Si, и всех дуг, начинающихся в этих состояниях.
Пусть М1, М2 и M3 – соответственно преходящий, тупиковый и изолированные подавтоматы автомата М, которые характеризуются множествами
– 570 -
где 11, 22, 33– матрицы подавтоматов М1, М2 и М3; 12– матрица, характеризующая переходы от состояний преходящего автомата М1 к состояниям тупикового автомата М2. Отсюда следует, что разбиение автомата М на подавтоматы М1, М2 и М3 можно осуществить преобразованием его матрицы соединений к стандартному виду путем перестановки соответствующих строк и столбцов. Например, для автомата, граф которого изображен на рис. 238, имеем:
Рис. 237. Обобщенный граф конечного автомата.
Рис. 238. Граф конечного автомата к примеру разбиения на подавтоматы.
Отсюда следует, что S1 = {3, 6} составляет преходящий подавтомат, S2 = {2, 4, 7} - тупиковый подавтомат и S3 = {1, 5} - изолированный подавтомат. Если начальное состояние принадлежит множеству S2, то можно упростить автомат, исключив состояния S1 S3 = {3, 6, 1, 5}, а в случае принадлежности начального состояния множеству S3 автомат упрощается исключением состояний S1 S2 = {3, 6, 2, 4, 7}.
6. Синтез конечных автоматов. Реализация конечных автоматов сводится к синтезу соответствующей комбинационной схемы, преобразующей входные переменные x и s в выходные переменные y и s( + 1) в соответствии с заданными характеристическими функциями s( + 1) = (x, s) и y= (x, s). Для сохранения состояний s( + 1) до следующего такта в цепь обратной связи вводится необходимое количество элементов памяти.
При реализации автоматов в двоичном структурном алфавите можно использовать рассмотренные ранее методы синтеза
– 571 -
комбинационных схем. Но для этого необходимо закодировать состояния схемы н представить характеристические функции в виде булевых функций двоичных переменных. Такое кодирование можно осуществить преобразованием общей таблицы перехода автомата к таблице соответствия в двоичном структурном алфавите.
Заменяя десятичные числа их двоичными эквивалентами, читаемыми сверху вниз, получаем таблицу соответствия, в которой значения функций s( + 1) и у представлены двоичными кодами:
Рис. 239. Структурная схема конечного автомата
Отсюда видно, что комбинационная схема должна иметь четыре входа, соответствующие входным переменным x1, х2 и переменным состояния s, s2, а также три выхода, соответствующие переменным состояния s1( + 1), s2( + 1) и выходной переменной у1. Синтезировав комбинационную схему, соответствующую полученной таблице и введя два элемента задержки З1 и З2, получим структурную схему автомата (рис. 239).
7. Минимизация автоматов. С утилитарной точки зрения интерес представляет только зависимость между входами и выходами автомата, а роль его состоянии сводится исключительно к участию в формировании этих зависимостей в качестве промежуточных переменных. Следовательно, любая совокупность состояний, обеспечивающая требуемые зависимости между входом и выходом, может быть выбрана в качестве множества состоянии автомата. В то же
– 572 -
время этот выбор естественно подчинить определенным целям, например, минимизации числа состояний или оптимизации автомата в каком-либо смысле. Следует иметь в виду, что с уменьшением числа состоянии уменьшается и количество требуемых элементов памяти, но это может привести к усложнению комбинационной схемы автомата. Поэтому синтез наиболее экономичного автомата часто требует поиска удачного компромисса между сложностью его комбинационной и запоминающих частей.
Рис. 240. Граф конечного автомата (а) и его сокращенная форма (б)
Минимизация числа состоянии полных автоматов связана с отношением эквивалентности. Пусть автоматы М1 и М2, находящиеся соответственно в начальных состояниях, i и j (обозначения М1 и М2 могут относиться к одному и тому же автомату), под воздействием любой входной последовательности выдают одинаковые выходные последовательности, т. е. автоматы М1 и М2 в данных состояниях i и j неразличимы по внешним выходам. Такое отношение между состояниями одного и того же или двух различных автоматов обладает свойствами рефлексивности, симметричности и транзитивности, следовательно, оно является отношением эквивалентности состояний. Если состояния не эквивалентны, то их называют различимыми. Легко доказать справедливость следующих положений:
1) состояния i и j автомата явно различимы, если различаются соответствующие, им строки в таблице выходов;
2) состояния i и j автомата явно эквививалентны, если соответствующие им строки в таблице переходов и таблице выходов одинаковы или становятся одинаковыми при замене каждого номера i на номер j (или наоборот).
Например, для автомата, граф которого изображен на рис. 240, а, общая таблица переходов имеет вид: