Синтез цифровых автоматов. Захаров Н.Г - 34 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

33
Контрольные вопросы
1. Машины Тьюринга. Основные понятия.
2. Детерминированный конечный автомат.
3. Машина Тьюринга с двумя выходами.
4. Машины Тьюринга и линейно-ограниченные автоматы.
5. Автоматы с магазинной памятью.
6. Недетерминированный магазинный автомат.
7. Бесконтекстные языки.
3. АБСТРАКТНЫЙ КОНЕЧНЫЙ АВТОМАТ
3.1. Абстрактная теория автоматов
Объектом изучения в абстрактной теории автоматов являются абстрактные ав-
томаты вместе с реализуемыми ими отображениями и событиями. Определим поня-
тия изоморфности, эквивалентности, однозначности функций переходов и выходов.
При синтезе цифровых автоматов будем употреблять такие обобщения понятия абст-
рактного автомата, для которых не выполняются условия полной определенности
(частичные автоматы).
3.1.1. Модель дискретного преобразователя Глушкова В. М.
Дискретный преобразователь представляет собой абстрактный автомат А,
функционирующий по соответствующим законам в дискретном времени.
Абстрактный автомат А задается совокупностью шести объектов:
А = (Х, Y, Q, q
0
, δ, λ),
где Х – конечное множество входных сигналов, называемое входным алфави-
том автомата;
Y – конечное множество выходных сигналов, называемое выходным алфави-
том автомата;
Q – произвольное множество, называемое множеством состояний автомата;
q
0
– элемент из множества Q, называемый начальным состоянием автомата;
δ(q, x) и λ(q, x) – две функции, задающие однозначные отображения множе-
ства пар (q, x), где q∈Q и x∈X, в множества Q и Х. Функция δ(q, x) называется
функцией переходов автомата, а функция λ(q, x) – функцией выходов, либо сдвину-
той функцией выходов.
Автомат, заданный функцией выходов, называется автоматом первого рода;
автомат, заданный сдвинутой функцией выходов, – автоматом второго рода.
Абстрактный автомат функционирует в дискретном времени, принимающем
целые неотрицательные значения t = 0, 1, 2, … В каждый момент t этого времени он
находится в определенном состоянии q(t) из множества Q состояний автомата, при-
чем в начальный момент времени t = 0 автомат всегда находится в своем начальном
состоянии q
0 ,
т. е. q(0) = q
0
.

Страницы