Теория алгоритмов. Дз 2025-10-17

Вариант 2

Задание

Построить машину Тьюринга, переводящую слово на ленте вида

$$\epsilon \underset{n}{\underbrace{00\dots 00}}\underset{n}{\underbrace{11\dots 11}}\epsilon$$

в слово на ленте вида

$$\epsilon \underset{n}{\underbrace{0101\dots 01}}\epsilon$$

Идея решения

Затираем первые $n$ нулей в начале строки (меняем на $\epsilon$). Среди оставшихся $n$ единиц единицы на нечетных местах заменяем на 0.

Решение

Полагаем, что состояние, записанное в первой строке является начальным состоянием

Состояние	0	1	$\epsilon$	F
$q_0$	$(q_0,\epsilon ,\to )$	$(q_1,0,\to )$	$(q_f,\epsilon ,\_)$	0
$q_1$		$(q_0,1,\to )$	$(q_f,\epsilon ,\_)$	0
$q_f$				1

Формат для сайта

{
    "alphabet": [
        "0",
        "1"
    ],
    "states": {
        "q0": {
            "0": "λ R q0",
            "1": "0 R q1",
            "comment": "Видим на ленте 0 -> затираем его, сдвигаемся вправо, состояние не меняем. Видим на ленте 1 -> переходим в сотояние q1, заменив 1 на 0 на ленте. Видим на ленте λ - признак того, что строка обработана. Допуск",
            "λ": "!"
        },
        "q1": {
            "0": "N",
            "1": "1 R q0",
            "comment": "Видим на ленте 1 -> оставляем 1, сдвигаемся вправо, переходим в сотояние q0. Видим на ленте λ -> признак того, что строка обработана. Допуск",
            "λ": "!"
        }
    },
    "word": "00001111"
}

Формат для сайта

// Вход: строка вида 00...0011...11
//                   \__n__/\__n__/
// Выход: строка вида 0101...0101
//                    \____n____/
// Идея: Затираем первые n нулей в начале строки.
//       Среди оставшихся n единиц единицы на нечетных местах заменяем на 0.
//
// Решение:
// Множество состояний: Q = {q0, q1, qf}
// Начальное состояние: q0
// Заключительное состояние: qf
// Функция переходов
//| Q | 0      | 1      | _       |
//| - | ------ | ------ | ------- |
//|q0 | q0,λ,> | q1,0,> | qf,_,-) |
//|q1 |        | q0,1,> | qf,_,-) |
//|qf |        |        |         |
//
// Сыромятников Дмитрий, КН-401

name: Variant 2
init: q0
accept: qf

q0,0
q0,_,>

q0,1
q1,0,>

q0,_
qf,_,-

q1,1
q0,1,>

q1,_
qf,_,-