2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Помогите разобраться с машиной Тьюринга:
Сообщение24.04.2010, 20:57 


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

 Профиль  
                  
 
 Re: Помогите разобраться с машиной Тьюринга:
Сообщение24.04.2010, 21:02 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Помогите разобраться с машиной Тьюринга:
Сообщение24.04.2010, 21:04 


24/04/10
8
Да буквы вперемешку!

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

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

 Профиль  
                  
 
 Re: Помогите разобраться с машиной Тьюринга:
Сообщение24.04.2010, 21:08 
Аватара пользователя


15/08/09
1465
МГУ
как-то странно ведь, лента бесконечна в обе стороны! вы точно правильно сформулировали задачу? приведите пример фрагмента ленты! в стандартной конфигурации

 Профиль  
                  
 
 Re: Помогите разобраться с машиной Тьюринга:
Сообщение24.04.2010, 21:11 
Заслуженный участник


09/08/09
3438
С.Петербург
Как конец строки определить? В "пустой" ячейке какой символ находится?

 Профиль  
                  
 
 Re: Помогите разобраться с машиной Тьюринга:
Сообщение24.04.2010, 21:14 
Аватара пользователя


15/08/09
1465
МГУ
может у вас всё-таки слова на ленте заданы! а то как заметил Maslov и конца строки нам не видать!

 Профиль  
                  
 
 Re: Помогите разобраться с машиной Тьюринга:
Сообщение24.04.2010, 21:15 


24/04/10
8
Мы должны реализовать алгоритм в algo2000.

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

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

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

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

 Профиль  
                  
 
 Re: Помогите разобраться с машиной Тьюринга:
Сообщение24.04.2010, 21:19 
Аватара пользователя


15/08/09
1465
МГУ
Mariya233
давайте сначала определимся с условиями задачи! честно говоря то как вы сформулировали не понятно как подойти так как не ясно как ограничения на строку поставить!

 Профиль  
                  
 
 Re: Помогите разобраться с машиной Тьюринга:
Сообщение24.04.2010, 21:22 


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

 Профиль  
                  
 
 Re: Помогите разобраться с машиной Тьюринга:
Сообщение24.04.2010, 21:27 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Помогите разобраться с машиной Тьюринга:
Сообщение24.04.2010, 21:28 


24/04/10
8
спасибо

 Профиль  
                  
 
 Re: Помогите разобраться с машиной Тьюринга:
Сообщение24.04.2010, 21:38 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Помогите разобраться с машиной Тьюринга:
Сообщение24.04.2010, 23:40 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Помогите разобраться с машиной Тьюринга:
Сообщение25.04.2010, 08:38 


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

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 14 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group