Распознающая машина тьюринга
Постановка задачи
Необходимо реализовать распознающую Машину Тьюринга для определения принадлежности входного слова языку L = { www│wÎ{0, 1}*}. Машина проверяет принадлежность слова языку и после него записывает символ “T”, если слово принадлежит языку и символ “F” - в противном случае.
Пример входных данных: 110110110
Пример выходных данных: 110110110T
Описание распознающей Машины Тьюринга
Таблица 3.1 - Таблица состояний
| q\a | λ | $ | # | ||||||
| q0 | |||||||||
| q1 | |||||||||
| q2 | |||||||||
| q3 | |||||||||
| q4 | |||||||||
| q5 | |||||||||
| q6 | |||||||||
| q7 | |||||||||
| q8 | |||||||||
| q9 |
Продолжение таблицы 3.1
| q\a | λ | $ | # | ||||||
| q10 | |||||||||
| q11 | |||||||||
| q12 | |||||||||
| q13 | |||||||||
| q14 | |||||||||
| q15 | |||||||||
| q16 | |||||||||
| q17 | |||||||||
| q18 | |||||||||
| q19 | |||||||||
| q20 | |||||||||
| q21 | |||||||||
| q22 | |||||||||
| q23 | |||||||||
| q24 |
В таблице 3.2 приведены комментарии, поясняющие назначение состояний:
Таблица 3.2 - Комментарии к состояниям Машины Тьюринга
| Состояние | Комментарий |
| q0 | |
| q1 |
Продолжение таблицы 3.2
| Состояние | |
| q2 | |
| q3 | |
| q4 | |
| q5 | |
| q6 | |
| q7 | |
| q8 | |
| q9 | |
| q10 | |
| q11 | |
| q12 |
Продолжение таблицы 3.2
| Состояние | |
| q13 | |
| q14 | |
| q15 | |
| q16 | |
| q17 | |
| q18 | |
| q19 | |
| q20 |
Продолжение таблицы 3.2
| Состояние | |
| q21 | |
| q22 | |
| q23 | |
| q24 |
На рисунке 3.1 приведено тестирование алгоритма распознающей машины:
Входные данные: 101010
Результат: 101010T
| Рисунок 3.1 - Тестирование алгоритма |
2.3.3 Временная сложность машины
На рисунке 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).