Входным словом называется совокупность сигналов, поступающих на вход.
Выходным словом называются совокупность сигналов на выходе.
Два автомата называются эквивалентными, если они имеют одинаковый входной и выходной алфавит, и на одинаковые входные слова выдают одинаковые выходные слова.
Два состояния одноэквивалентными, если на одинаковое входное слово выдается одинаковый выходной сигнал.
Два состояния k-эквивалентными, если на одинаковое входное слово длиной в k-единиц выдается одинаковый выходной сигнал длиной в k-единиц.
Эквивалентными состояниями называются k-эквивалентные состояния для любых k.
Эквивалентные состояния объединяются в класс эквивалентности.
Минимальный автомат – это автомат, состоящий из наименьшего числа состояний, каждое из которых является классом эквивалентности исходного автомата.