Кому не сложно - решите, пожалуйста, нижеприведенные задачи (хотя бы по-одной).
1. Опишите детерминированные конечные автоматы, которые допускают следующие языки над алфавитом {0,1}:
a. множество всех цепочек, оканчивающихся на 00;
b. множество всех цепочек, содержащих три нуля подряд;
c. множество цепочек, содержащих в качестве подцепочки 011.
2. Укажите конфигурации машины Тьюринга М1 при обработке следующего входа:
a. 00
b. 000111
c. 00111
3. Рассмотрим машину Тьюринга M2=({ q0, q1, q2, qf}, {0, 1}, {0, 1, B}, δ, q0, B, { qf}). Неформально, но чётко опишите язык L(M2), если δ состоит из следующего множества правил:
a. δ(q0, 0)= (q1, 1, R); δ(q1, 1)= (q0, 0, R); δ(q1, B)= (qf, B, R);
b. δ(q0, 0)= (q1, B, R); δ(q0, 1)= (q1, B, R); δ(q1, 1)= (q1, B, R); δ(q1, B)= (qf, B, R).
4. Запишите следующие цепочки:
a. w37;
b. w100.
5. Запишите один из возможных кодов машины Тьюринга M1.
Приложение
Машина Тьюринга – M1, допускающая {0n1n | n≥1}
M1=({ q0, q1, q2, q3, q4}, {0, 1}, {0, 1, X, Y, B}, δ, q0, B, { q4})
0 1 X Y B
q0 (q1, X, R) - - (q3, Y, R) -
q1 (q1, 0, R) (q2, Y, L) - (q1, Y, R) -
q2 (q2, 0, L) - (q0, X, R) (q2, Y, L) -
q3 - - - (q3, Y, R) (q4, B, R)
q4 - - - - -
Заранее благодарю.