Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 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
1 → q
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
1 → q
3
1L ε011*1ε 23) q
2
ε → q
3
1L ε000*11ε
8) q
3
1 → q
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
1 → q
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ε 
   2) q01 → q01R        ε111ε        7) q11 → q10L      ε100ε
   3) q01 → q01R        ε111ε        8) q1ε → q21L      ε000ε
   4) q0ε → q1εL        ε111ε        9) q2 ε → qz εR    ε1000ε
   5) q11 → q10L        ε111ε

    Из примера видно, что машина Тьюринга из стандартной начальной конфигурации, имея
на ленте аргумент 111, выполнив совокупность команд 1-9, перешла в стандартное
заключительное состояние, имея на ленте результат 1000. Действительно:
    1112 + 12 = 10002.

    Пример 2. Построить машину Тьюринга, выполняющую операцию (x div 2) и имеющую
входной алфавит А = {0, 1, ε}.
    Таблица соответствия данной машины Тьюринга будет иметь следующий вид:
                            0         1         ε             0       1        ε
                   q0     q0 0R     q0 1R    q1 ε L    q2   q3 1L   q2 0L    q3 1L

                   q1     q3 ε L    q2 ε L             q3   q2 0L   q2 1L    qz ε R

   Операция (x div 2) реализована сдвигом цепочки вправо на 1 разряд.

    Пример 3. Построить машину Тьюринга, которая выполняет копирование заданного
аргумента. Выберем входной алфавит А={0,1,ε}. Представим данную машину таблицей
соответствия:

                                    0           1              *              ε
                    q0            q11L        q10R           q0*L           qzεR
                    q1                        q11R           q2*R           q2*R
                    q2                        q21R                          q31L
                    q3            q00R        q31L           q3*L

      Запишем программу построенной машины для заданной входной цепочки на ленте,
равной двоичному числу 111. Слева от каждой команды приведем представление входной
цепочки на ленте до выполнения данной команды. Символ, который находится под
головкой, будем помечать подчеркиванием.
      1) q01 → q10R        ε111ε         17) q31 → q31L     ε001*11ε
      2) q11 → q11R        ε011ε         18) q30 → q00R      ε001*11ε
      3) q11 → q11R        ε011ε         19) q01 → q10R      ε000*11ε
      4) q1ε → q2*R        ε011ε         20) q1* → q2*R      ε000*11ε
      5) q2ε → q31L       ε011*ε         21) q21 → q21R      ε000*11ε
      6) q3* → q3*L       ε011*1ε        22) q21 → q21R      ε000*11ε
      7) q31 → q31L       ε011*1ε        23) q2ε → q31L      ε000*11ε
      8) q31 → q31L       ε011*1ε        24) q31 → q31L      ε000*111ε
      9) q30 → q00R       ε011*1ε        25) q31 → q31L      ε000*111ε
      10) q01 → q10R      ε011*1ε        26) q3* → q3*L      ε000*111ε
      11) q11 → q11R      ε001*1ε         27) q30 → q00R      ε000*111ε
      12) q1* → q2*R      ε001*1ε        28) q0* → q0*L      ε000*111ε
      13) q21 → q21R      ε001*1ε         29) q00 → q01L     ε000*111ε
      14) q2ε → q31L      ε001*1ε         30) q00 → q01L      ε001*111ε

Страницы