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

UptoLike

ВУЗ: 

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

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

Рубрика: 

8
его входных и выходных сигналов. Входные и выходные сигналы рассматриваются
при этом просто как буквы двух фиксированных для данного автомата алфавитов:
входного и выходного. Не интересуясь способом построения автомата, абстрактная
теория изучает лишь те переходы, которые претерпевает автомат под воздействием
входных сигналов, и те выходные сигналы, которые он при этом выдает.
В противоположность абстрактной теории, структурная теория автоматов учи-
тывает структуры автомата и его входных и выходных сигналов. В структурной тео-
рии изучаются способы построения автоматов из нескольких элементарных автома-
тов, способы кодирования входных и выходных сигналов элементарными сигналами,
передаваемыми по реальным входным и выходным каналам.
Таким образом, структурная теория автоматов является продолжением и даль-
нейшим развитием абстрактной теории. В частности, задача синтеза идеализирован-
ного (без учета переходных процессов) цифрового автомата естественным образом
подразделяется на этапы абстрактного и структурного синтеза.
Частным случаем дискретных автоматов являются автоматы, обладающие
лишь одним внутренним состоянием. Такие автоматы называются комбинационны-
ми схемами или автоматами без памяти. Работа таких автоматов состоит в том,
что они сопоставляют каждому входному сигналу x(t) выходной сигнал y(t).
Абстрактная теория автоматов без памяти совершенно тривиальна, а структур-
ная теория таких автоматов много легче, чем теория произвольных автоматов с памя-
тью. Основная идея излагаемой методики синтеза автоматов состоит в том, чтобы еще
на уровне абстрактной теории преодолеть основные затруднения, вызванные наличи-
ем памяти, а на уровне структурной теории свести задачу синтеза автомата к задаче
синтеза комбинационных схем.
1.2. Основные понятия теории формальных грамматик
В общем случае язык представляет собой бесконечное множество, а бесконеч-
ные объекты даже задать трудно: их невозможно задать простым перечислением эле-
ментов. Любой конечный механизм задания языка называется грамматикой.
Формальный язык представляет собой множество цепочек в некотором конеч-
ном алфавите. К формальным языкам можно отнести искусственные языки для обще-
ния человека с машиной – языки программирования.
Для задания описания формального языка необходимо, во-первых, указать ал-
фавит, т. е. совокупность объектов, называемых символами (или буквами), каждый из
которых можно воспроизводить в неограниченном количестве экземпляров (подобно
обычным печатным буквам или цифрам), и, во-вторых, задать формальную граммати-
ку языка, т. е. перечислить правила, по которым из символов строятся их последова-
тельности, принадлежащие определяемому языку, – правильные цепочки.
Правила формальной грамматики можно рассматривать как продукции (прави-
ла вывода), то есть элементарные операции, которые, будучи применены в опреде-
ленной последовательности к исходной цепочке (аксиоме), порождают лишь пра-
вильные цепочки. Сама последовательность правил, использованных в процессе по-
рождения некоторой цепочки, является ее выводом. Определенный таким образом
язык представляет собой формальную систему.
По способу задания правильных цепочек формальные грамматики разделяются
на порождающие и распознающие. К порождающим относятся грамматики языка L,

Страницы