Теория алгоритмов и формальных языков. Мелихов А.Н - 45 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

Составители: 

Рубрика: 

Теорема 2.3. Если МТ Z с начальным состоянием q
0
применима к
входному слову n, то это эквивалентно тому, что в полутуэвской системе П с
аксиомой
hnhq
0
выводима формула hsh.
При доказательстве теоремы 2.3 ограничимся только доказательством
того, что, если ТМ Z применима к n, то из этого следует, что в полутуэвской
системе П выводима формула hsh. Обратное доказательство проводить не
будем.
Для этого покажем, как по командам МТ Z построить полутуэвскую
систему П. Алфавит системы П
образуется объединением входного алфавита
состояний МТ Z и маркера h. Аксиомой системы является начальная
ситуация МТ Z
nq
0
с маркерами h слева и справа, т.е. hnhq
0
. Команде МТ Z
lkji
qxxq в системе П сопоставляется подстановка QxPqQxPq
klji
→ , которая
обеспечивает переход от конфигурации, которая имела место в МТ Z до
применения команды, к конфигурации, в которую переходит МТ Z после
применения команды. Здесь Р и Q - некоторые слова (контекст). Команде
lji
zqxq соответствует подстановка QxxPqQxqPx
jkljik
→ . Команде
lji
lqxq
соответствует подстановка
QxqPxQxPq
lljji
→ .
Кроме того, введем в систему П дополнительные подстановки, которые
не соответствуют никаким командам МТ Z и применяются только тогда,
когда МТ Z переходит в заключительную конфигурацию и останавливается
(в этом случае МТ Z встретилась с ситуацией q
i
x
j
, которой нет ни в одной
команде или выполнила команду
0
sqxq
ji
). Подстановки QhxhPqQhxhPq
jiji
→ ,
которые для всех пар (q
i
x
j
), на встречающихся в левых частях команд МТ Z,
заменяют символ состояния q
i
маркером q. Подстановки
hPqQhQhhPqx
j
→
,
стирающие все символы (кроме h) справа от q. Подстановки
hPshhPqh →
вводят символ s слева от правого h. Подстановки
hPshshhPx
j
→ стирают все
символы между левым h и s. И, наконец, подстановки
hshshhx →
0
, которые
перемещают левый маркер h в позицию, предшествующую символу s.

Страницы