Элементарные конечные автоматы

В настоящее время в вычислительной технике, как правило, используются элементарные автоматы, имеющие следующие особенности:

1. Элементарные автоматы являются автоматами Мура с двумя внутренними состояниями;

2. Автомат выдает два различных выходных сигнала, соответствующих двум его внутренним состояниям. В дальнейшем состояния автомата и его выходные сигналы будем обозначать одной буквой Q и кодировать цифрами 0 и 1;

3. Элементарные автоматы могут иметь в общем случае несколько физических входов, на каждый из которых могут подаваться сигналы, закодированные цифрами 0 и 1.

В качестве элементарных автоматов в вычислительной технике используются, в основном, триггеры различных типов.

Задача синтеза конечных автоматов заключается в построении сложного автомата из более простых автоматов, называемых элементарными автоматами. На практике в большинстве случаев применяют элементарные автоматы с двумя внутренними устойчивыми состояниями, которые соединяются между собой с помощью логических элементов таким способом, чтобы обеспечить функционирование схемы в соответствии с заданными кодированными таблицами переходов и выходов.

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

1.Элементарные автоматы, например триггера, являются автоматами Мура и имеют два внутренних устойчивых состояния.

2. Двум внутренним состояниям элементарного автомата соответствуют два различных выходных сигнала, которые по существу и позволяют физически различать состояния элементарных автоматов.

3. В общем случае элементарные автоматы могут иметь несколько физических входов.

Для того чтобы можно было построить схему любого конечного автомата, набор элементов, с помощью которых проводится синтез автомата, должен быть функционально полным и включать в себя в качестве элементарных автоматов триггера, т.е, необходимо и достаточно, чтобы он содержал:

- хотя бы один элементарный автомат с двумя различными состояниями, для которых соблюдаются условия полноты системы переходов и выходов;

- логические элементы, образующие функционально полную систему для синтеза логических комбинационных схем.

Дата добавления: 2015-07-26; просмотров: 152; Нарушение авторских прав

Мы поможем в написании ваших работ!