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

UptoLike

ВУЗ: 

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

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

Рубрика: 

6
1. ОСНОВЫ ТЕОРИИ ФОРМАЛЬНЫХ ГРАММАТИК
1.1. Основные понятия теории автоматов
Термин «автомат», как правило, используется в двух аспектах. С одной сторо-
ны, автомат - это устройство, выполняющее некоторые функции без непосредствен-
ного участия человека. В этом смысле мы говорим, что ЭВМ – автомат, так как после
загрузки программы и исходных данных ЭВМ решает заданную задачу без участия
человека. С другой стороны, термин «автомат» как математическое понятие обозна-
чает математическую модель реальных технических автоматов. В этом смысле авто-
мат представляется как «черный ящик», имеющий конечное число входов и выходов
и некоторое множество внутренних состояний Q = {q
1
(t), q
2
(t), ..., q
n
(t)}, в которые он
под действием входных сигналов переходит скачкообразно, т. е. практически мгно-
венно, минуя промежуточное состояние. Конечно, это условие не выполняется в ре-
альности, так как любой переходный процесс длится конечное время.
Автомат называется конечным, если множество его внутренних состояний и
множество значений входных сигналов – конечные множества.
На практике часто используется понятие цифрового автомата, под которым по-
нимают устройство, предназначенное для преобразования информации. С общей точ-
ки зрения, процесс получения информации есть ни что иное, как процесс снятия не-
определенности в результате того, что из некоторой совокупности возможных в дан-
ной конкретной ситуации явлений выделяется явление, фактически имевшее место.
Таким образом, в понятии информации существенно не само происшедшее явление, а
лишь его отношение к совокупности явлений, которые могли произойти.
Устройства, служащие для преобразования дискретной информации, называ-
ются дискретными автоматами.
В современных дискретных автоматах принято обычно отождествлять буквы
используемого стандартного алфавита с цифрами той или иной системы счисления.
В состав цифровых автоматов обязательно входят запоминающие элементы
(элементы памяти). Выходные сигналы в таких автоматах формируются в зависимо-
сти от входных сигналов и состояний, в которых находятся элементы памяти. Поэто-
му дискретные автоматы принято называть также цифровыми автоматами.
Основным качеством, выделяющим дискретные автоматы из числа всех других
преобразователей информации, является наличие дискретного множества внутренних
состояний и свойства скачкообразного перехода автомата из одного состояния в дру-
гое. Скачкообразность перехода означает возможность трактовать этот переход как
мгновенный, хотя для любого реально существующего автомата имеет место конеч-
ная длительность переходных процессов, так что требование скачкообразности пере-
хода не удовлетворяется.
Второе допущение состоит в том, что после перехода автомата в произвольное
состояние переход в следующее состояние оказывается возможным не ранее, чем че-
рез некоторый фиксированный для данного автомата промежуток времени τ > 0, так
называемый интервал дискретности автомата. Это допущение дает возможность рас-
сматривать функционирование цифрового автомата в дискретном времени. При по-
строении автоматов с дискретным автоматным временем различают синхронные и
асинхронные автоматы.

Страницы