Языки и трансляции. Мартыненко Б.К. - 91 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

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

Рубрика: 

90
6. δ([q
2
, B, B], A) = ([q
2
, B, B], A, L) для A∈ Γ \ {B, X}.
Машина двигается влево, пока не выходит на символ X. После этого
машина перейдет в состояние, которое, как мы предполагаем, существует в
множестве состояний Q, и возобновит другие свои действия.
6.2.5. Моделирование.
Пусть B — автомат, который с входной
цепочкой w последовательно проходит конфигурации C
1
, C
2
,..., C
n
.
Неформально, мы говорим, что автомат A моделирует автомат B, если
автомат A с входной цепочкой w проходит последовательно конфигурации,
представляющие C
1
, C
2
,..., C
n
.
Возможно, что автомат A будет входить в другие конфигурации в
промежутках между конфигурациями, представляющими конфигурации
автомата B.
Понятие моделирования полезно при доказательстве, что автомат одного
типа может распознавать язык, принимаемый автоматом некоторого другого
типа. Чтобы автомат A моделировал автомат B, он должен быть способен, во-
первых, по представлению конфигурации C
i
вычислять представление C
i +1
; во-
вторых, автомат A должен определять, является ли конфигурация C
i
автомата B
принимающей. В этом случае A тоже должен принимать его собственную
входную цепочку.
Попутно заметим, что для целей моделирования часто бывает удобно
представлять конфигурацию машины Тьюринга в виде αqXβ, где α и β
являются ленточными цепочками, X — символ ленты, q — состояние. В
конфигурации αqXβ состояние есть q, αXβ — непустая часть ленты, а X —
символ, сканируемый головкой ленты. Пример моделирования недетерминиро-
ванной машины Тьюринга с помощью детерминированной приводится в § 6.4.
6.2.6. Диагонализация
— другое полезное понятие. Оно может быть
использовано для того, чтобы показать, что существует язык, принимаемый
автоматом типа 2, который не принимается никаким автоматом типа
1.
Диагонализация характеризуется несколькими отличительными чертами.
а) Должно существовать кодирование всех автоматов типа 1, входные
символы которых выбираются из одного и того же алфавита Σ. Пример того,
как это кодирование может быть сделано, приводится в следующей главе.
б) Должен строиться автомат A типа 2 с входными цепочками из Σ
*
.
Входная цепочка автомата A трактуется как кодирование некоторого автомата
B типа 1 с его собственной входной цепочкой.
в) Автомат A должен моделировать автомат B и определять, принимает B
свою собственную входную цепочку или нет. Если автомат B принимает
входную цепочку, то автомат A не принимает, и наоборот.
г) Всегда истинно, что язык, принимаемый автоматом A типа 2, не
принимается
никаким автоматом типа 1. Действительно, предположим, что B
является таким автоматом типа 1, который принимает язык, принимаемый
автоматом A. Автомат B имеет кодирование w∈ Σ
*
. Предположим, что автомат
B принимает цепочку w. Тогда автомат A не принимает цепочку w, и наоборот.
В любом случае, автоматы A и B не могут принимать один и тот же язык.

Страницы