Дана машина Тьюринга с внешним алфавитом A={a0 1}. Бесплатный доступ к решению задач

Реферат.Справочник
Решенные задачи по другому
Дана машина Тьюринга с внешним алфавитом A={a0 1}

Дана машина Тьюринга с внешним алфавитом A={a0 1} .pdf

Зарегистрируйся в 2 клика в Кампус и получи неограниченный доступ к материалам с подпиской Кампус+ 🔥

Условие

Дана машина Тьюринга с внешним алфавитом A={a0,1}, алфавитом внутренних состояний Q={q0,q1,q2,q3,q4,q5,q6,q7} и со следующей функциональной схемой (программой): Изображая на каждом такте работы машины получающуюся конфигурацию, определите, в какое слово перерабатывает машина каждое из следующих слов, исходя из начального стандартного положения: б) 111111е) 1a0111a0a01111з) 11a0111

Нужно полное решение этой работы?

Решение

Потяни, чтобы посмотреть

Выписываем последовательность конфигураций машины при переработке ею слова из начального стандартного положения:
q1
q4
1)
1 1 1 1 1 1
13)
1 1 1 1
q2
q5
2)
1 1 1 1 1 1
14)
1 1 1
q3
q4
3)
1 1 1 1 1 1
15)
1 1 1
q1
q5
4)
1 1 1 1 1 1
16)
1 1
q2
q5
5)
1 1 1 1 1 1
17)
1 1
q2
q4
6)
1 1 1 1 1 1
18)
1 1
q3
q5
7)
1 1 1 1 1 1
19)
1
q1
q4
8)
1 1 1 1 1 1
20)
1
q4
q5
9)
1 1 1 1 1 1
21)
q5
q4
10)
1 1 1 1 1
22)
q4
q0
11)
1 1 1 1 1
23)
1
q5
12)
1 1 1 1
Итак, слово 111111 из начального стандартного положения перерабатывается машиной в слово 1.
е) Выписываем последовательность конфигураций машины при переработке ею слова 1a0111a0a01111 из начального стандартного положения:
q1
1)
1 a0 1 1 1 a0 a0 1 1 1 1
q2
2)
1 a0 1 1 1 a0 a0 1 1 1 1
q3
3)
1 a0 1 1 1 a0 a0 1 1 1 1
q1
4)
1 a0 1 1 1 a0 a0 1 1 1 1
q2
5)
1 a0 1 1 1 a0 a0 1 1 1 1
q6
6)
1 a0 1 1 1 a0 a0 1 1 1 1
q7
7)
1 a0 1 1 1 a0 a0 a0 1 1 1
q6
8)
1 a0 1 1 1 a0 a0 a0 1 1 1
q7
9)
1 a0 1 1 1 a0 a0 a0 a0 1 1
q6
10)
1 a0 1 1 1 a0 a0 a0 a0 1 1
q7
11)
1 a0 1 1 1 a0 a0 a0 a0 a0 1
q6
12)
1 a0 1 1 1 a0 a0 a0 a0 a0 1
q7
13)
1 a0 1 1 1 a0 a0 a0 a0 a0 a0
q6
14)
1 a0 1 1 1 a0 a0 a0 a0 a0 a0
q0
15)
1 a0 1 1 1 a0 a0 a0 a0 a0 a0 a0
Итак, слово 1a0111a0a01111 из начального стандартного положения перерабатывается машиной в слово 1a0111a0a0a0a0a0a0a0 или 1a0111.
з) Выписываем последовательность конфигураций машины при переработке ею слова 11a0111 из начального стандартного положения:
q1
q4
1)
1 1 a0 1 1 1
7)
1 1 a0 a0 1 1
q2
q5
2)
1 1 a0 1 1 1
8)
1 1 a0 a0 a0 1
q3
q4
3)
1 1 a0 1 1 1
9)
1 1 a0 a0 a0 1
q1
q5
4)
1 1 a0 1 1 1
10)
1 1 a0 a0 a0 a0
q4
q4
5)
1 1 a0 1 1 1
11)
1 1 a0 a0 a0 a0
q5
q0
6)
1 1 a0 a0 1 1
12)
1 1 a0 a0 a0 a0 1
Итак, слово 11a0111 из начального стандартного положения перерабатывается машиной в слово 11a0 a0 a0 a01.

50% задачи недоступно для прочтения

Переходи в Кампус, регистрируйся и получай полное решение

Получить задачу