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

         

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


Назовем заключительную конфигурацию стандартной, если в ней головка наблюдает первый значащий символ результата, который находится в 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-ой ячейки замена символов # на
      и удаление штриха:

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

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



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