<<
>>

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=(x1,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-t), t>0.

(Считается, Z+(t=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.

В следующий момент 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. Табл.(**)

Время X Z+ Z- Y
0 1 0 0 1
t 0 0 1 1
2t 1 1 0 0
3t 0 0 1 1
4t 0 1 1 0
5t 1 1 0 0

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

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

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

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

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

<< | >>
Источник: Т.Д.Бессонова, Н.М.Петухова, В.В. Тарасенко. Математика ч.2: учебно-методический комплекс / сост. Т.Д.Бессонова, Н.М.Петухова, В.В. Тарасенко - СПб.: Изд-во CЗТУ,2008. – 158 с.. 2008

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

  1. СООТНОШЕНИЕ ЭВРИСТИЧЕСКОЙ И РЕГУЛЯТИВНОЙ ФУНКЦИИ ФИЛОСОФСКИХ ПРИНЦИПОВ в ФОРМИРОВАНИИ НОВОЙ ФИЗИЧЕСКОЙ ТЕОРИИ
  2. Язык классической логики
  3. Базисный ассерторический язык
  4. 1.3.4. Элементарные вопросы и стззты на них: аббревиатуры и формальная запись
  5. ЛОГИКА ФОРМАЛЬНАЯ
  6. ОБЩИЕ ВЫВОДЫ
  7. РАЗДЕЛ VI СИНТАКСИС СОВРЕМЕННОГО РУССКОГО ЯЗЫКА
  8. История логики
  9. 2.2 Онтология, эпистемология и философия языка Рассела
  10. 1.1. Предисловие
  11. 2.1. Рабочая программа (объем дисциплины 150 часов)
  12. 2.2. Тематический план дисциплины
  13. Раздел 3. ДИСКРЕТНАЯ МАТЕМАТИКА
  14. 3.2. Формальные языки и дискретные автоматы
  15. 4.3. Блок текущего контроля
  16. Содержание
  17. СТРУКТУРНЫЕ МОДЕЛИ ЯЗЫКА
  18. ПРОГРАММЫ ФОРМИРОВАНИЯ СУЖДЕНИЙ, РАБОТАЮЩИЕ С ЕСТЕСТВЕННЫМ ЯЗЫКОМ
  19. Большинство исследователей, работающих в области филосо­фии языка, а в последнее время даже и некоторые лингвисты признают, что удовлетворительная семантическая теория должна отвечать на вопрос о том, каким образом значения[63] предложений зависят от значений слов.