ГЛАВА 3. ЭКВИВАЛЕНТНОСТЬ И МИНИМИЗАЦИЯ АВТОМАТОВ

3.1. Введение

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