Форум Академгородка, Новосибирск > Подсобите составить машину тьюринга
Помощь - Поиск - Пользователи - Календарь
Полная версия этой страницы: Подсобите составить машину тьюринга
Форум Академгородка, Новосибирск > Образование > Задачник
Kostrach
Задано число N, нужно зделать так, чтобы машина была применима только к словам длинной 3N.
Не важно что машина будет делать с этими словами))
Алфавит состоит из единицы и из пустого места, больше ничего
Agent_Smith
Странная формулировка задачи. Если N фиксированно, то и 3N фиксированно.
Обозначим 3N через M. Так как пустой символ вспомогательный, то фактически алфавит состоит только из единицы
Пустой символ обозначаем через 0.

Вот машина применимая к словам из $M$ единиц:
q_1 0 -> q_2 0 R
q_2 1 -> q_3 1 R
q_3 1 -> q_4 1 R
...
q_k 1 -> q_{k+1} 1 R для всех k от 2 до M+1
...
q_{M+2} 0 -> q_0 0 // остановка.

Эта машина останавливается (достигает состояния q_0) только на словах из M единиц.
==================================================================
Другая задача (которая может быть имелась ввиду) Машина должна определять слова длины, делящейся на 3 (пустое слово, 111, 111111 и т.д.):

q_1 0 -> q_2 0 R
q_2 0 -> q_0 0 //остановка
q_2 1 -> q_3 1 R //пока встретили 3N+1 единиц
q_3 1 -> q_4 1 R //пока встретили 3N+2 единиц
q_4 1 -> q_2 1 R //пока встретили 3N единиц

Эта машина останавливается (достигает состояния q_0) только на словах из 3N единиц (N-произвольное).

Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.
Русская версия IP.Board © 2001-2024 IPS, Inc.