АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Задача 6. Решение этой задачи обычно вызывает у школьников затруднение

Читайте также:
  1. C) Любой код может быть вирусом для строго определенной среды (обратная задача вируса)
  2. БУДУЩЕЕ – ПЕРЕД ВАМИ СТОИТ НЕЛЕГКАЯ ЗАДАЧА. В ОДИНОЧКУ ВЫ С НЕЙ НЕ СПРАВИТЕСЬ.
  3. Вопрос 10. Задача
  4. Вопрос 18. Задача
  5. Вопрос 24. Задача
  6. Вопрос 26. Задача
  7. Вопрос 36. Задача
  8. Вопрос 38. Задача
  9. Вопрос 40. Задача
  10. Вопрос 42. Задача
  11. Вопрос 6. Задача
  12. Задача 1

Решение этой задачи обычно вызывает у школьников затруднение. При разборе решения этой задачи можно пойти, например, следующим путем.

Рассмотрите со школьниками следующие варианты входных слов и попросите их сформулировать, что должна делать машина Тьюринга, каков внешний вид выходного слова, чем с точки зрения машины Тьюринга эти варианты различаются:

aaa —> выходное слово совпадает с входным, просматриваем входное слово до тех пор, пока оно не заканчивается.

a —> выходное слово совпадает с входным, просматриваем входное слово до тех пор, пока оно не заканчивается.

bbb —> выходное слово совпадает с входным, просматриваем входное слово до тех пор, пока оно не заканчивается.

b —> выходное слово совпадает с входным, просматриваем входное слово до тех пор, пока оно не заканчивается.

ab —> выходное слово совпадает с входным, просматриваем входное слово до тех пор, пока оно не заканчивается.

Результат обсуждения. Машина Тьюринга должна “понимать”, по цепочке каких букв она идет, т.е. у нее должно быть как минимум два состояния. Пусть состояние q 1 — движение по цепочке из букв “ a ”, а q 2 — состояние движения по цепочке из букв “ b ”. Заметим, что цепочка может состоять и из одной буквы. Если мы дошли до конца строки в состоянии q 1 или q 2, т.е. встретили a 0, машина должна остановиться, мы обработали всю строку.

Рассмотрим следующие варианты входных слов:

bba —> abb

bbbaab —> aabbbb

aabbbaab —> aaaabbbb

Результат обсуждения. Первый вариант входного слова можно последовательно обработать следующим образом: bba —> bbb —> вернуться к левому концу цепочки из букв “ b ” —> abb (заменить первую букву в этой цепочке на “ a ”). Для выполнения этих действий нам потребуется ввести два новых состояния и, кроме того, уточнить состояние q 2. Таким образом, для решения этой задачи нам нужно построить машину Тьюринга со следующими состояниями:

q 1 — идем вправо по цепочке букв “ a ”. Если цепочка заканчивается a 0, то переходим в q 0; если заканчивается буквой “ b ”, то переходим в q 2;

q 2 — идем вправо по цепочке букв “ b ”, если цепочка заканчивается a 0, то переходим в q 0; если заканчивается “ a ”, то заменяем букву “ a ” на “ b ”, переходим в состояние q 3 (цепочку вида заменили на цепочку вида );

q 3 — идем влево по цепочке букв “ b ” до ее левого конца. Если встретили a 0 или “ a ”, то переходим в q 4;

q 4 — заменяем “ b ” на “ a ” и переходим в q 1 (цепочку вида заменяем на цепочку вида .


1 | 2 | 3 | 4 | 5 | 6 | 7 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)