Лекция: Практические задания.

Выяснить, применимы ли программы к заданным состояниям машины Поста, указать результат работы машины Поста для каждого состояния. (с14)

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

Ответы:

a) 1) 1110011000

2) зацикливание

3) 1001011000

b) 1) зацикливание

2) 010011

3) 01010110

c) 1) зацикливание (…111)

2) зацикливание (…1111001)

3) зацикливание (1010111…)