Лекция 2

Машина состояний. Блок-схема алгоритма (БСА). Матричная структура алгоритма (МСА). Строка Тьюринга. Строка Маркова. Строка Ляпунова. Логическая структура алгоритма (ЛСА). Структурное программирование.

Лекция содержит фундаментальные понятия машинных алгоритмов и их использование для проектирования программного обеспечения.

Точного определения алгоритма нет. В 19301950 г. в работах Тьюринга, Поста, Клини, Гёделя сложились три типа уточнения понятия алгоритма: 1) алгоритм-машина (машинный алгоритм); 2) алгоритм-функция (система функций вычислимых алгоритмом, информационная структура алгоритма); 3) алгоритм-исчисление. В настоящее время все три типа алгоритмов используются для решения различных задач и поддерживаются специальными программными средствами в языках программирования.

Принципы, положенные в основу функционирования машинных алгоритмов.

1. Однопроцессорность и поэтому последовательная работа процессора только над одним потоком команд.

2. Управление процессора происходит под действием внешних либо внутренних событий.

3. Алгоритм понимается как последовательность переходов из состояния в состояние под действием команд или последовательностей команд.

4. Управляющие внутренние события воспринимаются как изменения в памяти процессора.

1. Машина состояний (State Machine) – SM.

SM =  S, E, П, P 

а) S = s₀, s₁, …, s_k – алфавит состояний, s₀ – начальное состояние, s_k – конечное состояние.

б) E = e₁, e₂, …, e_n – алфавит событий (events), событие идентифицируется (происходит, совершается) при изменении состояния машины под воздействием команд.

в) П = П₁, П₂, …, П_е – набор элементарных действий, изменяющих состояние машины.

г) P=р₁, р₂, …, р_m – набор правил (команд машины); где вид правила (команда SM) – р = {S(t), e(t), П(t)  S(t + 1)}.

Интерпретация правил SM: если SM находится в момент времени t в состоянии S(t), идентифицируется событие e(t), тогда инициируется действие П(t), которое переводит SM в новое состояние S(t+1); момент времени «t» называется тактом работы SM. В большинстве SM употребляется другой вид правил: р = S(t), e(t),  S(t + 1), П(t + 1) – с интерпретацией: событие e(t) вызывает переход в S(t + 1) и действие П(t + 1) в этот же момент.

Последовательность действий SM, приводящих SM из состояния S₀ в конечное состояние S_k, называется алгоритмом (программой) работы SM.

Исходная информация (данные), промежуточная и результирующая (когда SM попадает в конечное состояние S_k и останавливается) записывается в память SM.

Для абстрактных SM (например, машины Тьюринга) память имеет вид ленты или строки (например, нормального алгоритма Маркова) с определенными свойствами.

2. Машина Тьюринга (мт).

МТ = S, E, П, P определяется как некоторая SM.

а) S – алфавит состояний.

б) E  А={a₁, a_2, …, a_n} – алфавит внешних символов, которые записываются в память (на ленту). Идентификацию символа в момент t в МТ производит специализированный процессор, который называется «управляющей головкой» (УГ). Внешние символы являются событиями, которые управляют процессором УГ.

в) П = {L, R, stop} – алфавит действий УГ.

г) Для МТ определяется набор команд вида

, либо .

Лента МТ представляет своеобразную структуру данных (СД), которая может моделироваться двунаправленным линейным списком, вообще говоря, растущим в обе стороны.

Обозначения в линейном списке:

L – ссылка на предыдущий элемент списка;

R – ссылка на последующий элемент списка;

Z – запись (для МТ это ячейка ленты, куда записывается

единственный символ);

 – спейсер, ограничивающий запись слова.

Строка с такой СД носит название «строка Тьюринга» – (СТ).

Пример SM в виде машины Тьюринга, порождающей слова языка L = aⁿbⁿ; A = {a, b, , } – алфавит символов ленты МТ. Структура данных – СТ;  – пустой символ; начальное состояние СТ – все ячейки пустые;  – спейсер может быть в любой ячейке. SM определяется следующими конструкциями.

а) S = {S_L, S_R, S_stop} – алфавит состояний; S_L – начальное состояние; состояние движения УГ влево, S_stop – конечное состояние, S_R – состояние движения УГ вправо.

б) Правила: Р₁ = {(S_L, , а, R)  S_R}, правило читается так, если SM в состоянии S_L, считывает из элемента списка символ «», то записывает символ «а», по правой ссылке R вызывается следующий элемент списка и SМ переходит в S_R.

Р₂ = {(S_R, , b, L)  S_L}; P₃ = {(S_R, a, a, R)  S_R}

P₄ = {(S_R, b, b, R)  S_R}; P₅ = {(S_L, *, *, stop)  S_R}

P₆ = {(S_L, b, b, L)  S_L}; P₇ = (S_L, a, a, L) S_L}.

Правила работы SM могут быть записаны в виде матриц S  S (матрица состояние/состояние) S  A (матрица состояние/собы-тие). Такая запись называется матричной структурой алгоритма (МСА). Для рассматриваемого примера:

в) Матрица переходов – S  S (состояние/состояние).

	SL	SR	Sstop
SL	a,(a,L) b,(b,L)	(a,R) 	*,(*,stop)
SR	(b,L) 	a,(a,R) b,(b,R)

г) Матрица – S  A (состояние/событие).

	a	b		
SL	(a,L)SL	(b,L)SL	(a,R)SR	*,(*,stop)Sstop
SR	(a,R)SR	(b,R)SR	(b,L)SL

Каждое действие в правилах можно назвать элементарной программой. Набор элементарных программ П = {П₁ = (a,R); П₂ = (b,R); П₃ = (b,L); П₄ = (a,L); П_k = (*, stop)} из которых строятся сценарии работы (поведения) МТ в зависимости от начальной информации на входной ленте.

Программа работы SM может быть задана графом. Для примера на рис.1 приведен граф переходов. Вершины – состояния. Дуги помечены выражением: «если в элементе списка находится символ «х», то замени его на символ «у» и перейди к следующему элементу по ссылке L или R, в соответствии с правилом».

Рис.1 Граф переходов SM, порождающей .

Пример работы SМ со строкой Тьюринга при порождении слова а²b²  L.

0 )  1) а 2) аb

3 ) ab 4) aab 5) aab

6 ) aab 7) aabb 8) aabb

9 ) aabb 10)aabb 11) Stop SM

3. Блок-схема алгоритма (БСА – машина). БСА является еще одной конструкцией алгоритмической машины, к БСА достаточно просто перейти от SM, если задан ее граф переходов.

БСА суть направленный граф с множествами вершин двух типов.

1) П – программные вершины,2) R – вершины-распознаватели. Дуги RП, RR помечаются «+» или «–», дуги ПП, ПR не помечаются. Интерпретация графа: П – программный блок, R – содержит проверку истинности или ложности условия. Проверку выполняет программа, вычисляющая соответствующий предикат.

Интерпретация работы БСА – машины.

1. Машина начинает работу с П₀ (начальный программный блок) и заканчивает (останавливается) после работы над блоком П_k.

2. Переход после окончания работы над блоком П_i к блоку П_J безусловно (по стрелке) либо через распознаватель R по стрелке «+», если условие (предикат) распознавателя выполнено, или по стрелке «–», если условие (предикат) не выполнено. Выполнение/невыполнение условия суть события, на которые БСА реагирует включением того или иного блока.