ВУЗ:
Составители:
Рубрика:
89
3.12. МИНИМИЗАЦИЯ КОНЕЧНЫХ АВТОМАТОВ
С практической точки зрения при функционировании автомата
представляет интерес только зависимость между входами и выходами
автомата, а роль его состояний сводится исключительно к участию в
формировании этих зависимостей в качестве промежуточных переменных.
Следовательно, любая совокупность состояний, обеспечивающая требуемые
зависимости между входом и выходом, может б ыть выбрана в качестве
множества состояний автомата. В то же время этот выбор естественно
подчинить определенным целям, например, минимизации числа состояний,
что уменьшает количество требуемых элементов памяти, однако может
привести к усложнению комбинационной схемы автомата.
Задача минимизации количества состояний в полностью описанном
автомате сводится к определению попарно эквивалентных состояний и
последующему их объединению. Так, для автомата, заданного таблицей
переходов (см. таблицу 3.8), состояния s
0
и s
2
являются эквивалентными и
объединяются в одно, например s
0
,при этом общая таблица переходов
принимает вид табл.3.9, а исходный граф автомата, изображенный на
рис.3.12, преобразуется к виду, показанному на рис.3.13.
Таблица 3.9
Общая таблица переходов
Рис.3.12. Граф исходного автомата Рис.3.13. Граф
эквивалентного автомата
Страницы
- « первая
- ‹ предыдущая
- …
- 87
- 88
- 89
- 90
- 91
- …
- следующая ›
- последняя »
