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


             

и будем считать, что во


Выделим в алфавите ? специальный пустой символ a0 =
и будем считать, что во всех ячейках ленты, кроме конечного их числа, в начальный и во все последующие моменты находится пустой символ.

Будем говорить, что некоторый символ стирается, если он заменяется на пустой. Два слова из ?* будем считать равными, если они совпадают после отбрасывания всех пустых символов слева и справа. Например,
ab
c
=
ab
c = ab
c, но ab
c
abc.

Как и для конечных автоматов, программу P можно задавать с помощью таблицы размера n ? m, строки которой соответствуют состояниям из Q, а столбцы - символам из входного алфавита ?, в которой на пересечении строки qi и столбца aj стоит тройка qk al C - правая часть команды qi aj
qk al C.

Определение 9.2. Назовем конфигурацией м.Т.
в некоторый момент времени слово K= wл qi aj wп, где wл
?* - слово на ленте левее текушего положения головки, qi - внутреннее состояние в данный момент, aj- символ, обозреваемый головкой, wп
?* - слово на ленте правее текушего положения головки.

Будем считать, что слово wл aj wп содержит все значащие символы на ленте. Поэтому, с точностью до описанного выше равенства слов, конфигурация определена однозначно. В частности, если wл=?, т.е. пусто, то левее положения головки все ячейки пусты, а если wп=?, то правее положения головки все ячейки пусты.

Начальная конфигурация - это конфигурация вида q0w, т.е. в начальный момент времени головка в состоянии q0 обозревает первый символ входного слова w. { it Заключительная } конфигурация - это конфигурация вида w1 qf w2, в которой машина находится в заключительном состоянии qf .

Определение 9.3. Скажем, что конфигурация K= w1 qi aj w2 м.Т.
за один шаг (такт) переходит в конфигурацию
если в программе имеется команда qi aj
qk al C и при этом,

  • если С=Н, то w1'=w1, w2'=w2 и a{j'}=al;
  • если С=Л, то w1=w1' a, a{j'}=a, w2'=al w2 (если w1=?, / то w1' = ? и a{j'}=
    );
  • если С=П, то w2=aw2', a{j'}=a, w1'=w1 al (если w2=?, / то w2' = ? и a{j'}=
    ).


Как обычно, через
обозначим рефлексивное и транзитивное замыкание отношения
а
будет означать, что конфигурация K за n шагов переходит в K'. (Если из контекста ясно, о какой машине идет речь, то индекс
будем опускать).


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