Л.С. Корухова, М.Р. Шура-Бура - Введение в алгоритрмы, страница 6

НОРМАЛЬНЫЕ АЛГОРИТМЫ МАРКОВАВ 1954 году русский математик А.А.Марков предложил новый подход к формализациипонятия алгоритма. В отличие от подхода Тьюринга, доводящего простоту описываемыхопераций до замены символов, А.А.Марков предложил использовать замену слов,включив в шаг алгоритма процедуру выбора реализуемой замены.Для дальнейшего изложения нам потребуется знакомство с некоторыми терминами ипонятиями, играющими заметную роль не только в теории алгоритмов.Пусть А = { a 1 , a 2 , ... , a p } - конечный алфавит.Пусть u = a i1 ...aik и v = a j1...ajl - слова из A*. Говорят, что слово w = a i1...

aik aj1...ajlполучено конкатенацией (сцеплением) слов u и v (обозначается uv),а также, что слово wявляется конкатенацией этих слов. Очевидным образом конкатенация обобщается наслучай, когда u или v оказываются пустыми словами. Операция конкатенацииассоциативна. Следовательно, однозначно определяется конкатенацияuvw = (uv)w = u(vw) и конкатенация u1u2...u m.Говорят, что имеет место вхождение слова v в слово w, если w = u1vu2.

При этом словаu1 и u2 называются, соответственно, левым и правым контекстом вхождения. Вхожденияслова v в w могут различаться контекстами. Среди таких вхождений вхождение сминимальной длиной левого контекста называется левым или первым вхождением v в w.Замена в слове w = u1vu2 слова v на слово v', т.е. получение слова w' = u1v'u2,называется подстановкой, определяемой парой (v, v'). Пара (v, v''), определяющая18операцию подстановки называется формулой или правилом подстановки и длянаглядности часто изображается в виде:v  v'Как v, так и v', могут быть пустыми словами. Формула подстановки v  v' применима кслову w, если имеет место вхождение слова v в w.

Подстановка с пустым левым словомвсегда применима.Алгоритм, названный А.А.Марковым нормальным, сводится к ряду подстановок,определяемых заданием конечной последовательности определяющих формулподстановкиv1  v'1.....v m  v'm ,некоторые из них заранее выделены, как играющие особую роль в завершении алгоритма.Выделенные формулы подстановки называются заключительными и обычно отмечаютсядополнительным значком при стрелке , например:  или * .В нормальных алгоритмах всегда идет речь о подстановках, связанных с заменойпервого вхождения левого слова формулы подстановки.

В процессе выполнениянормального алгоритма исходное слово преобразуется применением заданных формулподстановки. На каждом шаге исполнения нормального алгоритма либо осуществляетсяодна из заданных подстановок (а именно - первая применимая подстановка), либоалгоритм завершается, если ни одна из этих подстановок неприменима. Алгоритмзавершается и в случае выполнения на очередном шаге одной из заключительныхподстановок.

Слово, полученное в результате последней из выполненных подстановок,считается результатом работы алгоритма.Описанные алгоритмы, в которых, как исходные слова, так и слова в подстановках,принадлежат A*, называются нормальными алгоритмами в алфавите А. А. А. Марковпредложил рассматривать более широкий класс алгоритмов, допустив для задания пар,определяющих подстановки, использование алфавитов, являющихся расширениемалфавита А, употребляемого для задания исходных слов. Такие алгоритмы А. А. Марковназвал нормальными алгоритмами над алфавитом А. Слова, получаемые на отдельныхшагах таких алгоритмов, могут и не принадлежать A*. А.

А. Марковым быласформулирована гипотеза, названная им принципом нормализации, заменяющая гипотезуТьюринга:ПРИМЕРПостроим нормальный алгоритм, который "инвертирует" любое слово, заданное валфавите А = { a, b }, т.е. заменяет в заданном слове все символы a на символы b и все bна a.+a  b++b  a++ +Работа алгоритма начинается с приписывания к исходному слову слевадополнительного символа +. Такое приписывание обеспечивается правилом подстановки,которое применимо к любому слову. Но поскольку оно стоит последним, то применяетсятолько один раз, когда другие правила еще не применимы.

Далее символ + "перегоняется"в конец слова с заменой стоящей за ним буквы на "противоположную". Когда +19оказывается в конце слова, применимо третье правило подстановки, которое "стирает"символ + и прекращает выполнение алгоритма.Любой алгоритм, отображающий слова из A*, где А - конечный алфавит, эквивалентеннормальному алгоритму над алфавитом А. Как и гипотеза Тьюринга, принципнормализации А.А.Маркова недоказуем.

Как гипотеза Тьюринга, так и принципнормализации, являются формальными определениями алгоритма, и важнымобстоятельством для их обоснования является эквивалентность этих определений. Дляустановления их эквивалентности достаточно доказать:I) Алгоритм, выполняемый каждой машиной Тьюринга, эквивалентен некоторомунормальному алгоритму над внешним алфавитом машины.II) Каждый нормальный алгоритм над алфавитом А эквивалентен алгоритму,выполняемому некоторой машиной ТьюрингаДоказательство утверждения I) оказывается совсем простым. Нормальный алгоритм,эквивалентный заданной машине Тьюринга с внешним алфавитом А ={ a 1 , a 2 , ...

, a p } ивнутренним алфавитом Q = {q 0,...q n,q s}, задается подстановками, определяемымиследующим образом. Для каждой клетки (qi, a j) таблицы переходов, в которой записанатройка (a j', R, q i'), т.е. предписывается переход управляющей головки к рассмотрениюследующей (правой) ячейки ленты, вводим подстановку q i a j  aj'q i' , если q i'≠ qs, илизаключительную подстановку qia j  aj', если q i' = q s. Если же в клетке (q i,a j) записанатройка (a j',L,q i'), то управляющая головка должна перейти к рассмотрению предыдущей(левой) ячейки ленты. В этом случае для всех a k ∈ A при q i'≠ q s вводим группуподстановок a k qi a j  q i'a k aj', либо при q i' = q s - группу заключительных подстановокa k qi a j  a k aj'. К выписанным подстановкам добавим подстановку  q 0, поместив ее вконце всех остальных, упорядочение которых произвольно.Легко видеть, что нормальный алгоритм, определенный введенными подстановками,начинается с приписывания перед исходным словом символа q 0.Такое приписываниеобеспечивается формулой подстановки  q 0.

Далее выполняется нормальный алгоритм,который полностью соответствует работе заданной машины Тьюринга и завершается темже результатом.Доказательство положения II требует преодоления некоторых технических трудностей.Это связано с тем, что операции подстановки, выполняемые в нормальном алгоритме,существенно сложнее элементарных шагов машины Тьюринга и каждый шаг нормальногоалгоритма требует порой сложной серии различных тактов машины Тьюринга. Длякаждого нормального алгоритма, заданного конечной последовательностью подстановокv i  v i' , i = 1,...,n,мы построим машину Тьюринга, выполняющую алгоритм, эквивалентный заданному.Через a(i,j) будем обозначать символы, входящие в слова v i - левые части подстановокv i  v i' , определяющих нормальный алгоритм. Пусть v i= a(i,1) a(i,2) ... a(i,m i),где i= 1,2,...,n-1 и m i = | v i|.

Заметим, что для i < n можно считать, что v i ≠ λ, так какподстановки, следующие за подстановкой с пустым словом в ее левой части, не имеютникакого значения в выполнении нормального алгоритма и могут быть отброшены. Еслиv i ≠ λ, то считаем, что v n= a(n,1)...a(n,m n). Через b(i,j) будем обозначать символы,входящие в слова v i' - правые части подстановок, определяющих нормальный алгоритм.При этом v i' = b(i,1) b(i,2) ... b(i,n i), i= 1,2,...,n.

Если n i=0, то в правой части i-той формулыподстановки - пустая цепочка (v i'= λ).Соотношение длин цепочек v i и v i' в соответствующей подстановке задается формулойn i = m i + d i, где d i может принимать положительные, отрицательные, и нулевыезначения. Рассмотрим далее вариант реализации подстановок, для которых d i >= 0. При20реализации подстановок, правая часть которых "короче" левой ( d i< 0), не возникаетновых принципиальных трудностей. Предлагаем рассмотреть этот вариантсамостоятельно.Для определения вхождения левых частей подстановок, определяющих заданныйнормальный алгоритм, в управляющей головке соответствующей машины Тьюрингапредусмотрим следующие состояния:1). q(i,j) для j =1,..,m i и i = 1,2,...,n-1, и i = n, если m n= 0Эти состояния будут соответствовать проверке наличия символа a(i,j) вобозреваемой головкой ячейке ленты машины Тьюринга.

Состояние q(1,1) отождествим сначальным состоянием q 0.2). q(i,j)' и q(i)' - состояния, обеспечивающие возврат управляющей головкидля продолжения поиска вхождения или его завершения3). q(i,m i+1) = p(i,d i), i= 1,2,...,n - состояния, соответствующие установлениювхождения v i и переходу к реализации i-ой подстановки4). q(n+1,1) = q s - заключительное состояние машины ТьюрингаЧерез IZ обозначим множество номеров подстановок, которые нумеруютзаключительные подстановки нормального алгоритма, а q Z - соответствующие такимподстановкам состояния.

Если машина оказывается в состоянии qZ, то нужно перевестиуправляющую головку в начало слова и закончить работу, т.е. перейти в состояниеостанова q s.Для описания таблицы переходов конструируемой машины Тьюринга Т N мы будемописывать клетки таблицы соотношениями вида :[ q, a] : [ a', X, q'],где слева в квадратных скобках обозначена клетка таблицы переходов символами еестроки q и столбца а, справа же -.содержимое этой клетки. Здесь а' - записываемый вобозреваемую ячейку символ, X - один из символов указателей R и L, перехода головки крассмотрению следующей ячейки ленты, а q' - состояние, в которое переходитуправляющая головка. Клетки таблицы переходов, обеспечивающие обнаружениесоответствующих вхождений, зададим следующими формулами1.