Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 21 стр.

       где 100001 - a, 10000001 - b, 1000000001 - c, 100000000001 - d.
       Программа же будет представлена следующими строками:
       1) 1000001 10000001 1000001 10000001 101
        (q 0b → q 0 b R)
       2) 1000001 1000000001 1000001 1000000001 101
       (q 0c → q 0 c R)
       3) 1000001 100001 100000001 1000000001 101
       (q 0 a → q 1 c R)
    3) 100000001 100000000001 10000000001 100000000001 10001
       (q1d→q2dL).
    Рассмотрим еще один пример. Пусть на ленту универсальной машины Тьюринга
поступает слово, составленное из букв английского алфавита. Задача машины Тьюринга -
переставлять местами буквы n и o таким образом, чтобы сочетание on преобразовывалось в
no. Таким образом, после переработки входного слова в нем не должно остаться ни одного
буквосочетания on.
    Возьмем слово mnonnop, которое должно преобразоваться универсальной машиной
Тьюринга в новое слово mnnnoop.
    Пусть внешний алфавит универсальной машины Тьюринга состоит из символов A =
{0,1}, а внутренний алфавит Q = {q0, q1, q2, q3, qz }, где qz - заключительное
состояние. Разбивка входных символов на кодовые группы и сопоставление кодовых групп
исходным символам внешнего и внутреннего алфавитов осуществляется согласно
приведенной выше таблице кодирования.
    Тогда входное слово будет представлено следующим образом:
    100001 10000001 1000000001 10000001 10000001 1000000001 100000000001,
     где 100001 - m, 10000001 - n, 1000000001 - o, 100000000001 - p.
    Ниже представлены команды универсальной машины Тьюринга, которые будут
выполняться при обработке и преобразовании исходного слова. Напротив каждой команды
приводится входное слово таким, какое оно есть в момент начала выполнения данной
команды. Символ, на который указывает головка машины Тьюринга, показан как прописная
буква.

      q 0m → q 0m R     Mnonnop
      q 0n → q 0n R     mNonnop
      q 0o → q 1o R     mnOnnop
      q 1n → q 2o L     mnoNnop
      q 2o → q 0n R     mnOonop
      q 0o → q 1o R     mnnOnop
      q 1n → q 2o L     mnnoNop
      q 2o → q 0n R     mnnOoop
      q 0o → q 1o R     mnnnOop
      q 1o → q 0o R     mnnnoOp
      q 0p → q zp E     m n n n o o P.

   Программа же будет выглядеть так:

   1000001 100001 1000001 100001 101
   1000001 10000001 1000001 10000001 101
   1000001 1000000001 100000001 1000000001 101
   100000001 10000001 10000000001 1000000001 10001
   10000000001 1000000001 1000001 10000001 101
   1000001 1000000001 100000001 1000000001 101