Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
УМК Математика ч.2-2-ое издание 97-2003-испр.doc
Скачиваний:
25
Добавлен:
30.04.2019
Размер:
6.18 Mб
Скачать

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 соответствующих размерностей:

X

ДА

=(x
1,x2,…,xk) Y=(y1,y2,…,yq)

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

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 и ДА останется в состоянии . Следующий входной - х1, тогда y1 и . Далее, y1 и , потом y2 и , т.е. последовательность сигналов на выходе: y2, y1, y1, y2.

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

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

,

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

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

З

Память

Комбинационная

часть

десь входной сигнал задается не только входным Х в момент t, но и выходным сигналом предшествующего

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

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

Z+ Z-

X Y

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

X

Z+

Z-

Y

0

0

1

1

0

1

1

0

1

0

0

1

1

1

0

0

Табл. (*) В t = 0 вектор XZ+, равный 10 ( Х = 1 – первый член входной последовательности, Z+ = Z0+ = 0), определяет, в соответствие с третьей строкой (*) вектор 01. В следующий момент  входной вектор Х = 0(второй член входной последовательности), а Z+() = Z-() = Z-(0) = 0, тогда в t = XZ+ = 00 и из первой строки (*): Z-Y = 11. В t = 2 XZ+ = 11 (X = 1 – третий член входной последовательности), а Z+(2) = Z-(), и из 4-й строки (*) Z-Y = 00 etc.

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