Сборник упражнений по алгоритмическим схемам (МТ и НАМ)

В данном сборнике отражены типичные задачи по алгоритмическим схемам «Машина Тьюринга» (МТ) и «Нормальные Алгоритмы Маркова» (НАМ), которые решаются на семинарских занятиях студентами 110 и 111 групп на 1 курсе ВМиК МГУ.

Для проверки своих решений можете прибегнуть к помощи интерактивного эмулятора нормальных алгоритмов Маркова, либо машины Тьюринга.

Принятые в тексте обозначения:

• А  — исходный алфавит алгоритмической схемы.
• P  — означает входное слово.
• Λ — означает пустой символ для МТ или пустое слово для НАМ. При решении задач по алгоритмическим схемам всегда необходимо проверять граничные условия. Необходимо проверить, как алгоритм реагирует на пустые входные слова, и слова, не удовлетворяющие условию задачи.

Базовые задачи

• Дан алфавит A = {a, b, c}. Перенести в начало все a.
• Дан алфавит A = {a, b, c}. Упорядочить буквы в P  по алфавиту.
• Дан алфавит A = {*, a, b, c}, P  = *Q , где *∉Q. Получить Q*.
• Дан алфавит A = {a, b, c}. Если входное словоP  содержит букву a то написать a, иначе Λ
• Дан алфавит A = {a, b, c}. Приписать к входному слову P  букву a: P  → P a.
• Дан алфавит A = {a, b, c}. Приписать к входному слову P  слово aba: P  → P aba.
• Дан алфавит A = {a, b, c}. Написать 1, если входное слово P  чётной длины, иначе написать 2.
• Дан алфавит A = {a, b, c}. Удвоить последнюю букву входного слова P  = Qξ: P  → Q ξξ.
• Дан алфавит A = {a, b, c}. Приписать к слову P  слева его первую букву.
• Дан алфавит A = {a, b, c}. Переставить первую букву P  в его конец.
• Дан алфавит A = {a, b, c}. Удвоить каждую букву P .
• Дан алфавит A = {a, b, c}. Заменить последнее вхождение буквы a в P  на bb. Если a∉P , то оставить P  без изменений.
• Дан алфавит A = {a, b, c} Удалить второе вхождение a.
• Дан алфавит A = {a, b, c}. Если в P  входит буква a ещё раз, тогда написать a, иначе Λ.
• Дан алфавит A = {a, b, c}. Приписать к концу P  столько палочек, сколько раз буква b входит в P . Пример: abcbb → abcbb|||.
• Дан алфавит A = {|, >}, P  = |||...||>. Входное слово P  представляет собой запись некоторого числа n в палочной системе счисления, в конце которой стоит знак >. Дописать число n в палочной системе счисления после знака > (дописать n палочек). Пример: ||||> → ||||>||||.
• Дан алфавит A = {|, −}, P  = |||...||−|||...||. Входное слово P  представляет собой запись некоторых чисел n и m в палочной системе счисления, разделённую знаком «−». Получить запись модуля разности n и m в палочной системе счисления. Пример: |−||| → ||.
• Дан алфавит A = {|, *, =}, P  = |||...||*|||...||=. Входное слово P  содержит n палочек слева от знака * и m палочек справа. В конце стоит знак =. Дописать справа от знака = nm палочек. Пример: ||*|||= → ||*|||=||||||.
• Дан алфавит A = {a, b, c}. Если P  = abc, то написать a, иначе Λ.
• Дан алфавит A = {a, b}, входное слово P  чётной длины. Стереть правую половину слова P . Пример: babbaa → bab.
• Дан алфавит A = {a, b}. Обратить входное слово P . Пример: babbaa → aabbab.
• Дан алфавит A = {0, 1}. Входное слово P  представляет собой двоичную запись некоторого числа n. Написать число n + 1 в двоичной системе счисления. Пример: 1011 → 1100.
• Дан алфавит A = {|}. Входное слово P  представляет собой запись некоторого числа n в палочной системе счисления. Написать двоичную запись числа n. Пример: ||||| → 101.
• Дан алфавит A = {0, 1}. Входное слово P  представляет собой двоичную запись некоторого числа n. Написать в двоичной системе счисления остаток от деления n на двоичное число 11₂. Пример: 101 → 10.
  Примечание: Не смотря на то, что решение задачи в рамках двочиной системы счисления занимает не более 5 строк, поиск его достаточно нетривиален, поэтому в решении допускается переход из двоичной системы счисления в палочную и обратно.
• Дан алфавит A = {a, b}. Удвоить входное слово P : P →P P . Пример: abb → abbabb.

Задачи для самостоятельных работ

В контрольных задачах делается упор на определение количества вхождений, номера позиции вхождения, комбинирование различных подходов.

• Дан алфавит A = {a, b, c}. Если во входное слово P  входит буква b, то заменить все вхождения букв b на с.
• Дан алфавит A = {a, b, c}. Заменить во входном слове P  все вхождения ba, на a.
• Дан алфавит A = {a, b}. Заменить во входном слове P  все стоящие на чётных позициях вхождения b на bab. Пример: abaababb → ababaababbab.
• Дан алфавит A = {a, b}. Удалить во входном слове P  два последних вхождения буквы a. Пример: aabaababb → aababbb.