Классификация языков по Хомскому.

Для описания (задания) ЦА используются разнообразные средства, называемые языками, которые делятся на начальные и автоматные языки. Поскольку языки базируются на алфавитах, то применительно к ЦА множество Х трактуется в качестве входного алфавита, множество Y - выходного алфавита, а множество S - внутреннего алфавита. Как и для других объектов, для автоматов используются разные таблицы, матрицы, графы.

Наиболее общее при выработке выходных сигналов, формировании новых состояний под действием входных сигналов отражается законом функционирования автомата [4, 12]:

s(t)= d (s(t-1), x(t)),

y(t)= l (s(t-1), x(t)).

Как видно, закон функционирования представляет собой совокупность двух функций: функции перехода d и функции выхода l.

В формулах используются обозначения:

t - данное автоматное время,

t-1 - предыдущее автоматное время,

d - оператор формирования данного состояния s,

l - оператор формирования данного выходного сигнала y,

х - входной сигнал.

Видно, что данное состояние s(t) зависит от предыдущего состояния

s(t-1) и входного сигнала в данный момент времени, что выходной сигнал в данный момент времени так же определяется предыдущим состоянием и входным сигналом в данный момент времени.

ЦА строится по имеющемуся алгоритму, представленному в виде граф-схемы алгоритма (ГСА). Определяются состояния, число триггеров памяти, синтезируются логические схемы.

При наличии простейших автоматов может реализовываться их комбинация, получаться более сложный новый автомат.

Над имеющимися автоматами можно выполнять другие разнообразные операции, их результаты будут новыми автоматами. Например, операция пе-ресечения ЦАС= ЦАА ЦАВ даёт автомат С, состоящий из совпадающих фрагментов исходных автоматов А и В.

Для задания (описания) автоматов используются языки описания, в настоящее время под языком понимается совокупность средств описания.

Все языки применительно к автоматам делятся на начальные и на автоматные.