Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 18 стр.

UptoLike

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

2) q
0
1 q
0
1R ε111ε 7) q
1
1 q
1
0L ε100ε
3) q
0
1 q
0
1R ε111ε 8) q
1
ε → q
2
1L ε000ε
4) q
0
ε → q
1
εL ε111ε 9) q
2
ε → q
z
εR ε1000ε
5) q
1
1 q
1
0L ε111ε
Из примера видно, что машина Тьюринга из стандартной начальной конфигурации, имея
на ленте аргумент 111, выполнив совокупность команд 1-9, перешла в стандартное
заключительное состояние, имея на ленте результат 1000. Действительно:
111
2
+ 1
2
= 1000
2
.
Пример 2. Построить машину Тьюринга, выполняющую операцию (x div 2) и имеющую
входной алфавит А = {0, 1, ε}.
Таблица соответствия данной машины Тьюринга будет иметь следующий вид:
0 1
ε
0 1
ε
q
0
q
0
0R q
0
1R
q
1
ε L
q
2
q
3
1L q
2
0L q
3
1L
q
1
q
3
ε L q
2
ε L
q
3
q
2
0L q
2
1L
q
z
ε R
Операция (x div 2) реализована сдвигом цепочки вправо на 1 разряд.
Пример 3. Построить машину Тьюринга, которая выполняет копирование заданного
аргумента. Выберем входной алфавит А={0,1,ε}. Представим данную машину таблицей
соответствия:
0 1 *
ε
q
0
q
1
1L
q
1
0R q
0
*L
q
z
εR
q
1
q
1
1R
q
2
*R q
2
*R
q
2
q
2
1R
q
3
1L
q
3
q
0
0R
q
3
1L
q
3
*L
Запишем программу построенной машины для заданной входной цепочки на ленте,
равной двоичному числу 111. Слева от каждой команды приведем представление входной
цепочки на ленте до выполнения данной команды. Символ, который находится под
головкой, будем помечать подчеркиванием.
1) q
0
1 q
1
0R ε111ε 17) q
3
1q
3
1L ε001*11ε
2) q
1
1 q
1
1R ε011ε 18) q
3
0 → q
0
0R ε001*11ε
3) q
1
1 q
1
1R ε011ε 19) q
0
1 → q
1
0R ε000*11ε
4) q
1
ε q
2
*R ε011ε 20) q
1
* q
2
*R ε000*11ε
5) q
2
ε → q
3
1L ε011*ε 21) q
2
1 q
2
1R ε000*11ε
6) q
3
*q
3
*L ε011*1ε 22) q
2
1 q
2
1R ε000*11ε
7) q
3
1q
3
1L ε011*1ε 23) q
2
ε → q
3
1L ε000*11ε
8) q
3
1q
3
1L ε011*1ε 24) q
3
1 q
3
1L ε000*111ε
9) q
3
0
q
0
0R ε011*1ε 25) q
3
1 q
3
1L ε000*111ε
10) q
0
1q
1
0R ε011*1ε 26) q
3
* q
3
*L ε000*111ε
11) q
1
1 q
1
1R ε001*1ε 27) q
3
0 q
0
0R ε000*111ε
12) q
1
* q
2
*R ε001*1ε 28) q
0
* q
0
*L ε000*111ε
13) q
2
1 q
2
1R ε001*1ε 29) q
0
0 q
0
1L ε000*111ε
14) q
2
ε → q
3
1L ε001*1ε 30) q
0
0 q
0
1L ε001*111ε