Читать «Математический аппарат инженера» онлайн - страница 66
Виталий Петрович Сигорский
При реализации автоматов в двоичном структурном алфавите можно использовать рассмотренные ранее методы синтеза
- 571 -
комбинационных схем. Но для этого необходимо закодировать состояния схемы н представить характеристические функции в виде булевых функций двоичных переменных. Такое кодирование можно осуществить преобразованием общей таблицы перехода автомата к таблице соответствия в двоичном структурном алфавите. Если элементы множеств
Заменяя десятичные числа их двоичными эквивалентами, читаемыми сверху вниз, получаем таблицу соответствия, в которой значения функций s(
Рис. 239. Структурная схема конечного автомата
Отсюда видно, что комбинационная схема должна иметь четыре входа, соответствующие входным переменным
7. Минимизация автоматов. С утилитарной точки зрения интерес представляет только зависимость между входами и выходами автомата, а роль его состоянии сводится исключительно к участию в формировании этих зависимостей в качестве промежуточных переменных. Следовательно, любая совокупность состояний, обеспечивающая требуемые зависимости между входом и выходом, может быть выбрана в качестве множества состоянии автомата. В то же
- 572 -
время этот выбор естественно подчинить определенным целям, например, минимизации числа состояний или оптимизации автомата в каком-либо смысле. Следует иметь в виду, что с уменьшением числа состоянии уменьшается и количество требуемых элементов памяти, но это может привести к усложнению комбинационной схемы автомата. Поэтому синтез наиболее экономичного автомата часто требует поиска удачного компромисса между сложностью его комбинационной и запоминающих частей.
Рис. 240. Граф конечного автомата (
Минимизация числа состоянии полных автоматов связана с отношением эквивалентности. Пусть автоматы