Машина Тьюринга, поиск одинаковых слов на ленте

@alex_nik · Регистрация: 24.10.2017

Author24 — интернет-сервис помощи студентам

Помогите, пожалуйста, с заданием.

Реализовать машину Тьюринга со стандартной заключительной конфигурацией для выполнения следующей задачи. На вход подается множество слов в алфавите {a,b,c}, разделенных одним пустым символом. На выходе должно быть написано в двоичной системе количество одинаковых входных слов. Для каждого фрагмента программы необходимо дать подробное пояснение выполняемых действий.

Накидайте идей или литературы, где поискать. После недели работы, ничего толкового не получилось.

@Sindbad_M · 24.10.2017, 12:42

Литературу можно посмотреть по ссылкам на этой странице:
http://kpolyakov.spb.ru/prog/turing.htm
Начать рекомендую с этой методички:
http://kpolyakov.spb.ru/download/turmar.pdf

С машиной Тьюринга все просто, если можете описать алгоритм простыми словами, то и машину составить сможете.

Условие задачи у вас как-то неоднозначно сформулировано. В строке "aa bb aa bb aa" какое количество одинаковых входных слов?

@alex_nik · 24.10.2017, 13:32 **[ТС]**

Спасибо за литературу. Количество пар одинаковых слов.
Я пытаюсь сначала найти к первому слову подходяшую пару, но сложность возникает, что очень много состояний, а с итерациями построить не получается.

@Sindbad_M · 24.10.2017, 13:38

Сообщение от alex_nik

Количество пар одинаковых слов.

Все равно не понятно. В приведенной мной строке сколько пар одинаковых слов?

@alex_nik · 24.10.2017, 14:03 **[ТС]**

Мне вот тоже не совсем понятно, потому и не получается конструировать МТ. Я для себя в качестве способа поиска пар, решила найденные пары стирать. Тогда получается, что в Вашей записи две пары одинаковых слов.

@Sindbad_M · 24.10.2017, 15:40

Сообщение от alex_nik

Мне вот тоже не совсем понятно, потому и не получается конструировать МТ

Да, потому и не получается. Невозможно решить задачу, не понимая её условия. А как проверять правильность решения будете?

Сообщение от alex_nik

в качестве способа поиска пар, решила найденные пары стирать.

Если ищете пары, подход вполне рабочий. Где-то левее входной строки записываете число. При каждом удалении очередной пары увеличиваете число на 1. До тех пор пока входная строка не будет полностью стерта.

@alex_nik · 24.10.2017, 17:37 **[ТС]**

А как проверять правильность решения будете?

Использую Алго2000.
Слева вместо пробела я сразу поставила 0, чтобы потом увеличивать на 1 при поиске пар слов.
ДЛя слов из двух символов МТ работает, если символов больше, то состояний очень много. Хотелось бы построить итерацию, чтобы не вводить новых состояний, но получается ерунда.
Для итераций я пыталась заменять первые прочитанные символы в слове на пробелы. Вот например есть на ленте слова

0aac aab abc abb acb bba bbc aaa aac bba
Т.е. после второй итерации я получу на ленте, если ищу пары для слова aac
0c b bc bb cb bba bbc a c bba.
Вот здесь переход конечный вызывает затруднение.

Добавлено через 1 час 29 минут
И еще пример, где способ итераций работает неверно. Ищем пару для первого слова слева.
0abb abc bbac ab abb abc cba аb0
После двух итераций просто исчезла пара слов ab.

0b c bbac _ b c cba _0
Как тут быть?

@Sindbad_M · 24.10.2017, 18:05

Сообщение от alex_nik

А как проверять правильность решения будете? .

Использую Алго2000.

Я не про это. Если вы не понимаете условия, то не сможете определить, является ли полученный результат правильным решением задачи.

Обратите внимание, дальше обсуждается задача "подсчитать количество пар одинаковых слов", а не та о которой шла речь в первом сообщении.

Сообщение от alex_nik

ДЛя слов из двух символов МТ работает, если символов больше, то состояний очень много.

Подход в корне тупиковый. Нужно сразу думать надо алгоритмом не привязанным к длине слова. Более того, речь ведь не шла о том что все слова будут одинаковой длины.
Предлагаю такой алгоритм поиска пары одинаковых слов:
- ищем слово совпадающее с самым правым словом
- перед проверенными и несовпадающими словами ставим какой-нибудь значок, например "&"
Например, в данной строке слова "bbaa" и "aa" уже проверены, следующее подлежащее проверке слово "cbbc":
"0 abba bb aa abc cbbbс aa&bbaa&abc"
для поиска совпадающего слова заменяем поочередно маленькие буквы на большие до тех пор пока не найдем совпадение или расхождение. Если нашли расхождение, отмечаем очередное не совпавшее слово значком "&", возвращаем маленькие значки и начинаем сначала. Если совпадение найдено, увеличиваем счетчик, стираем пару, (при желании) упаковываем строку чтобы между словами был ровно один пробел, заменяем "&" на пробелы и начинаем поиск пары для самого правого слова:
0 abba bb aa abc cbbbс aa&bbaa&abc
0 abba bb aa abc cbbbс aa&bbaa&abС
0 abba bb aa abc cbbbС aa&bbaa&abС
0 abba bb aa abc cbbbС aa&bbaa&aBС
0 abba bb aa abc cbbBС aa&bbaa&aBС
0 abba bb aa abc cbbBС aa&bbaa&ABС
0 abba bb aa abc cbbbС aa&bbaa&ABС
0 abba bb aa abc cbbbc aa&bbaa&ABС
0 abba bb aa abc cbbbc&aa&bbaa&ABС
0 abba bb aa abc cbbbc&aa&bbaa&aBС
0 abba bb aa abc cbbbc&aa&bbaa&abС
0 abba bb aa abc cbbbc&aa&bbaa&abc
0 abba bb aa abc cbbbc&aa&bbaa&abC
0 abba bb aa abC cbbbc&aa&bbaa&abC
0 abba bb aa abC cbbbc&aa&bbaa&aBC
0 abba bb aa aBC cbbbc&aa&bbaa&aBC
0 abba bb aa aBC cbbbc&aa&bbaa&ABC
0 abba bb aa ABC cbbbc&aa&bbaa&ABC
1 abba bb aa ABC cbbbc&aa&bbaa&ABC
1 abba bb aa _BC cbbbc&aa&bbaa&ABC
1 abba bb aa __C cbbbc&aa&bbaa&ABC
1 abba bb aa ___ cbbbc&aa&bbaa&ABC
1 abba bb aa ___ cbbbc&aa&bbaa& BC
1 abba bb aa ___ cbbbc&aa&bbaa&__C
1 abba bb aa ___ cbbbc&aa&bbaa&
1 abba bb aa ___ cbbbc&aa&bbaa
1 abba bb aa c__ _bbbc&aa&bbaa
1 abba bb aa cb_ __bbc&aa&bbaa
1 abba bb aa cbb ___bc&aa&bbaa
1 abba bb aa cbbb____c&aa&bbaa
1 abba bb aa cbbbc____&aa&bbaa
1 abba bb aa cbbbc a_____a&bbaa
1 abba bb aa cbbbc aa_____&bbaa
1 abba bb aa cbbbc aa b_____baa
1 abba bb aa cbbbc aa bb_____aa
1 abba bb aa cbbbc aa bba_____a
1 abba bb aa cbbbc aa bbaa
и т.д.

@alex_nik · 24.10.2017, 18:44 **[ТС]**

Да, большие символы использовала в одной их версий :-)
Спасибо большое за объяснение.
Я начинала с левого края, и пыталась проверить сразу все слова в строке, помечая первую букву, затем вторую и т.д
Ваш алгоритм мне кажется проще. Большое спасибо за помощь!

Новые блоги и статьи
Книги и учебные ресурсы по C# InfoMaster 08.01.2025 Базовые учебники и руководства Одной из лучших книг для начинающих является "C# 10 и . NET 6 для начинающих" Эндрю Троелсена и Филиппа Джепикса . Книга последовательно раскрывает основные концепции. . .	Что такое NullReferenceException и как исправить? InfoMaster 08.01.2025 NullReferenceException - одно из самых распространенных исключений, с которым сталкиваются разработчики на C#. Это исключение возникает при попытке обратиться к членам объекта (методам, свойствам или. . .	Что такое Null Pointer Exception (NPE) и как это исправить? InfoMaster 08.01.2025 Null Pointer Exception (NPE) - это одно из самых распространенных исключений в Java, которое возникает при попытке использовать ссылку на объект, значение которой равно null. Это исключение относится. . .	Русский язык в консоли C++ InfoMaster 08.01.2025 При разработке программ на C++ одной из частых проблем, с которой сталкиваются русскоязычные программисты, является корректное отображение кириллицы в консольных приложениях. Эта проблема особенно. . .	Telegram бот на C# InfoMaster 08.01.2025 Разработка ботов для Telegram стала неотъемлемой частью современной экосистемы мессенджеров. C# предоставляет мощный и удобный инструментарий для создания разнообразных ботов, от простых. . .	Использование GraphQL в Go (Golang) InfoMaster 08.01.2025 Go (Golang) является одним из наиболее популярных языков программирования, используемых для создания высокопроизводительных серверных приложений. Его архитектурные особенности и встроенные. . .
Что лучше использовать при создании класса в Java: сеттеры или конструктор? Alexander-7 08.01.2025 Вопрос подробнее: На вопрос: «Когда одновременно создаются конструктор и сеттеры в классе – это нормально?» куратор уточнил: «Ваш класс может вообще не иметь сеттеров, а только конструктор и геттеры. . .	Как работать с GraphQL на TypeScript InfoMaster 08.01.2025 Введение в GraphQL и TypeScript В современной разработке веб-приложений GraphQL стал мощным инструментом для создания гибких и эффективных API. В сочетании с TypeScript, эта технология. . .	Счётчик на базе сумматоров + регистров и генератора сигналов согласования. Hrethgir 07.01.2025 Создан с целью проверки скорости асинхронной логики: ранее описанного сумматора и предополагаемых fast регистров. Регистры созданы на базе ранее описанного, предполагаемого fast триггера. То-есть. . .	Как перейти с Options API на Composition API в Vue.js BasicMan 06.01.2025 Почему переход на Composition API актуален В мире современной веб-разработки фреймворк Vue. js продолжает эволюционировать, предлагая разработчикам все более совершенные инструменты для создания. . .	Архитектура современных процессоров inter-admin 06.01.2025 Процессор (центральный процессор, ЦП) является основным вычислительным устройством компьютера, которое выполняет обработку данных и управляет работой всех остальных компонентов системы. Архитектура. . .	История создания реляционной модели баз данных, правила Кодда Programming 06.01.2025 Предпосылки создания реляционной модели В конце 1960-х годов компьютерная индустрия столкнулась с серьезными проблемами в области управления данными. Существовавшие на тот момент модели данных -. . .

@alex_nik 0 / 0 / 0 Регистрация: 24.10.2017 Сообщений: 6
		1
	Машина Тьюринга, поиск одинаковых слов на ленте 24.10.2017, 00:15. Показов 5460. Ответов 8 Метки нет (Все метки) Помогите, пожалуйста, с заданием. Реализовать машину Тьюринга со стандартной заключительной конфигурацией для выполнения следующей задачи. На вход подается множество слов в алфавите {a,b,c}, разделенных одним пустым символом. На выходе должно быть написано в двоичной системе количество одинаковых входных слов. Для каждого фрагмента программы необходимо дать подробное пояснение выполняемых действий. Накидайте идей или литературы, где поискать. После недели работы, ничего толкового не получилось. 0

@Sindbad_M 466 / 393 / 122 Регистрация: 23.05.2016 Сообщений: 1,580
	24.10.2017, 12:42	2
	Литературу можно посмотреть по ссылкам на этой странице: http://kpolyakov.spb.ru/prog/turing.htm Начать рекомендую с этой методички: http://kpolyakov.spb.ru/download/turmar.pdf С машиной Тьюринга все просто, если можете описать алгоритм простыми словами, то и машину составить сможете. Условие задачи у вас как-то неоднозначно сформулировано. В строке "aa bb aa bb aa" какое количество одинаковых входных слов? 0

@alex_nik 0 / 0 / 0 Регистрация: 24.10.2017 Сообщений: 6
	24.10.2017, 13:32 [ТС]	3
	Спасибо за литературу. Количество пар одинаковых слов. Я пытаюсь сначала найти к первому слову подходяшую пару, но сложность возникает, что очень много состояний, а с итерациями построить не получается. 0

@Sindbad_M 466 / 393 / 122 Регистрация: 23.05.2016 Сообщений: 1,580
	24.10.2017, 13:38	4
	Сообщение от alex_nik Количество пар одинаковых слов. Все равно не понятно. В приведенной мной строке сколько пар одинаковых слов? 0

@alex_nik 0 / 0 / 0 Регистрация: 24.10.2017 Сообщений: 6
	24.10.2017, 14:03 [ТС]	5
	Мне вот тоже не совсем понятно, потому и не получается конструировать МТ. Я для себя в качестве способа поиска пар, решила найденные пары стирать. Тогда получается, что в Вашей записи две пары одинаковых слов. 0

@Sindbad_M 466 / 393 / 122 Регистрация: 23.05.2016 Сообщений: 1,580
	24.10.2017, 15:40	6
	Сообщение от alex_nik Мне вот тоже не совсем понятно, потому и не получается конструировать МТ Да, потому и не получается. Невозможно решить задачу, не понимая её условия. А как проверять правильность решения будете? Сообщение от alex_nik в качестве способа поиска пар, решила найденные пары стирать. Если ищете пары, подход вполне рабочий. Где-то левее входной строки записываете число. При каждом удалении очередной пары увеличиваете число на 1. До тех пор пока входная строка не будет полностью стерта. 1

@alex_nik 0 / 0 / 0 Регистрация: 24.10.2017 Сообщений: 6
	24.10.2017, 17:37 [ТС]	7
	А как проверять правильность решения будете? Использую Алго2000. Слева вместо пробела я сразу поставила 0, чтобы потом увеличивать на 1 при поиске пар слов. ДЛя слов из двух символов МТ работает, если символов больше, то состояний очень много. Хотелось бы построить итерацию, чтобы не вводить новых состояний, но получается ерунда. Для итераций я пыталась заменять первые прочитанные символы в слове на пробелы. Вот например есть на ленте слова 0aac aab abc abb acb bba bbc aaa aac bba Т.е. после второй итерации я получу на ленте, если ищу пары для слова aac 0c b bc bb cb bba bbc a c bba. Вот здесь переход конечный вызывает затруднение. Добавлено через 1 час 29 минут И еще пример, где способ итераций работает неверно. Ищем пару для первого слова слева. 0abb abc bbac ab abb abc cba аb0 После двух итераций просто исчезла пара слов ab. 0b c bbac _ b c cba _0 Как тут быть? 0

@Sindbad_M 466 / 393 / 122 Регистрация: 23.05.2016 Сообщений: 1,580
	24.10.2017, 18:05	8
	Сообщение от alex_nik А как проверять правильность решения будете? . Использую Алго2000. Я не про это. Если вы не понимаете условия, то не сможете определить, является ли полученный результат правильным решением задачи. Обратите внимание, дальше обсуждается задача "подсчитать количество пар одинаковых слов", а не та о которой шла речь в первом сообщении. Сообщение от alex_nik ДЛя слов из двух символов МТ работает, если символов больше, то состояний очень много. Подход в корне тупиковый. Нужно сразу думать надо алгоритмом не привязанным к длине слова. Более того, речь ведь не шла о том что все слова будут одинаковой длины. Предлагаю такой алгоритм поиска пары одинаковых слов: - ищем слово совпадающее с самым правым словом - перед проверенными и несовпадающими словами ставим какой-нибудь значок, например "&" Например, в данной строке слова "bbaa" и "aa" уже проверены, следующее подлежащее проверке слово "cbbc": "0 abba bb aa abc cbbbс aa&bbaa&abc" для поиска совпадающего слова заменяем поочередно маленькие буквы на большие до тех пор пока не найдем совпадение или расхождение. Если нашли расхождение, отмечаем очередное не совпавшее слово значком "&", возвращаем маленькие значки и начинаем сначала. Если совпадение найдено, увеличиваем счетчик, стираем пару, (при желании) упаковываем строку чтобы между словами был ровно один пробел, заменяем "&" на пробелы и начинаем поиск пары для самого правого слова: 0 abba bb aa abc cbbbс aa&bbaa&abc 0 abba bb aa abc cbbbс aa&bbaa&abС 0 abba bb aa abc cbbbС aa&bbaa&abС 0 abba bb aa abc cbbbС aa&bbaa&aBС 0 abba bb aa abc cbbBС aa&bbaa&aBС 0 abba bb aa abc cbbBС aa&bbaa&ABС 0 abba bb aa abc cbbbС aa&bbaa&ABС 0 abba bb aa abc cbbbc aa&bbaa&ABС 0 abba bb aa abc cbbbc&aa&bbaa&ABС 0 abba bb aa abc cbbbc&aa&bbaa&aBС 0 abba bb aa abc cbbbc&aa&bbaa&abС 0 abba bb aa abc cbbbc&aa&bbaa&abc 0 abba bb aa abc cbbbc&aa&bbaa&abC 0 abba bb aa abC cbbbc&aa&bbaa&abC 0 abba bb aa abC cbbbc&aa&bbaa&aBC 0 abba bb aa aBC cbbbc&aa&bbaa&aBC 0 abba bb aa aBC cbbbc&aa&bbaa&ABC 0 abba bb aa ABC cbbbc&aa&bbaa&ABC 1 abba bb aa ABC cbbbc&aa&bbaa&ABC 1 abba bb aa _BC cbbbc&aa&bbaa&ABC 1 abba bb aa __C cbbbc&aa&bbaa&ABC 1 abba bb aa ___ cbbbc&aa&bbaa&ABC 1 abba bb aa ___ cbbbc&aa&bbaa& BC 1 abba bb aa ___ cbbbc&aa&bbaa&__C 1 abba bb aa ___ cbbbc&aa&bbaa& 1 abba bb aa ___ cbbbc&aa&bbaa 1 abba bb aa c__ _bbbc&aa&bbaa 1 abba bb aa cb_ __bbc&aa&bbaa 1 abba bb aa cbb ___bc&aa&bbaa 1 abba bb aa cbbb____c&aa&bbaa 1 abba bb aa cbbbc____&aa&bbaa 1 abba bb aa cbbbc a_____a&bbaa 1 abba bb aa cbbbc aa_____&bbaa 1 abba bb aa cbbbc aa b_____baa 1 abba bb aa cbbbc aa bb_____aa 1 abba bb aa cbbbc aa bba_____a 1 abba bb aa cbbbc aa bbaa и т.д. 0

@alex_nik 0 / 0 / 0 Регистрация: 24.10.2017 Сообщений: 6
	24.10.2017, 18:44 [ТС]	9
	Да, большие символы использовала в одной их версий :-) Спасибо большое за объяснение. Я начинала с левого края, и пыталась проверить сразу все слова в строке, помечая первую букву, затем вторую и т.д Ваш алгоритм мне кажется проще. Большое спасибо за помощь! 0