машина тьюринга. информатика машина тьюринга. 1 задание (увелечение восьмиричного числа на 1)

• Название: 1 задание (увелечение восьмиричного числа на 1)
• Анкор: машина тьюринга
• Дата: 16.10.2019
• Размер: 17.75 Kb.
• Имя файла: информатика машина тьюринга.docx
• Тип: Документы; #90481

1 задание (увелечение восьмиричного числа на 1)

	1	2	3	4	5	6	7	е
q1	1 q1 R	2 q1 R	3 q1 R	4 q1 R	5 q1 R	6 q1 R	7 q1 R	e q2 L
q2	2 q3 S	3 q3 S	4 q3 S	5 q3 S	6 q3 S	7 q3 S	0 q3 L	1 q3 S
q3	S	S	S	S	S	S	S	S

R-right(вправо)

L-Left(влево)

Обьяснение В состоянии q1 R машина должна найти правый конец числа, в состоянии q2 машина должна увеличить самый правый символ на 1 причем если самым правым оказался символ 7, то машина дожна перевести его в 0 и потом сделать шаг влево, и так пока она не наткнется на другой символ, в том числе и пустой, который в этом случае она заменит на 1, как только она достигнет начала последовательности — она остановится

2 задание (уменьшение десятичного числа на 1)

	1	2	3	4	5	6	7	8	9
q 1	0 q1 S	1 q1 S	2 q1 S	3 q1 S	4 q1 S	5 q1 S	6 q1 S	7 q1 S	8 q1 L
q 2	S	S	S	S	S	S	S	S	S

Обьяснение Состояние q1 — уменьшает самую маленькую цифру на 1 причем Если она не равна нулю, то после уменьшения машина останавливается , если же самая маленькая цифра равна 0, то вместо нее пишем 9, после этого смещаемся влево и вновь выполняем вычитание.

3 задание (уменьшение на 1 )

	0	1	2	3	4	5	6	7	8	9	e
q 1
q 2
q 3