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


Основные определения - часть 2


Выделим в алфавите ? специальный пустой символ 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. Назовем конфигурацией м.Т.

{\cal M }\
в некоторый момент времени слово 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 м.Т.

{\cal M }
за один шаг (такт) переходит в конфигурацию
K^\prime= w_1^\prime q_k a_{j^\prime} w_2^\prime\ (K \vdash_{\cal M } K^\prime),
если в программе имеется команда 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'}=
    ).

Как обычно, через

\vdash^*_{\cal M }
обозначим рефлексивное и транзитивное замыкание отношения
\vdash_{\cal M },\
а
K \vdash^n_{\cal M } K^\prime
будет означать, что конфигурация K за n шагов переходит в K'. (Если из контекста ясно, о какой машине идет речь, то индекс
{\cal M }
будем опускать).




- Начало -  - Назад -  - Вперед -



Книжный магазин