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



             

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


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

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

{\cal M}\
можно построить эквивалентную м.Т.
{\cal M}^\prime,
у которой все заключительные конфигурации стандартны.

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

{\cal M} = <Q, \Sigma, P,q_0, q_f>.
Определим по ней м.Т.
\ {\cal M}^\prime = <Q^\prime, \Sigma^\prime, P^\prime,q_0^\prime, q_f^\prime>
, которая удовлетворяет требованиям леммы. Положим ?' = ?
{ a' | a
?}
{ #}, где # - новый символ.
{\cal M}^\prime\
работает следующим образом.

  1. Отмечает символ в первой ячейке штрихом и переходит в начальное состояние
    {\cal M}:\ \ q_0^\prime a \rightarrow q_0 a^\prime \textit{Н}.
  2. Далее работает как
    {\cal M},\
    но сохраняет штрих в первой ячейке и вместо пустого символа
    записывает #. Для этого для каждой команды qiaj
    qk alC из P'
  3. в P' добавляется ее дубликат qiaj'
    qk al'C, в правых частях команд символ
    всюду заменяется на # и для каждой команды вида qi
    qk al C в P' добавляется команда qi #
    qk al C . После завершения этого этапа все посещенные в процессе работы головкой
    {\cal M}\
    ячейки составляет непрерывный отрезок, не содержащий пустых символов.
  4. Далее
    {\cal M}^\prime\
    стирает ненужные символы # слева и справа от блока ячеек, содержащего первую ячейку и все ячейки с символами результата, и переходит в одну из трех следующих конфигураций:
    K_1= q_\textit{л} \#^\prime \#\ldots \# w\wedge,\ \ K_2=\wedge q_\textit{п} w \# \ldots \#\#^\prime, \ \ K_3 =\wedge q_\textit{н} w_1 a^\prime w_2\wedge,
    где 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-ой ячейки замена символов # на
      \wedge
      и удаление штриха:
      p^{a\prime} \#^\prime \rightarrow p_2 a^\prime \textit{Н}; p_2 b \rightarrow p_2 b \textit{П};\\ p_2 \wedge \rightarrow p_3 \wedge \textit{Л};\\ p_3 \# \rightarrow p_3 \wedge \textit{Л}; \ \ p_3 b \rightarrow p_3 b \textit{П}\ (b \neq \#, b \neq a^\prime) ; \ \ p_3 a^\prime \rightarrow q_f^\prime a \textit{Н}.

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

    {\cal M}^\prime\
    удовлетворяет требованиям леммы.




Содержание  Назад  Вперед