Kostrach
27.11.2012, 23:40
Задано число N, нужно зделать так, чтобы машина была применима только к словам длинной 3N.
Не важно что машина будет делать с этими словами))
Алфавит состоит из единицы и из пустого места, больше ничего
Agent_Smith
07.01.2013, 13:47
Странная формулировка задачи. Если 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-произвольное).