Расчетно-графическая работа №5

Тема: «Нормальные алгоритмы Маркова и машины Тьюринга».

1 Теоретическая часть

1.1 Нормальные алгоритмы Маркова

Интересной особенностью нормальных алгоритмов Маркова (НАМ) является то, что в них используется лишь одно элементарное действие – так называемая подстановка.

Формулой подстановки называется запись вида α→β (читается «α заменить на β»), где α и β – любые слова (возможно, и пустые). При этом α называется левой частью формулы, а β – правой частью.

Сама подстановка (как действие) задается формулой подстановки и применяется к некоторому слову Р. Суть операции сводится к тому, что в слове Р отыскивается часть, совпадающая с левой частью этой формулы (т.е. с α), и она заменяется на правую часть формулы (т.е. на β). При этом остальные части слова Р (слева и справа от α) не меняются. Получившееся слово R называют результатом подстановки. Условно это можно изобразить так:

P

x

α

y

→

R

x

β

y

 

Необходимые уточнения:

1. Если левая часть формулы подстановки входит в слово Р, то говорят, что эта формула применима к Р. Но если α не входит в Р, то формула считается неприменимой к Р, и подстановка не выполняется.

2. Если левая часть α входит в Р несколько раз, то на правую часть β, по определению, заменяется только первое вхождение α в Р:

 

P

x

α

y

α

z

→

R

x

β

y

α

z

 

3. Если правая часть формулы подстановки – пустое слово, то подстановка α→ сводится к вычеркиванию части α из Р (отметим попутно, что в формулах подстановки не принято как-либо обозначать пустое слово):

 

P

x

α

y

→

R

x

y

 

4. Если в левой части формулы подстановки указано пустое слово, то подстановка →β сводится, по определению, к приписыванию β слева к слову P:

P

x

→

R

β

x

 

Из этого правила вытекает очень важный факт: формула с пустой левой частью применима к любому слову. Отметим также, что формула с пустыми левой и правой частями не меняет слово.

Нормальным алгоритмом Маркова (НАМ) называется непустой конечный упорядоченный набор формул подстановки:

		k>=1

 

 

В этих формулах могут использоваться два вида стрелок: обычная стрелка (→) и стрелка «с хвостиком» (). Формула с обычной стрелкой называется обычной формулой, а формула со стрелкой «с хвостиком» – заключительной формулой.

Записать алгоритм в виде НАМ – значит предъявить такой набор формул.

Правила выполнения НАМ.

Прежде всего, задается некоторое входное слово Р. Где именно оно записано – не важно, в НАМ этот вопрос не оговаривается.

Работа НАМ сводится к выполнению последовательности шагов. На каждом шаге входящие в НАМ формулы подстановки просматриваются сверху вниз и выбирается первая из формул, применимых к входному слову Р, т.е. самая верхняя из тех, левая часть которых входит в Р. Далее выполняется подстановка согласно найденной формуле. Получается новое слово Р′.

На следующем шаге это слово Р′ берется за исходное и к нему применяется та же самая процедура, т.е. формулы снова просматриваются сверху вниз начиная с самой верхней и ищется первая формула, применимая к слову Р′, после чего выполняется соответствующая подстановка и получается новое слово Р′′. И так далее:

Р → Р′ → Р′′ → …

Следует обратить особое внимание на тот факт, что на каждом шаге формулы в НАМ всегда просматриваются начиная с самой первой.

Необходимые уточнения:

1. Если на очередном шаге была применена обычная формула (α→β), то работа НАМ продолжается.

2. Если же на очередном шаге была применена заключительная формула (α β), то после её применения работа НАМ прекращается. То слово, которое получилось в этот момент, и есть выходное слово, т.е. результат применения НАМ к входному слову.

3. Если на очередном шаге к текущему слову неприменима ни одна формула, то и в этом случае работа НАМ прекращается, а выходным словом считается текущее слово.

Таким образом, НАМ останавливается по двум причинам: либо была применена заключительная формула, либо ни одна из формул не подошла. То и другое считается «хорошим» окончанием работы НАМ. В обоих случаях говорят, что НАМ применuм к входному слову.

Однако может случиться и так, что НАМ никогда не остановится; это происходит, когда на каждом шаге есть применимая формула и эта формула обычная. Тогда говорят, что НАМ неприменим к входному слову. В этом случае ни о каком результате нет и речи.