Применение машин тьюринга к словам



бет1/4
Дата23.02.2016
өлшемі344.5 Kb.
  1   2   3   4
Практические задания к разделу 5

ПРИМЕНЕНИЕ МАШИН ТЬЮРИНГА К СЛОВАМ
5.1. Имеется машина Тьюрин­га с внешним алфавитом А={а0, 1}, алфавитом внутренних состояний Q={q0, q1}, и со следующей функциональной схе­мой (программой):

А Q

q0

q1

а0




q01

1




q1

(В столбце q0 ничего не написано, потому что q0 заключительное состояние машины, т.е. такое состояние, оказавшись в котором машина останавливается. Функциональную схему или программу кратко можно записать в виде последовательности из двух команд: q1а0q01, q11  q11П.) Определите, в какое слово переработает машина каждое из следующих слов, если она находится в начальном состоянии q1 и обозре­вает указанную ячейку:

а) 1ao11aoao11 (обозревается ячейка 4, считая слева);

б) 11ao111ao1 (обозревается ячейка 2);

в) 1aoao111 (обозревается ячейка 3);

г) 1111а011 (обозревается ячейка 4);

д) 11ao1111 (обозревается ячейка 3);

е) 1111111 (обозревается ячейка 4);

ж) 11111 (обозревается ячейка 5);

з) 111 (обозревается ячейка k).

Изобразите схематически последовательность конфигура­ций, возникающих на ленте на каждом такте работы машины.

Решение. а) Изобразим схематически начальную кон­фигурацию (начальное положение машины):














q1



















1

ao

1

1

ao

ao

1

1



Схема означает, что машина находится в состоянии q1 и обозревает ячейку, в которой записана буква 1, в соседней слева ячейке записана та же буква, а в соседней справа ячейке за­писана буква а0 (т. е. согласно нашему соглашению ничего не записано) и т. д. Ничего не записано и во всех непоказанных ячейках ленты. На первом такте работы согласно команде q11  q11П машина остается в прежнем состоянии q1, в обо­зреваемую ячейку вписывает букву 1 (т. е. фактически оставляет уже вписанную в эту ячейку букву 1 неизменной ) и пере­ходит к обозрению следующей правой ячейки (т. е. ячейки 5). Изобразим схематически положение, в котором оказалась


машина:
















q1
















1

ao

1

1

ao

ao

1

1




На втором такте работы согласно команде q1aoqo1 машина вписывает в обозреваемую ячейку 5 букву 1, продолжает обозревать ту же ячейку и переходит в состояние q0, т. е. останавливается. Создавшаяся конфигурация имеет вид:
















q0
















1

ao

1

1

1

ao

1

1




Таким образом, из данного начального положения слово 1ao11aoao11 перерабатывается машиной в слово 1ao111ao11.

5.2. Дана машина Тьюринга с внешним алфавитом А = {а0, 1}, алфавитом внутренних состояний Q = { q0, q1, q2, q3, q4, q5, q6, q7 } и со следующей функциональной схемой (про­граммой):

А Q

q1

q2

q3

q4

q5

q6

q7

a0

q4 a0П

q6 a0П

q6 a0П

q01

q4 a0П

q0 a0

q6 a0П

1

q2

q3

q1

q5 a0

q5 a0

q7 a0

q7 a0

Изображая на каждом такте работы машины получающуюся конфигурацию, определите, в какое слово перерабатывает машина каждое из следующих слов, исходя из начального стандартного положения (стандартным считается такое поло­жение, когда машина находится в состоянии q1 и обозревает крайнюю правую ячейку из тех, в которых записано перера­батываемое слово):

а) 11111; б) 111111; в) 1111; г) 1111111; д) 111;

е) 1ao111aoao1111; ж) 11aoao111111; з)11ao111.

Решение. д) Выписываем последовательность кон­фигураций машины при переработке ею слова 111 из началь­ного стандартного положения:















q1













q4







1)




1

1

1




7)







1

1













q2
















q5







2)




1

1

1




8)









1










q3






















q4




3)




1

1

1




9)









1







q1

























q5




4)




1

1

1




10)





















q4






















q4




5)




1

1

1




11)





















q5






















q0




6)






1

1




12)









1



Итак, слово 111 из начального стандартного положения пере­рабатывается машиной в слово 1.



5.3. Машина Тьюринга определяется следующей функцио­нальной схемой:

А Q

q1

q2

q3

а0




q3

q1а0Л

1

q2 а0Л

q2

q3

*

q0 а0

q2

q3

Определите, в какое слово перерабатывает машина каждое из следующих слов, исходя из начального стандартного состояния (определение которого см. в задаче 5.2). После этого постарайтесь усмотреть общую закономерность в работе ма­шины:

а) 111 * 111; б)1111 * 11; в) 111 * 1; г) 1 * 11;

д) 11 * 111; е) 11111 * ; ж) * 1111.

5.4. Машина Тьюринга определяется следующей функцио­нальной схемой:


А Q

q1

q2

q3

q4

а0

q1а0П

q3а0П

q3а0Л

q1а0Л

1

q2а0Л

q2

q4а0П

q4

*

q0а0

q3




q4

Определите, в какое слово перерабатывает машина каждое из следующих слов, исходя из стандартного начального состоя­ния:

а) 111 * 11; б) 11 * 11; в) 1111 * 1; г) 11111 * 111; д) 11111 * 1111.

Постарайтесь выявить общую закономерность в работе машины.

5.5. Для машины Тьюринга, определяемой следующей функциональной схемой:


А Q

q1

q2

q3

q4

а0

q4а0П

q3а0Л

q1а0П

q0а0Л

1

q2

q1

q1

q1



q1Л

q2П

q3

q4а0П



q1Л

q2П

q3а0Л

q4

и для следующих слов определите, в какое слово переработа­ется каждое из них данной машиной, исходя из начального положения, при котором машина находится в состоянии q1 и обозревается указываемая ячейка:

а) 11111 (обозревается ячейка 2, считая слева);

б) 111 (обозревается ячейка 1);

в) 1111111111 (обозревается ячейка 4);

г) 111111 (обозревается ячейка 2);

д) 111111111111111 (обозревается ячейка 6).


Какова общая закономерность работы машины?

5.6. Машина Тьюринга с внешним алфавитом А = 0, 1} определяется следующей программой:

А Q

q1

q2

q3

а0

q2 а0П

q2 а0П

q0а0

1

q1

q3

q3

Остановится ли когда-нибудь эта машина, если она начнет перерабатывать следующее слово (в начальный момент; в состоянии q1, машина обозревает ячейку, в которой записана самая левая буква перерабатываемого слова):

а) 111а0а01;

б) 11а0а011а01;

в) 111111?

Если остановка происходит, то какое слово получается в ре­зультате, какая ячейка и в каком (перед остановкой) состоя­нии обозревается?

5.7. Остановится ли когда-нибудь машина Тьюринга, заданная следующей программой:


А Q

q1

q2

q3

а0

q1П

q3а0Л

q0а0

1

q2

q1а0П

q2

если она начнет перерабатывать следующее слово, начав в состоянии q1 обозревать ячейку, в которой записана самая левая буква перерабатываемого слова:

а) 1111а01;

б) 11111;

в) 1а001?

Если машина остановится, то какова ее заключительная кон­фигурация?

5.8. Останавливается ли когда-нибудь машина Тьюрин­га с внешним алфавитом А=0,1} и функциональной схе­мой:


А Q

q1

q2

q3

q4

а0

q2а0П

q3а0Л

q1

q0а0

1

q2

q4а0П

q01

q2а0




Достарыңызбен бөлісу:
  1   2   3   4




©dereksiz.org 2020
әкімшілігінің қараңыз

    Басты бет