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

Подождите немного. Документ загружается.

ности языками, принимаемыми недетерминированными МП-автоматами при

пустом магазине, а затем, что языки, принимаемые при пустом магазине, совпа-

дают с классом КС-языков.

Теорема 5.1. Язык L = N(M

) для некоторого недетерминированного мага-

зинного автомата M

тогда и только тогда, когда L = Т(M

) для некоторого

магазинного автомата M

Доказательство.

I. Необходимость. Пусть M

= (Q, Σ, Γ, δ, q

, Z

, ∅) — недетерминированный

pda, такой, что L = N(M

). Положим

= (Q ∪ {

, q

}, Σ, Γ∪{X}, δ

′

, X, {q

}),

где δ

′

определяется следующим образом:

1) δ

′

(

ε, X)={( q

, Z

X)};

2) δ

′

(q, a, Z) = δ( q, a, Z) для всех q ∈Q, a ∈(Σ ∪ {ε}) и Z ∈Γ;

3) δ

′

(q, ε, X) = {(q

, ε)} для всех q∈Q.

Правило 1 воспроизводит начальную конфигурацию автомата M

. При этом

начальный символ магазина X остается в качестве своеобразного маркера дна

магазина до тех пор, пока он не будет удален последним движением автомата

. Выше этого маркера при последующих движениях, повторяющих движения

pda M

, всегда будут находиться только магазинные символы автомата M

. Это

обеспечивается правилом 2. Когда же будет воспроизведено последнее движе-

ние pda M

, опустошающее его магазин, на вершине магазина автомата M

поя-

вится маркер дна. В этот момент автомат M

посредством правила 3

переводится

в конечное состояние, тем самым сигнализируя прием входной цепочки.

Заметим, что движение по правилу 3 стирает символ магазина X, но могло

бы записать вместо него любую магазинную цепочку.

I.1. Докажем, сначала, что если x

∈N(M

), то x ∈T(M

Пусть

x ∈N(M

), т.е. (q

, x, Z

) (q, ε, ε). Посмотрим, какие движения будет

совершать автомат M

, имея на входе цепочку символов x. Согласно правилу 1

(

x, X) ( q

, x, Z

X). Далее согласно правилу 2 автомат M

, повторяя движе-

ния автомата M

осуществляет переход (q

, x, Z

X) (q, ε, X). Наконец, по прави-

лу

3 имеем последнее движение: (q, ε, X)

, ε, ε). Таким образом, x ∈T(M

I.2. Теперь докажем, что если x

∈T(M

) , то x ∈N(M

Пусть

x ∈T(M

), т.е. (

x, X) (q

, ε, γ) для некоторой цепочки γ∈

(

Γ∪{X})

, причем по построению автомата M

γ = ε. Выделив здесь первый шаг

явным образом, имеем (

, x, X)

, x, Z

X) (q

, ε, ε). Заключительная кон-

фигурация (q

, ε, ε) достижима лишь посредством ε-движения благодаря прави-

лу 3 в случае, когда на вершине магазина находится X. Следовательно, предпо-

следняя конфигурация должна иметь вид (q

, ε, X). Итак, все движения выстраи-

ваются в следующую последовательность конфигураций:

(

, x, X)

, x, Z

X) (q, ε, X) (q

, ε, ε).

Но на главном участке (q

, x, Z

(q, ε, X) автомат M

просто повторяет дви-

жения автомата M

. Поэтому (q

, x, Z

)

(q, ε, ε) и x ∈N(M

Из рассуждений, проведенных в пп.I.1 и I.2 следует, что T(M

)=N(M

II.

Достаточность. Пусть M

= (Q, Σ, Γ, δ, q

, Z

, F) — недетерминирован-

ный

pda, такой, что L = T(M

). Положим

= (Q ∪ {

, q

}, Σ, Γ∪{X}, δ

′

, X,

∅),

где δ

′

определяется следующим образом:

1) δ

′

(

ε, X) = {(q

, Z

X)};

2) δ

′

(q, a, Z) = δ(q, a, Z) для всех q ∈Q, a ∈(Σ∪{ε}) и Z ∈Γ;

3) δ

′

(q, ε, Z) = {(q

, ε)} для всех q ∈F и Z ∈Γ∪{X};

4) δ

′

, ε, Z) = {(q

, ε)} для всех Z ∈Γ∪{X}.

Правило 1 воспроизводит начальную конфигурацию автомата M

. При

этом начальный символ магазина X остается в качестве своеобразного маркера

дна магазина до тех пор, пока он не будет удален последним движением

автомата M

. Выше этого маркера при последующих движениях, повторяющих

движения автомата M

, всегда будут находиться только магазинные символы

автомата M

. Это обеспечивается правилом 2. Если когда-либо pda M

входит в

конечное состояние, то правила 3 и 4 позволяют pda M

выбирать переход в

состояние q

и, не продвигаясь по входу, очищать магазин, тем самым принимая

вход или продолжая моделировать движения автомата M

Следует заметить, что автомат M

может на неправильном входе

опустошить свой магазин, не заходя в конечное состояние и, следовательно, не

принимая входную цепочку. Чтобы неправильные цепочки не принимались pda

, и введено его собственное особое дно в виде символа X, чтобы он,

воспроизводя эти же движения, тоже не опустошил свой магазин и таким

образом принял бы неправильную цепочку.

Остается убедиться в том, что N(M

) = T(M

II.1. Докажем, сначала, что если x

∈N(M

), то x ∈T(M

Если

x ∈N(M

), то по определению (

x, X) (q, ε, ε) при некотором

q ∈Q ∪ {

}. Рассмотрим подробнее эти движения. Согласно правилу 1 имеем

(

x, X) (q

, x, Z

X). Далее (q

, x, Z

(q, ε, ε) при некотором q ∈Q ∪{

Удалить X из магазина согласно построению автомата M

возможно только по-

средством правил 3 или 4, причем правило 4 применимо только после того, как

применено правило 3. В свою очередь, правило 3 применимо только в том слу-

чае, если автомат M

достиг одного

из своих конечных состояний. C этого мо-

мента происходят только

ε-движения, стирающие содержимое магазина. С уче-

том этого имеем

(

x, X) (q

, x, Z

(q, ε, γX)

, ε, γ’)

, ε, ε).

Здесь q

∈F, γ∈Γ

, γ’∈(Γ∪{X})

, причем если γ’= ε, то перехода (q

, ε, γ’)

, ε, ε) фактически нет.

Но мы знаем, что согласно правилу 2 автомат M

на главном участке просто

повторяет движения автомата M

, x, Z

(q, ε, γX), т.е. имеет место пере-

ход (q

, x, Z

(q, ε, γX), где q ∈F. Следовательно, x ∈T(M

II.2. Теперь докажем, что если x

∈T(M

), то x ∈N(M

Пусть

x ∈T(M

), т.е. (q

, x, Z

) (q, ε, γ), где q ∈F, γ∈Γ

. Посмотрим, как будет

действовать автомат M

на том же входе. Согласно правилу 1 имеем (

, x, X)

, x, Z

X). Затем согласно правилу 2 воспроизводятся указанные ранее движе-

ния автомата M

, т.е. имеем (

x, X) (q

, x, Z

(q, ε, γX), где q ∈F, γ∈Γ

Далее согласно правилам 3 и 4 имеем (q,

ε, γX)

( q

, ε, γ’)

, ε, ε), где

γ’(Γ∪{X})

. Если γ’= ε, то последнего перехода фактически нет.

Итак,

существует последовательность конфигураций:

(

x, X) (q

, x, Z

(q, ε, γX)

( q

, ε, γ’)

( q

, ε, ε),

означающая, что x

∈N(M

Из рассуждений. проведенных в пп.II.1 и II.2 следует, что N(M

) = T(M

Заключение теоремы следует из доказанных утверждений I и II.

Теорема 5.2. Если L — контекстно-свободный язык, то существует неде-

терминированный магазинный автомат M, такой, что L = N(M).

Доказательство.

Пусть G =(V

, V

, P, S) — контекстно-свободная грамма-

тика

в нормальной форме Грейбах, и L = L(G). Мы предполагаем, что ε∉L(G).

Пусть

α, где x ∈V

, причем α = Aβ, A ∈V

, β∈V

, либо α = ε. Цепочка x

называется закрытой, а

α — открытой частью сентенциальной формы xα.

Построим недетерминированный pda M таким образом, чтобы в его магазине

воспроизводились последовательности сентенциальных форм, составляющих

левосторонние выводы в грамматике G, вернее, открытые части таких форм.

Для этого положим M =({q}, V

, V

, δ, q, S, ∅), где (q, γ) ∈δ(q, a, A), если суще-

ствует правило A

→ aγ∈P. Очевидно, что в магазине pda M всегда находится

нетерминальная цепочка, причем на вершине — символ, подлежащий замене на

текущем шаге левостороннего вывода.

Чтобы показать, что L(G) = N(M), достаточно доказать, что A

α тогда и

только тогда, когда (q, x, A)

(q,

ε, α) для любых x ∈V

, A ∈V

, α∈V

. Утвер-

ждение теоремы последует как частный случай этого вспомогательного утвер-

ждения при A = S,

α = ε: S

x тогда и только тогда, когда (q, x, S)

(q,

ε, ε).

Заметим, что pda M не совершает

ε-движений.

I. Индукцией

по длине вывода l покажем, что если A

xα, где x ∈V

, α∈V

то

(q, x, A)

(q, ε, α).

База. Пусть l =1. Имеем A

xα. Это значит, что существует правило

→ xα∈P, где x ∈V

, α∈V

. Одновременно по построению автомата M мы

имеем (q,

α) ∈δ(q, x, A), а тогда (q, x, A)

(q, ε, α).

Индукционная гипотеза. Предположим, что для всех l

≤ n (n ≥ 1), если A

xα, то (q, x, A)

(q, ε, α).

Индукционный переход. Докажем это утверждение для l = n +1. Пусть A

γ yaβγ = xα — левосторонний вывод длиной n +1. В нем x = ya,

α = βγ и B → aβ∈P. По построению автомата M существует (q, β) ∈δ(q, a, B). В

соответствии с

индукционной гипотезой и с учетом этого последнего обстоя-

тельства можем написать: (q, x, A)=(q, ya, A)

(q, a, Bγ)

(q,

ε, βγ)=(q, ε, α).

II. Теперь индукцией

по числу l движений автомата M покажем, что если (q,

x, A)

(q, ε, α), где x ∈V

, α∈V

, то A

α.

База. Пусть l =1. Имеем (q,

x, A)

(q, ε, α), где x ∈V

, α∈V

. Поскольку pda

M не совершает

ε-движений, то это движение имеет место благодаря тому, что (x,

α) ∈δ(q, x, A), где x ∈V

. Но это обусловлено тем, что существует правило

→xα∈P, с помощью которого получаем требуемый вывод A

xα.

Индукционная гипотеза. Предположим, что утверждение выполняется

для всех l

≤ n (n ≥ 1).

Индукционный переход. Докажем это утверждение для l = n +1. Пусть

(q,

x, A)=(q, ya, A)

(q, a, Bγ)

(q, ε, βγ)=(q, ε, α), где x = ya, α = βγ. Послед-

нее из этих движений подразумевает, что (q,

β) ∈δ(q, a, B), где a ∈V

, а это обу-

словлено

существованием правила B → aβ∈P. Учитывая следствие индукцион-

ной гипотезы из (q,

ya, A)

(q,

a, Bγ) и упомянутое правило, мы можем напи-

сать:

yBγ yaβzγ = xα.

Из рассуждений, проведенных в пп. I и II, при A = S и

α = ε получаем утвер-

ждение теоремы. Что и требовалось доказать.

Теорема 5.3. Если M — недетерминированный магазинный автомат, и L =

N(M), то L — контекстно-свободный язык.

Доказательство.

Пусть M =(Q, Σ, Γ, δ, q

, Z

, ∅) — недетерминированный

pda, такой, что L = N(M).

Построим cfg G, левосторонние выводы в которой моделируют движения

pda M. В частности, нетерминалы, которые появляются в сентенциальных фор-

мах на любом шаге левостороннего вывода в грамматике G, соответствуют сим-

волам в магазине автомата M в момент, когда он уже просмотрел такую же

часть входной цепочки, какую грамматика уже породила.

Положим G =(V

, V

, P, S), где V

={S} ∪ {[qAp] | q, p ∈Q; A ∈Γ}; V

= Σ;

P =

{(1) S → [q

q] |q ∈Q} ∪

{(2) [qAp] → a [q

][q

]...[q

m + 1

] |q, qz

∈Q (i =1, 2,..., m +1);

p= q

m + 1

; a ∈Σ∪{ε}; A, B

∈Γ (j =1, 2,..., m); (q

, B

...B

) ∈δ(q, a , A)}.

Отметим, что если

, ε) ∈δ(q, a , A), то m =0, q

= p и правило вида 2 имеет

вид [qAp]

→ a.

Чтобы показать, что L(G)=N(M), мы сначала докажем вспомогательное

утверждение: [qAp]

x тогда и только тогда, когда (q,

x, A)

(p, ε, ε).

I. Индукцией по числу l движений pda M покажем, что если (q,

x, A)

(p,

ε, ε), то [qAp]

База. Пусть l =1. Имеем (q,

x, A)

(p,

ε, ε). Это движение обусловлено тем,

что (p,

ε) ∈δ(q, x, A), где x ∈Σ∪{ε}. Соответственно по способу построения

грамматики G существует правило [qAp]

→ x, при помощи которого [qAp]

Индукционная гипотеза. Предположим, что утверждение выполняется

для всех значений l

≤ n (n ≥ 1).

Индукционный переход.

Докажем, что утверждение выполняется для

l = n +1. Пусть (q, x, A)=(q, ax

... x

, A)

, x

... x

, B

...B

)

(p, ε, ε).

Здесь

x = ax

... x

, a ∈Σ∪{ε}, x

∈Σ

, причем (q

, x

, B

)

i + 1

, ε, ε), i =

2,..., m, q

m + 1

= p.

Поясним, что в этой последовательности переходов явно показано первое

движение,

которое может использовать входной символ a, с которого начинается

входная цепочка x, либо оно может быть

ε-движением. Каждая из подцепочек x

есть та часть цепочки x, которую автомат просматривает с момента, когда он

оказывается в состоянии q

с символом B

на вершине магазина, до того момен-

та, когда вершина магазина впервые опустится на один символ ниже этой пози-

ции B

Очевидно,

что первое движение обусловлено тем, что (q

, B

... B

) ∈

δ(q, a, A), и, как следствие этого, существует правило грамматики вида

[qAp]

→a [q

][q

]...[q

m + 1

]

с нетерминалами, связанными с состояниями и магазинными символами,

участвующими в указанных конфигурациях. С другой стороны, применение ин-

дукционной гипотезы к переходу (q

, x

, B

)

i + 1

, ε, ε), где l

≤ n, дает основание

заключить, что [q

i + 1

]

, i = 1, 2,..., m, q

m + 1

= p.

С помощью упомянутых правила и частичных выводов можно выстроить

требуемый вывод:

[qAp]

a[q

][q

]...[q

m + 1

]

]...[q

m + 1

]

...

... x

= x.

II. Индукцией

по длине вывода l покажем, что если [qAp]

x, то (q,

x, A)

(p,

ε, ε).

База. Пусть

l =1. Имеем [qAp]

x. Очевидно, что на этом единственном

шаге применено правило [qAp] → x. По способу построения cfg G x ∈Σ∪{ε}.

Такое правило существует, если только (p,

ε) ∈δ(q, x, A). А тогда (q, x, A)

(p,

ε, ε).

Индукционная гипотеза. Предположим, что утверждение выполняется

для всех значений l

≤ n (n ≥ 1).

Индукционный переход.

Докажем, что утверждение выполняется для

l = n +1. Пусть [qAp] a[q

][q

]...[q

m + 1

]

... x

= x. Очевидно,

что существует

правило [qAp] → a [q

][q

]...[q

m + 1

] ∈P, использован-

ное на первом

шаге вывода, в котором q

m+1

= p, и частичные выводы [q

i + 1

]

где

≤ n, i = 1, 2,..., m. Из существования такого правила следует, что

, B

...B

) ∈δ(q, a, A). Из частичных выводов в соответствии с индукционной

гипотезой вытекает, что (q

, x

, B

)

i + 1

, ε, ε), i = 1, 2,..., m, q

m + 1

= p. Следова-

тельно, существует последовательность конфигураций:

(q, x, A) = (q, ax

...x

, A)

, x

...x

, B

... B

)

, x

... x

...B

)

...

(p,

ε, ε).

Итак, из рассуждений, проведенных в пп. I и II, следует справедливость

вспомогательного утверждения: [qAp]

тогда и только тогда, когда (q, x, A)

(p,

ε, ε). В частности, при q = q

и A = Z

x тогда и только тогда, когда

, x, Z

)

(p, ε, ε).

Остается вспомнить, что существуют правила вида S

→ [ q

q] для любых

∈Q, в частности для q = p; тогда, пристраивая новое начало к выводу, получа-

ем справедливость следующего утверждения: S

x тогда и только то-

гда,

когда (q

, x, Z

)

(p, ε, ε), или, что то же самое, L(G)=N(M). Что и требова-

лось доказать.

Теоремы 5.1, 5.2 и 5.3 можно подытожить: следующие три утверждения яв-

ляются эквивалентными:

1) L — cfl;

2) L = N(M

) для некоторого pda M

;

3) L = T(M

) для некоторого pda M

Пример 5.3. Пусть pda M = ({q

, q

}, {0, 1}, {X, Z

}, δ, q

, Z

0 ,

∅),

где

δ= { (1) δ(q

, 0, Z

)={(q

, XZ

)}, (4) δ(q

, 1, X )={(q

, ε)},

(2)

δ(q

, 0, X )={(q

, XX)}, (5) δ(q

, ε, X )={(q

, ε)},

(3)

δ(q

, 1, X )={(q

, ε)}, (6) δ(q

, ε, Z

)={(q

, ε)}}.

Нетрудно сообразить, что N(M) = {0

n ≥ m}.

Построим cfg G =(V

, V

, P, S), порождающую язык N(M), положив

= {S, [q

], [q

]},

= {0, 1}.

Для экономии времени при построении правил грамматики следует учесть,

что некоторые нетерминалы не участвуют ни в каких выводах, начинающихся с

символа S. Поэтому мы должны начать с построения правил для S, затем по-

строить правила для тех нетерминалов, которые встречаются в правых частях

уже построенных правил.

Правилами для S являются: S

→ [q

] и S → [q

Затем, исходя из правила 1 в определении

δ, мы добавим правила для нетер-

минала [ q

] → 0[q

][q

] → 0[q

][q

Так как в правых частях построенных правил появился нетерминал [q

],мы

должны построить правила для него, опять исходя из того же правила 1:

] → 0[q

][q

] → 0[q

][q

Аналогично, исходя из правила 2 в определении

δ, получаем следующие пра-

вила грамматики:

] → 0[q

][q

] → 0[q

][q

] → 0[q

][q

] → 0[q

][q

Исходя из правил 3–6 в определении

δ, получаем следующие правила грамма-

тики:

] → 1, [q

] →ε, [q

] →ε.

Заметим, что нет никаких правил для нетерминалов [q

] и [q

]. Соот-

ветственно правила, в правых частях которых встречаются эти два нетерминала,

бесполезны и могут быть отброшены. Кроме того, легко заметить, что из нетер-

миналов [q

] и[q

] не выводится ни одной терминальной цепочки. По-

этому правила с их участием могут быть отброшены.

Окончательно получаем следующее множество правил приведенной

грамматики:

(1) S

→ [q

] , (4) [q

] → 1,

(2) [q

] → 0[q

][q

] , (5) [q

] → 1,

(3) [q

] → 0[q

][q

] , (6) [q

] →ε, (7) [q

] →ε.

Глава 6

МАШИНЫ ТЬЮРИНГА

§ 6.1. Неформальное и формальное описания

В этой главе мы рассмотрим еще один тип распознающих устройств — ма-

шины Тьюринга. Это абстрактное устройство было предложено в качестве ма-

тематической модели для описания процедур. Так как наше интуитивное поня-

тие процедуры как конечной последовательности инструкций, которые могут

выполняться механически, не является математически точным, мы не можем

доказать формально, что оно эквивалентно точному понятию машины Тьюрин-

га. Однако из определения этого устройства будет очевидно, что любое вычис-

ление, которое может быть описано посредством машины Тьюринга, может

быть выполнено механически. Также может быть показано, что любое вычисле-

ние, которое может быть выполнено на современной вычислительной машине,

может быть описано посредством машины Тьюринга. Таким образом, если кто-

нибудь когда-нибудь нашел бы процедуру, которая соответствует интуитивным

понятиям, но не поддается описанию посредством машины Тьюринга, то она

была бы необычной природы, так как не могла бы быть запрограммирована для

любой существующей вычислительной машины. Было предложено много дру-

гих формализаций процедуры, и было показано, что все они эквивалентны фор-

мализации машины Тьюринга. Это поддерживает нашу уверенность в том, что

машина Тьюринга имеет достаточную общность, чтобы охватить интуитивное

понятие процедуры.

А.Чёрчем была высказана гипотеза, что любой процесс, который естествен-

ным образом мог бы быть назван процедурой, реализуем машиной Тьюринга.

Впоследствии вычислимость при помощи машины Тьюринга стала признанным

определением процедуры. Мы примем гипотезу Чёрча и просто подставим фор-

мальное определение машины Тьюринга вместо интуитивного понятия проце-

дуры.

В литературе определение машины Тьюринга давалось разными способами.

Мы начнем с обсуждения основной модели (рис. 6.1).

Основная модель имеет конечное управление, ленту, которая разделена на

ячейки, и головку ленты, которая сканирует одну ячейку ленты в один прием.

Лента имеет крайнюю левую ячейку, но простирается в бесконечность в правую

сторону. Каждая ячейка может содержать ровно один из конечного числа сим-

волов ленты.

Первоначально n крайних левых ячеек для некоторого конечного n

содержит входную цепочку, строку символов ленты, называемых входными сим-

волами. Остальные ячейки до бесконечности содержат пробел — специальный

символ ленты, который не является входным символом.

Рис. 6.1.

В один такт, зависящий от символа, сканируемого головкой ленты, и со-

стояния конечного управления, машина Тьюринга

1) изменяет состояние;

2) печатает символ ленты, не являющийся пробелом, в сканируемой ячейке

ленты, замещая то, что было там записано;

3) сдвигает свою головку влево или вправо на одну ячейку.

Определение 6.1. Машина Тьюринга (Tm) является формальной системой:

T =(Q, Σ, Γ, δ, q

, F), где Q — конечное множество состояний; Γ — конечное

множество допустимых символов ленты, один из них, обычно обозначаемый

буквой B, есть пробел; Σ⊆Γ\{B} — множество входных символов;

δ: Q ×Γ→ Q × (Γ \{B}) × {L, R} — функция следующего такта (движения),

для некоторых аргументов может быть не определена

; q

∈Q — начальное со-

стояние; F ⊆ Q — множество конечных состояний.

Определение 6.2. Конфигурацией машины Тьюринга назовем тройку (q, α, i),

где q ∈Q — текущее состояние машины Тьюринга; α∈(Γ \{B})

— строка, яв-

ляющаяся непустой частью ленты; i — целое, определяющее позицию головки

ленты, отсчитываемую от левого конца ленты.

Заметим, что если головка ленты покидает ячейку, она должна напечатать

непустой символ в этой ячейке, так что лента всегда содержит непустой блок

символов (α — этот блок) с бесконечным числом пробелов справа от него.

Определим теперь один такт (движение) машины Тьюринга T. Пусть

(q, A

... A

, i) — некоторая ее конфигурация, где 1 ≤ i ≤ n + 1.

Случай 1. Если 1 ≤ i ≤ n и δ(q, A

)=(p, A, R), то

(q, A

... A

, i)

(p, A

... A

i – 1

i + 1

... A

, i +1),

т.е. T печатает символ A в i-й позиции и двигается вправо.

Случай 2. Если 2 ≤ i ≤ n и δ(q, A

)=(p, A, L), то

(q, A

... A

, i) (p, A

... A

i – 1

A A

i + 1

... A

, i –1),

т.е. T печатает символ A в i-й позиции и двигается влево, не сходя с левого

конца ленты.

Мы не позволили Tm печатать пробел ради простоты определения конфигураций. Од-

нако Tm могла бы иметь другой символ, который трактуется точно так же, как пробел, за ис-

ключением того, что Tm разрешается печатать этот символ псевдопробела. Разумеется, никакой

дополнительной мощности не появляется за счет введения такого символа. В неформальном

обсуждении мы часто допускаем печать пробела, зная, что вместо него можно использовать

другой, но эквивалентный ему символ.

Лента:

Конечное

управление

Случай 3. Если i = n +1, то головка сканирует пробел B.

а) Если при этом δ(q, B)=(p, A, R), то

(q, A

... A

, n +1)

(p, A

... A

A, n +2).

б) Если при этом δ(q, B)=(p, A, L), то

(q, A

... A

, n +1)

(p, A

... A

A, n).

Таким образом, мы ввели отношение непосредственного следования одной

конфигурации за другой. Очевидным образом можно определить степень, тран-

зитивное и рефлексивно-транзитивное замыкания этого отношения. Будем обо-

значать их традиционно через ,

соответственно. Если две конфигурации

связаны знаком

, то мы будем говорить, что вторая получается из первой за n

движений. Соответственно запись

обозначает положительное число движе-

ний, а

— любое число движений, включая нуль.

Определение 6.3. Пусть T = (Q, Σ, Γ, δ, q

, F) — машина Тьюринга. Язык,

принимаемый машиной T есть L = {w | w ∈Σ

и (q

, w, 1)

(q, α, i)

для некото-

рых q ∈F, α∈Γ

и i > 0}.

Мы

предполагаем, что данная Tm, распознающая язык L, останавливается,

т.е. не имеет никакого следующего движения, всякий раз, как входная цепочка

принимается. Но для цепочек, которые не принимаются, Tm может не остано-

виться.

Пример 6.1. Построим Tm, распознающую cfl L ={0

| n ≥ 1}. Положим

T = (Q, Σ, Γ, δ, q

, F), где Q ={q

, q

}; Σ = {0,1}; Γ = {0, 1, B, X, Y};

F ={q

}. Функцию δ определим следующим образом:

1. δ(q

, 0) = (q

, X, R).

В состоянии q

символ 0 заменяется на X и машина сдвигается вправо в со-

стояние q

в поисках 1.

2. а) δ(q

, 0) = (q

, 0, R);

б) δ(q

, Y)=(q

, Y, R);

в) δ(q

, 1) = (q

, Y, L).

Оставаясь в состоянии q

машина продвигается вправо сквозь все нули (п. 2а)

и блок Y (п. 2б). Наткнувшись на 1, заменяет ее на Y и переходит в состояние q

начав движение влево (п. 2в).

3. а) δ(q

, Y)=(q

, Y, L);

б) δ(q

, X)=(q

, X, R);

в) δ(q

, 0) = (q

, 0, L).

Оставаясь в состоянии q

, машина продвигается влево сквозь блок Y (п. 3а).

Если машина встречает X, все еще оставаясь в состоянии q

, то больше нет ну-

лей, которые следовало бы заменять на X, и машина переходит в состояние q

начиная движение вправо, чтобы убедиться, что не осталось единиц (п. 3б). Ес-

ли же 0 встретился, машина переходит в состояние q

, чтобы продолжить дви-

жение в поисках крайнего левого 0 (п. 3в).