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

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

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

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

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

1) Состояние языка {S₀,S₁,…,S_n} = M_n , где S₀ – начальное или нейтральное состояние, а само множество M_n – множество нетерминальных символов.

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

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

S_l ::= S_km_i, (1)

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

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

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

Пример 1: Язык Я с алфавитом M_t={m₁,m₂,m₃} задан совокупностью следующих правил грамматики:

S₁:: = S₀m₀; S₂:: = S₁m₁|S₂m₃; S₃:: = S₀m₀|S₂m₂; S₀:: = S₃m₁. (2)

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

○Построение слов в языке Я удобно проводить с помощью графов: в вершинах помещаются состояния S, а рядом с дугой, соединяющей S_k и S_l пишут появляющуюся при этом букву m_i. Начнем с S₀. С этим состоянием связаны состояния S₁ и S₃: дуги и производят пробел , а дуга ­­- букву ; дуга - букву ; дуга производит букву , дуга ­-­ букву . При обходе всего цикла из в

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

m₀ 1) m₁m₂m₁;

2) m₁m₃m₂m₁;

m₃ 3) m_1;

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

m₂ Тогда

m₁ Я = {m₁, m₁m₂m₃, m₁m₃m₂m₁}.●

Пример 2: Язык Я с алфавитом M_t = {m₁,m₂,m₃} задан совокупностью правил:

S₁:: = S₀m₀|S₂m₂; S₂:: = S₁m₁; S₃:: = S₂m₃|S₃m₂; S₀:: = S₄m₃|S₃m₁.

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

○Слова:

1)[m­₁m₂ m₁] ⁿ m₃m₁, n-любое (тавтология, т.е. повторение одного и того же)

2)[m­₁m₂m₁]ⁿm₃m₂m₁, также тавтология

3) m₁m₃m₁

4)m₁m₃m₂m₁

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

●

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

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

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

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

Пусть ДА имеет k входов и q выходов, тогда совокупность входных (x₁,x₂,…,x_k) и выходных (y₁,y₂,…,y_q) сигналов можно трактовать как векторы X и Y соответствующих размерностей:

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

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

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

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

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

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

Y_n = f_пс (X_n, X_n-1) (2)

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

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

S_k ® xyS_l (3)

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

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

S₁ ® x₂y₂S₁, S₁ ® x₁y₁S_2, S₂ ® x₁y₁S₂, S₂ ® x₂y₁S₃, S₃ ® x₁y₂S₁.

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

Так как начальное состояние и первый входной сигнал х₂, то, в соответствии с графом, первым выходным сигналом будет y₂ и ДА останется в состоянии . Следующий входной - х₁, тогда y₁ и . Далее, y₁ и , потом y₂ и , т.е. последовательность сигналов на выходе: y₂, y₁, y₁, y₂.

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

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

,

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

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

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

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

Z⁺ Z^-

X Y

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

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

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

Ответ: 101001 110100. Табл.(**)

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

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

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

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

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