Задачи и упражнения
Описать автомат M с алфавитами A=Z={0, 1} и двумя состояниями s0 и s1, который считывает последовательность из нулей и единиц для проверки четности. Построить таблицу и диаграмму состояний.
Построить таблицу и диаграмму состояний для автомата M с алфавитами A=Z={0, 1} и тремя внутренними состояниями S={s0, s1, s2}, функции выхода и перехода которого задаются следующими предписаниями:
Определить для указанных четверок чисел последовательности, полученные на выходе:
а) 0, 1, 0, 1; б) 1, 0, 1, 0; в) 1, 1, 0, 1; г) 0, 1, 1, 0.
Начертить диаграмму состояний автомата M с алфавитами A=Z={0, 1}, который печатает 1, если непосредственно перед этим он считал четыре последовательных 1, и 0 в противном случае. Автомат работает до тех пор, пока не считает три последовательных 0, после чего печатает лишь нули.
Описать машину Тьюринга, которая считывает входную последовательность нулей и единиц и печатает Ч, если число единиц четное, и Н, если нечетно. Строке из нулей и единиц предшествуют и последуют пустые ячейки, обозначаемые #. Символы Ч или Н печатаются в первой пустой ячейке вслед за входной строкой.
Написать алгоритм для машины Тьюринга, выполняющий сложение двух неотрицательных целых чисел. Неотрицательное целое число N в машине Тьюринга задается последовательностью (N+1) единиц, стоящих подряд. Два числа отделяются нулем.
Написать для машины Тьюринга алгоритм прибавления единицы к числу N в десятичной системе счисления.
Составить программу прибавления к произвольному числу единицы для машины Поста, когда головка находится на расстоянии нескольких клеток слева от заданного числа.
Написать для машины Поста программу вычитания двух чисел, разделенных одной пустой клеткой. Уменьшаемое – не меньше вычитаемого. Начальное положение головки над пустой клеткой, отделяющей заданные числа.
Составить программу для машины Поста, создающую на ленте копию заданной последовательности меток справа от нее, когда головка находится над одной из заданных меток.
Составить программу для сложения целых положительных чисел на машине Поста, когда головка находится над числом a, а число b расположено справа от числа a через одну пустую клетку.
Написать для машины Поста программу умножения на 2 числа, записанного метками на ленте, когда головка находится над одной из заданных меток.
Написать для машины Поста программу деления числа, записанного метками, на 2, когда головка находится над одной из заданных меток. Исходное число должно делиться на 2 без остатка.
Построить дедуктивные цепочки от слова «мука» к слову «торт» и от слова «муха» к слову «слон», заменяя каждый раз по одной букве так, чтобы каждый раз получалось слово.
Постройте нормальный алгоритм Маркова, реализующий вычитание двух целых чисел, представленных символами 1. Проверьте его работу на примерах.
Задайте нормальный алгоритм Маркова, реализующий умножение двух чисел, представленных символами 1.
Используя рекурсивные функции, постройте:
а) трехместную функцию сложения;
б) n-местную функцию сложения.
Используя рекурсивные функции, постройте:
а) двухместную функцию умножения;
б) трехместную функцию умножения;
в) n-местную функцию умножения.
Постройте частичную двухместную функцию деления.