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

UptoLike

ВУЗ: 

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

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

Рубрика: 

102
одного счётчика в другой, конечное управление двух-счётчиковой машины
может определить, делится ли n на 2, 3, 5, 7 или какое-нибудь их произведение.
Теорема 6.5. Каждая машина Тьюринга может быть смоделирована
машиной Тьюринга с входной лентой только для чтения и лентой памяти с
двумя символами (пробел и другой символ) при условии, что машина может
печатать пробелы.
Доказательство. Большая часть доказательства будет оставлена читате-
лю. Приём состоит в том, чтобы закодировать каждый из k символов памяти
при помощи r бинарных символов, где 2
r
≥ k. Головка ленты машины Тьюринга
может посетить каждый из r бинарных символов, представляющих
первоначальный символ, чтобы определить, каким он был.
Замечательно, что может быть доказана теорема более сильная, чем
теорема 6.5.
Теорема 6.6. Каждая машина Тьюринга может моделироваться машиной
Тьюринга с входной лентой только для чтения и лентой памяти с двумя
символами: 0 (пробел) и 1. Машина Тьюринга может печатать 0 или 1, где
был найден 0, но не может печатать 0 там, где находилась 1.
Доказательство мы оставляем читателю. Приём состоит в том, чтобы
смоделировать последовательные конфигурации исходной машины Тьюринга
на ленте новой машины. Символы ленты, конечно, кодируются в бинарных
символах. Каждая конфигурация копируется, и попутно производятся необхо-
димые изменения, отражающие движение исходной машины.
Помимо бинарного кодирования первоначального символа машина
Тьюринга, моделирующая исходную, нуждается в ячейках, чтобы указывать (а)
позицию головки в конфигурации, которая копируется, и (б) что бинарное
представление символа уже скопировано
Упражнения
I-6.1. Построить машину Тьюринга, которая распознает язык
L = {wcw | w∈ {a, b}
+
}.
I-6.2. Пусть Tm T = ({q
0
, q
1
, q
2
, q
3
}, {¢ , [, ]}, {¢ , [, ], X, B)}, δ, {q
3
}), где
Какие слова вида ¢w, где w∈{[, ]}
*
, принимаются Tm T?
I-6.3. Пусть G = ({A, B}, {a, b}, P, A), где
P = {A → Ba, Aa → Bb, B → bA, Ab → ε, B → BB, B → b, A → a}.
Каков язык L(G)? Построить Tm, распознающую L(G).
Является ли язык L(G) контекстно-свободным распознает язык
или регулярным?
δ(q
0
, ¢) = (q
0
, ¢, R)
δ
(q
1
, ]) = (q
2
, X, L)
δ(q
0
, X) = (q
0
, X, R) δ(q
2
, a) = (q
2
, a, L) для всех a ≠ ¢
δ(q
0
, [) = (q
1
, X, R) δ(q
2
, ¢) = (q
0
, ¢, R)
δ(q
1
, [) = (q
1
, [, R) δ(q
0
, B) = (q
3
, X, R)
δ(q
1
, X) = (q
1
, X, R)

Страницы