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

Расчетно-графическая работа №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
 

 

 


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

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