Распознающая Машина Тьюринга

Постановка задачи

Необходимо реализовать распознающую Машину Тьюринга для определения принадлежности входного слова языку L = { www│wÎ{0, 1}^*}. Машина проверяет принадлежность слова языку и после него записывает символ “T”, если слово принадлежит языку и символ “F” - в противном случае.

Пример входных данных: 110110110

Пример выходных данных: 110110110T

Описание распознающей Машины Тьюринга

Таблица 3.1 - Таблица состояний

Продолжение таблицы 3.1

В таблице 3.2 приведены комментарии, поясняющие назначение состояний:

Таблица 3.2 - Комментарии к состояниям Машины Тьюринга

Продолжение таблицы 3.2

Продолжение таблицы 3.2

Продолжение таблицы 3.2

На рисунке 3.1 приведено тестирование алгоритма распознающей машины:

Входные данные: 101010

Результат: 101010T

На рисунке 3.2 приведён график временной сложности выполнения алгоритма.

Рисунок 3.2 - График временной сложности

На графике видно, что функция сложности имеет два скачка в точках 3 и 6. Это обусловлено тем, что слова, длинна которых не кратна трём отсекаются ещё на первых этапах проверки, в то время как слова, кратные трём нуждаются в дополнительном исследовании. Притом, если слово кратно трем, но не является словом языка, машина закончит свою работу раньше, чем при обработке слова языка.

Для вычисления функции сложности рассмотрим такие входные данные: 110110110.

Головка будет двигаться вперёд (состояния 0, 1, 2) и пройдёт 3 шага, затем 4 шага назад. Второй проход: 7 шагов вперёд, 8 назад. Третий проход: 11 шагов назад, 12 вперёд. Можно заметить, что:

(3.1)

Или в общем случае, для произвольного m — количества проходов (количество проходов равно длине слова (n), делённому на 3).

(3.2)

Итого:

(3.3)

(3.4)

Для второй тройки:

(3.5)

Так как троек три, то весь этап займёт:

(3.6)

Прибавляя это значение к предыдущему, получим:

(3.7)

После этого производятся проходы с целью проверки. На них тратится:

(3.8)

Всего:

(3.9)

Так как в некоторых местах этого расчёта использовались приближения, слагаемое 1 несущественно.

Это время выполнения для слова, принадлежащего языку. Рассмотрим теперь слова, не принадлежащие языку, длинна которых кратна 3.

……

Следует отметить, что в случае ввода данных, не принадлежащих языку, программа сработает быстрее. Например, в случае ввода слова, длина которого не кратна трём, алгоритм сработает быстрее, чем (3.3).