Задачи по теории алгоритмов

Задачи по теории алгоритмов

Написать программу МТ, которая аннулирует все слова в алфавите {a, b}, содержащие вхождение заданного непустого слова u. Указание: пусть u=u(1)…u(m); буквы слова u должны содержаться в программе машины в качестве параметров.
Написать схему НА, обращающего любое слово в заданном алфавите V, т.е. перерабатывающего любое слово w Î V*, в слово w^R.
Определим операцию * склеивания слов x=x(1)…x(k) и y=y(1)…y(m) по общей букве: x*y = x(1)…x(k-1)y(2)…y(m), если x(k)=y(1), и xy иначе. Написать программу МТ, выполняющую операцию склеивания, т.е. перерабатывающую пару слов x$y в слово x*y.
Написать схему НА, который аннулирует входное слово тогда и только тогда, когда оно содержит не менее трех вхождений некоторого фиксированного непустого слова u..
Используя теоремы сочетания применительно к МТ, построить МТ, выполняющей умножение натуральных чисел, представленных словами в алфавите V₀ = {0,|} (именно, натуральное число n записывается как слово 0||…| - с n палочками).
Используя теоремы сочетания, построить НА, аннулирующий все палиндромы в алфавите V. Указание: используйте схемы алгорифмов обращения и правого присоединения слова через разделитель).
Написать программу МТ, которая к произвольному слову в алфавите {a, b} приписывает слева слово aba.
Построить НА для выполнения сложения и умножения конструктивных натуральных чисел. Указание: используйте теоремы сочетания.
Написать программу МТ, которая аннулирует любое слово вида x$x, где x Î {a,b}*, а $ Ï {a, b}.
С использованием теорем сочетания построить НА, который аннулирует все слова вида x$x, где x Î {a,b}*, а $ Ï {a, b}.
С использованием теорем сочетания построить НА, который аннулирует все слова вида xx^R, где x Î {a,b}*.
Построить МТ, которая вычисляет модуль разности двух любых натуральных чисел. Указание: используйте сочетания МТ.
Написать программу МТ, которая удваивает любое входное слово в заданном алфавите.
Построить МТ, которая обращает любое входное слово в заданном алфавите. Указание: используйте программу МТ, удваивающей заданное слово, и сочетания МТ.
Написать схему НА, который входное слово x в некотором алфавите V перерабатывает в слово x^Rx .
Является ли алгорифмически разрешимым множество всех двойных слов, т.е. слов вида ww, в заданном алфавите V?
Используя теоремы сочетания, построить МТ, которая проверяет делимость на 3 конструктивного натурального числа.
Построить МТ, которая вычисляет остаток от деления заданного конструктивного натурального числа на 5.
Написать программу МТ, которая сдвигает входное слово на заданное число k ячеек вправо, а в освободившиеся k первых после маркера начала ленты ячейки записывает специальный символ $.
В виде НА реализовать алгоритм сложения натуральных чисел, заданных в двоичной системе счисления.
Векторной формулой подстановки в алфавите V назовем выражение вида (p_1, p₂,…p_k) à (q_1, q₂,…q_k), где p_i, q_i – слова в алфавите V (i=1,…,k). Применение векторной формулы подстановки к слову x состоит, по определению, в следующем: если слово x может быть представлено в виде x₁p₁x₂p₂…x_kp_kx_k₊₁, где каждое вхождение x_i*p_i*x_i₊₁p_i₊₁… x_kp_kx_k₊₁ есть первое, то результатом применения векторной формулы подстановки к слову x считается слово x₁q₁x₂q₂…x_kq_kx_k₊₁; в противном случае результат применения векторной формулы подстановки к слову x не определен. Построить НА, выполняющий векторную подстановку.
Построить МТ, которая для заданного k > 0 проверяет, что входное слово имеет длину, строго большую k, и тогда вставляет специальный символ $ между k-ой и (k+1)-ой буквами. В противном случае (т.е при длине входного слова, не большей k) входное слово не изменяется, т.е. МТ реализует тождественную функцию.
Построить НА, который для любых двух натуральных чисел, заданных в виде слов в алфавите {0,|} проверяет, является одно из них делителем другого.
Построить МТ, распознающую палиндромы в алфавите {a, b}.
Реализовать в виде МТ разрешающий алгоритм для множества правильных скобочных структур.
Написать схему НА, который каждое слово x в заданном алфавите V перерабатывает в слово xx^Rx.
Написать схему НА, утраивающего заданное слово.
Написать программу МТ, которая любое слово x в алфавите V преобразует в слово xxx^R
Построить МТ, которая для любых двух натуральных чисел, заданных в виде слов в алфавите {0,|} проверяет, является одно из них делителем другого.
Реализовать в виде НА разрешающий алгоритм для множества правильных скобочных структур.