Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Задача 9
Эта задача кажется достаточно легкой, но трудности возникают с остановом машины Тьюринга. Ниже приведен один из возможных вариантов машины Тьюринга для этой задачи. Идея решения (условие останова). На ленте есть два исходных массива штрихов. Штрихи начинаем стирать с левого конца массива m. И поочередно стираем самый левый штрих в массиве m и самый правый штрих в массиве n. Но прежде чем стереть правый штрих в массиве n, проверяем, единственный он (т.е. последний, который надо стереть) или нет. Опишем сначала состояния машины Тьюринга, которые необходимы для решения нашей задачи, а затем составим программу-таблицу. Состояние q1 — поиск разделителя между массивами штрихов при движении справа налево; состояние q2 — поиск левого штриха в массиве m; состояние q3 — удаление левого штриха в массиве m; состояние q4 — поиск разделителя при движении слева направо; состояние q5 — поиск правого штриха в массиве n; состояние q6 — проверка единственности этого штриха в массиве n, т.е. определяем, был ли он последним; состояние q7 — если он был последним, то останов, иначе переход на новый цикл выполнения алгоритма.
|