Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Задание 1. Конечный автомат задан диаграммой. Определить входной алфавит , выходной алфавит , внутренний алфавит , систему команд автомата:
Задание 2. Для автомата найти минимальный :
, | , | , | , | , | , | , | |
, | , | , | , | , | , | , | |
, | , | , | , | , | , | , |
Задание 3. Определить последовательность , в которую преобразуется заданная последовательность , в результате работы автомата:
автомат из упражнения II, при , ;
Практическая работа 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
Дата публикования: 2015-11-01; Прочитано: 1280 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!