Введение в схемы, автоматы и алгоритмы

Стандартная заключительная конфигурация

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

Лемма 9.1.Для всякой м.Т.

можно построить эквивалентную м.Т. у которой все заключительные конфигурации стандартны.

Доказательство. Пусть

Определим по ней м.Т. , которая удовлетворяет требованиям леммы. Положим ?' = ? { a' | a ?} { #}, где # - новый символ. работает следующим образом.

1. Отмечает символ в первой ячейке штрихом и переходит в начальное состояние
   
2. Далее работает как
   
   но сохраняет штрих в первой ячейке и вместо пустого символа
   
   записывает #. Для этого для каждой команды qiaj
   
   qk alC из P'
3. в P' добавляется ее дубликат qiaj'
   
   qk al'C, в правых частях команд символ
   
   всюду заменяется на # и для каждой команды вида qi
   
   
   qk al C в P' добавляется команда qi #
   
   qk al C . После завершения этого этапа все посещенные в процессе работы головкой
   
   ячейки составляет непрерывный отрезок, не содержащий пустых символов.
4. Далее
   
   стирает ненужные символы # слева и справа от блока ячеек, содержащего первую ячейку и все ячейки с символами результата, и переходит в одну из трех следующих конфигураций:
   
   где w - результат работы { cal M} (с заменой символов
   
   внутри w на #) и w1aw2 = w.
5. Сдвигает в нужном направлении результат, совмещая его начало с ячейкой, помеченной штрихом, заменяет все # внутри w на
   
   , снимает штрих в 1-ой ячейке и останавливается. Например, для K1 это достигается с помощью следующих команд (мы предполагаем, что ни одно из используемых ниже состояний qл, q1, p, p1, p2, p3, pa, pa' (a
   
   ?
   
   { #}) не входит в Q):
   • поиск левого конца w: qл a
     
     qлaП (a
     
     {#', #}); qлa
     
     q1a'П (a
     
     ?) (отметили первый символ w), qл
     
     
     p3
     
     Л; (результат пуст);
   • поиск правого конца w: q1 a
     
     q1aП (a
     
     ?
     
     { #} ), q1
     
     
     p
     
     Л (в состоянии p наблюдает последний символ w);
   • сдвиг результата на 1 ячейку влево: pa
     
     pa
     
     Л; pa b
     
     pb aЛ; pa b'
     
     pb'aП; pb' #
     
     p1 b'П;
   • возврат к правому концу и переход к следующему сдвигу: p1 a
     
     p1aП (a
     
     
     ); p1
     
     
     p
     
     Л;
   • при сдвиге до 1-ой ячейки замена символов # на
     
     и удаление штриха:
     

   Из построения непосредственно следует, что м.Т.

   
   удовлетворяет требованиям леммы.

Содержание раздела

---