Помогите разобраться с машиной Тьюринга:

[Mariya233]

Дана строка из букв a и b. Разработайте машину Тьюринга, которая переместит все буквы a в левую, а буквы b в правую часть строки. Каретка находится над крайним левым символом строки.

[maxmatem]

а буквы на ленте вперемешку?
какой у вас алфавит?Наверное такой $% MathType!Translator!2!1!AMS LaTeX.tdl!TeX -- AMS-LaTeX! \[ A = \left\{ {a_0 ,a,b} \right\} \] % MathType!End!2!1! $

[Mariya233]

Да буквы вперемешку!

-- Сб апр 24, 2010 22:06:43 --

Алфавит можно расширять в процессе решения, главное, чтобы в итоге было aaaaaabbbbb или что типа этого.

[maxmatem]

как-то странно ведь, лента бесконечна в обе стороны! вы точно правильно сформулировали задачу? приведите пример фрагмента ленты! в стандартной конфигурации

[Maslov]

Как конец строки определить? В "пустой" ячейке какой символ находится?

[maxmatem]

может у вас всё-таки слова на ленте заданы! а то как заметил Maslov и конца строки нам не видать!

[Mariya233]

Мы должны реализовать алгоритм в algo2000.

-- Сб апр 24, 2010 22:16:38 --

Пустая клетка _

-- Сб апр 24, 2010 22:18:51 --

Задача точно верно сформулирована!!!

[maxmatem]

Mariya233
давайте сначала определимся с условиями задачи! честно говоря то как вы сформулировали не понятно как подойти так как не ясно как ограничения на строку поставить!

[Mariya233]

Все что я знаю - это: пустой символ-нижнее подчеркивание, начальное состояние крайняя правая клетка. Больше я, к сожалению, никакой информацией не располагаю. Условие точное.

[maxmatem]

если заданы два слова например так $% MathType!Translator!2!1!AMS LaTeX.tdl!TeX -- AMS-LaTeX! \[ abbaa_0 babaa \] % MathType!End!2!1! $
тогда ясно! в журнале квант за 1977 год выпуск 2 , статья алгоритмы на словах! почитайте может поможет!

[Mariya233]

спасибо

[Maslov]

Предлагаю сортировать пузырьком: едем вправо; как только встречаем инверсию $ba$, меняем буквы местами; доехав до конца, возвращаемся в начало; завершаем работу, если при движении вдоль строки не было встречено ни одной инверсии.

[Maslov]

А еще проще за каждый проход убирать только одну инверсию: едем вправо; как только встречаем инверсию $ba$, меняем буквы местами и возвращаемся в начало. В этом случае достижение конца слова означает завершение работы программы.

[Mariya233]

Скажите, пожалуйста, как реализовать это с помощью algo2000.

-- Вс апр 25, 2010 09:51:45 --

Спасибо вам за участие, я решила эту задачу.