Алгоритмы Маркова
Договоренности:
слово с двух сторон окружено бесконечным количеством пустых символов (λ);
вставлять символ λ в середину слова нельзя;
использовать символ λ в одиночестве в качестве последовательности символов, которая ищется в слове, нельзя – только вместе с каким то значимым символом.
Рассмотреть работу нормального алгоритма, заданного подстановками:
ba ab
bc ba
bb ac
для входного слова «bcbaab».
Нормальный алгоритм Маркова, реализующий операцию умножения, задан алфавитом A={1;*;Т;Ф} и следующей схемой:
*11 Т*1
*1 Т
1Т Т1Ф
ФТ ТФ
Ф1 1Ф
Т1 Т
ТФ Ф
Ф 1
1 1·
Построить дедуктивную цепочку от слова «11*111».
Алфавит A={1;+}. Задать нормальный алгоритм, реализующий сложение А+В, где А и В – натуральные числа, представленные последовательностями единиц.
Алфавит A={1;-}. Задать нормальный алгоритм, реализующий вычисление псевдоразности А-В, где А и В – натуральные числа, представленные последовательностями единиц.
Алфавит A={1;0}. Задать нормальный алгоритм, который перерабатывает исходное слово в «0».
Алфавит A={1;0}. Задать нормальный алгоритм, который удваивает все символы в слове.
Алфавит A={1;0}. Задать нормальный алгоритм, который удаляет каждый третий символ в слове.
Алфавит A={1;0}. Задать нормальный алгоритм, который ставит в конце слова «+», если в нем есть хотя бы один нуль, и «-» - в противном случае.
Алфавит A={1;0}. Задать нормальный алгоритм для распознавания точно двух нулей в двоичном слове: поставить «+» в конце слова, если в слове точно два нуля, и «-» - в противном случае.
Алфавит A={1;0}. Задать нормальный алгоритм, который перерабатывает слово в «+», если в нем есть хотя бы два нуля, и в «-» - в противном случае.
Алфавит A={1;0}. Задать нормальный алгоритм для распознавания точно двух соседних нулей в двоичном слове: поставить «+» в конце слова, если в слове точно два соседних нуля, и «-» - в противном случае.
Алфавит A={1;0}. Задать нормальный алгоритм, который перерабатывает слово в «+», если в нем точно два соседних нуля, и в «-» - в противном случае.
Алфавит A={1;0}. Задать нормальный алгоритм, который считает количество нулей в слове и записывает результат в конце слова в унарном коде.
Алфавит A={1;0}. Задать нормальный алгоритм, который ставит в конце слова:
«+», если в слове больше нулей;
«-», если в слове больше единиц;
«=», если в слове одинаковое количество нулей и единиц.
Алфавит A={1;0}. Задать нормальный алгоритм, который перерабатывает слово в:
«0», если в слове больше нулей;
«1», если в слове больше единиц;
«=», если в слове одинаковое количество нулей и единиц.
Алфавит A={1;0}. Задать нормальный алгоритм, который копирует слово, поставив в конце исходного слова разделитель «*».
Алфавит A={1;0}. Задать нормальный алгоритм, который копирует слово без всякого разделителя.
Алфавит A={1;0}. Задать нормальный алгоритм, который копирует слово в обратном порядке, поставив в конце исходного слова разделитель «*».
Алфавит A={1;0}. Задать нормальный алгоритм, который копирует слово в обратном порядке без всякого разделителя.
Алфавит A={1;0}. Задать нормальный алгоритм для распознавания двоичных палиндромов: стирает слово и пишет вместо него «+», если слово – палиндром, и «0» - в противном случае.
Алфавит A={1;0}. Задать нормальный алгоритм, который анализирует двоичное слово:
если в нем на каждый нуль приходится по три и более единицы, перерабатывает слово в «3»;
если на каждый нуль приходится менее трех, но не менее двух единиц, перерабатывает слово в «2»;
если на каждый нуль приходится менее двух, но не менее одной единицы, перерабатывает слово «+»;
во всех остальных случаях перерабатывает слово в «-».