3.2. Формальные языки и дискретные автоматы

Изучаемые вопросы: Структура формального языка. Построение слов. Дискретные автоматы с памятью и без. Сумматор.

3.2.1. Формальные языки

Здесь будем под языком понимать средство общения автомата с окружающей средой.

Под формальным языком Я будем понимать математический объект, который включает в себя:

1) Состояние языка {S0,S1,…,Sn} = Mn , где S0 – начальное или нейтральное состояние, а само множество Mn – множество нетерминальных символов.

2) Алфавит языка {m1,m2,…,mp} = Mt, состоящий из некоторого набора символов (букв). Заметьте, здесь индексация начинается с 1, само Mt – множество терминальных символов. Чаще всего под символами понимаются двоичные символы 0 и 1.

3) Правила грамматики – показывают как образуются слова языка. Они имеют вид соотношений

Sl ::= Skmi, (1)

где i = 0,1,2,…,p; l,k = 0,1,2,…,n. Это соотношение означает, что при переходе из состояния Sk в Sl появляется буква mi образуемого слова. При этом значению i=0 соответствует буква m0, которая не входит в алфавит, а представляет собой знак пробела или некоторый интервал между словами.

Образование каждого слова начинается из начального состояния S0 и им же заканчивается (далее идет пробел).

Язык задан, если формула вида (1) определена для каждой пары состояний Sk, Sl.

Пример 1: Язык Я с алфавитом Mt={m1,m2,m3} задан совокупностью следующих правил грамматики:

S1:: = S0m0; S2:: = S1m1|S2m3; S3:: = S0m0|S2m2; S0:: = S3m1. (2)

(Здесь обозначение означает и/или).

○Построение слов в языке Я удобно проводить с помощью графов: в вершинах помещаются состояния S, а рядом с дугой, соединяющей Sk и Sl пишут появляющуюся при этом букву mi. Начнем с S0. С этим состоянием связаны состояния S1 и S3: дуги и производят пробел , а дуга ­­- букву ; дуга - букву ; дуга производит букву , дуга ­-­ букву .

m1 получаем все возможные слова:

m0 1) m1m2m1;

2) m1m3m2m1;

m3 3) m1;

m0 (m­0 –пробел – не пишется)!

m2 Тогда

m1 Я = {m1, m1m2m3, m1m3m2m1}.●

Пример 2: Язык Я с алфавитом Mt = {m1,m2,m3} задан совокупностью правил:

S1:: = S0m0|S2m2; S2:: = S1m1; S3:: = S2m3|S3m2; S0:: = S4m3|S3m1.

Изобразить в виде графа структуру языка и построить совокупность слов, порождаемых грамматикой данного языка.

○Слова:

1)[m­1m2 m1] n m3m1, n-любое (тавтология, т.е. повторение одного и того же)

2)[m­1m2m1]nm3m2m1, также тавтология

3) m1m3m1

4)m1m3m2m1

Здесь состояние ­- «мёртвое», поскольку в него невозможно попасть. (Такие ситуации возможны при проводившейся ранее коррекции языка).

●

3.2.2. Дискретные автоматы (ДА)

ДА – это устройство, служащее для восприятия, переработки поступающей извне информации и выработки соответствующей реакции на эту информацию.

(Здесь считаем, что информация дискретна, т.е. поступает в отдельно взятые моменты времени.)

Для двоичных сигналов (0 и 1) и автоматы называются двоичными.

Пусть ДА имеет k входов и q выходов, тогда совокупность входных (x1,x2,…,xk) и выходных (y1,y2,…,yq) сигналов можно трактовать как векторы X и Y соответствующих размерностей:

Рассмотрим два типа ДА:

1. Без памяти (или комбинационная схема КС)

2. С памятью (последовательная схема ПС).

В КС для текущего момента времени Yn = fкс (Xn), (1)

т.е. выходные сигналы являются функцией только входных.

В ПС они зависят и от предыдущего момента n-1:

Yn = fпс (Xn, Xn-1) (2)

Поскольку рассматриваем двоичные дискретные автоматы, то f являются не обычными алгебраическими функциями, но булевскими. И проблема математического описания поведения ДА решается на основе аппарата алгебры логики.

Пусть в некоторый момент времени ДА находится в состоянии Sk и под воздействием входного сигнала x, поступающего в этот момент, переходит в состояние Sl, вырабатывая выходной сигнал y, тогда процесс перехода ДА из Sk в Sl можно записать:

Sk ® xySl (3)

Рассмотрим ДА без памяти (КС)

Пример: пусть работа ДА задана совокупностью правил:

S1 ® x2y2S1, S1 ® x1y1S2, S2 ® x1y1S2, S2 ® x2y1S3, S3 ® x1y2S1.

И пусть на вход подана последовательность: х2, х1, х2, х1, а ДА установлен в состояние S1. Определить последовательность на выходе. Интерпретируем правила работы ДА в виде графа:

Так как начальное состояние и первый входной сигнал х2, то, в соответствии с графом, первым выходным сигналом будет y2 и ДА останется в состоянии .

Рассмотрим теперь ДА с памятью (ПС)

Пример: пусть имеется устройство с входным каналом Х, каналом обратной связи Z и выходным каналом Y, реализующее отображение

,

которое задается в виде таблицы (*).

Структурная схема блока:

момента, т.е.Z+(t)=Z-(t-t), t>0.

(Считается, Z+(t=0)=Z0+).

Z+ Z-

X Y

Пусть на вход подается последовательность 101001 и Z0+ = 0. Определить последовательность на выходе.

Табл.(*) В t = 0 вектор XZ+, равный 10 ( Х = 1 – первый член входной последовательности, Z+ = Z0+ = 0), определяет, в соответствие с третьей строкой (*) вектор 01.

Это решение удобно представить в виде табл.(**): Ответ: 101001 110100. Табл.(**)

Работа сумматора подробно описана в [3].

Вопросы для самопроверки по теме 3.2

1. Что означает «язык задан»?

2. В чём отличие комбинационной схемы от последовательной?

3. Что означает запись ?