Практическая работа 22. Разработка программ для машины Тьюринга
Вариант 1
На информационной ленте машины Тьюринга содержится массив символов +. Необходимо разработать функциональную схему машины Тьюринга, которая каждый второй символ + заменит на –. Каретка в состоянии q0 находится где-то над указанным массивом.
Вариант 2
Дано число n в восьмиричной системе счисления. Разработать машину Тьюринга, которая увеличивала бы заданное число n на 1.
Вариант 3
Дана десятичная запись натурального числа n >1. Разработать машину Тьюринга, которая уменьшала бы заданное число n на 1. При этом запись числа n –1 не должна содержать левый нуль, например, 100–1=99, а не 099. Начальное положение головки — правое.
Вариант 4
Дан массив из открывающихся и закрывающихся скобок. Построить машину Тьюринга, которая удаляла бы пары взаимных скобок. Например, дано: «) (() (()», надо получить: «)... ((.».
Вариант 5
Дана строка из букв «a» и «b». Разработать машину Тьюринга, которая переместит все буквы «a» в левую, а буквы «b» — в правую части строки. Каретка находится над крайним левым символом строки.
Вариант 6
Даны два целых положительных числа в десятичной системе счисления. Сконструировать машину Тьюринга, которая будет находить разность этих чисел, если известно, что первое число больше второго, а между ними стоит знак –. Каретка находится над левой крайней цифрой левого числа.
Вариант 7
Даны два целых положительных числа в различных системах счисления, одно — в троичной системе, другое — в десятичной. Разработать машину Тьюринга, которая будет находить сумму этих чисел в десятичной системе счисления.
Вариант 8
Дата добавления: 2016-01-06; просмотров: 32; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!