|
Читайте также: |
Автоматы являются устройствами для переработки дискретной информации. При этом характером перерабатываемой информации определяется входной и выходной алфавиты (
и 
); алфавит внутренних состояний (
) определяется строением автомата и, вообще говоря, он может различаться у разных автоматов с одинаковыми входными и выходными алфавитами. Следовательно, одно и то же преобразование информации может быть осуществлено автоматами с разным числом состояний и, следовательно, посредством различного числа команд. Введём ряд определений:
Состояния 
автомата 
и 
автомата 
считаются эквивалентными, если оба автомата, получив одну и ту же (любую) входную последовательность символов, перерабатывают её в одинаковую выходную последовательность.
Автоматы и называются эквивалентными, если для каждого состояния автомата существует эквивалентное ему состояние автомата и наоборот.
Другими словами, эквивалентные автоматы реализуют одинаковые преобразования, но могут иметь различное число внутренних состояний.
Понятие эквивалентности состояний применимо и к одному автомату (формально можно считать, что и совпадают). Для одного автомата эквивалентными будут различные состояния, через которые одна и та же входная последовательность символов преобразуется в одинаковую выходную.
Дата добавления: 2015-10-28; просмотров: 39 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Тема 18.2. Способы задания конечного автомата | | | Тема 18.4. Автоматы Мура и Мили |