 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Практическая работа 21. Конечные автоматы
|
|
Задание 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; Прочитано: 1278 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
