0 / 0 / 0
Регистрация: 19.11.2016
Сообщений: 33
|
|
1 | |
Программа для машины Тьюринга, которая строит массив, равный данному и отстоящий от него вправо на две ячейки03.01.2017, 12:54. Показов 5271. Ответов 13
Здравствуйте, я не могу разобраться, как переписать числовой массив, отступающий на две клетки вправо от исходного. Прошу помочь.
Должно получиться что-то типа: (a0 1 2 3 a0) => (a0 1 2 3 * * 1 2 3 a0). Или : (a0 1 2 3 a0) => (a0 * * 1 2 3 a0) Пожалуйста помогите. можно использовать для примера любые системы счисления. Вот точное условие задания: На ленте напечатан массив символов, состоящий из элементов. Составить программу для машины Тьюринга, которая строит массив, равный данному и отстоящий от него вправо на две неотмеченные ячейки.
0
|
03.01.2017, 12:54 | |
Ответы с готовыми решениями:
13
Написать программу для Машины Тьюринга, сдвигающую входное слово на заданное число k ячеек вправо Задача по машине Поста и Тьюринга: Необходимо найти сумму чисел задданых в виде меток(для машины Поста) или единиц( для машины Тьюринга) Программа для Машины Тьюринга Программа для работы машины Тьюринга |
456 / 385 / 117
Регистрация: 23.05.2016
Сообщений: 1,547
|
|
03.01.2017, 15:30 | 2 |
Задача копирования строки записанной на ленте не сложная - запоминаем символ в состоянии машины, заменяем его служебным символом чтобы найти точку разделяющую скопированную и нескопрированную части строки и тащим на нужное место, затем возвращаемся, восстанавливаем символ, запоминаем и стираем следующий и т.д.
Это общий подход. А вот ваши частности я не понял: Во-первых это ерунда, т.к. входная строка должна однозначно определять выходную, а у вас для одной и той же входной строки две различных выходных. 2. Что такое "а0"? Это два разных символа или один? У него какое-то особое предназначение? 3. Пробелы в строках только для наглядности, они не соответствуют пустым ячейкам? Пустые ячейки обозначены "*" ?
0
|
0 / 0 / 0
Регистрация: 19.11.2016
Сообщений: 33
|
|
04.01.2017, 22:24 [ТС] | 3 |
Пробелы для наглядности, "а0" - это пустая клетка, а "*" - это символ не входящий в алфавит. Я пробовал вариант с заменой символа но преподаватель отверг его и сказал, что машина не имеет памяти и не может различить, какой символ я менял, а я должен вычитать из числа по единице и переносить его на место после двух "*". А мои примеры это то ,что, как она сказала мне, должно получиться. Но я не понимаю, почему моё вариант неверный, и что тогда мне необходимо сделать. Т.е. она сказала мне, что я должен вычитать из числа по единице и получить два таких числа, между которыми две "*", или одно число, равное исходному, но перенесённое после двух "*". Если необходимо, то я могу прислать мой первоначальный вариант решения.
0
|
456 / 385 / 117
Регистрация: 23.05.2016
Сообщений: 1,547
|
|
05.01.2017, 00:02 | 4 |
Eveigh, вы меня пугаете.
1. Базовым условием задачи от которого отталкиваемся было: т.е. остальное должно пояснять, но никак не противоречить этому условию. "неотмеченные ячейки" это обычно пустые ячейки, т.е. ячейки не содержащие вообще никаких символов. Вдруг оказывается, что Т.е. ячейка не просто не пустая, а содержащая какой-то таинственный символ. Но в какой алфавит он не входит? И сколько вообще этих алфавитов? 2. Еще более непонятно. Ваше решении работало? Если да, то преподаватель должен был задать входную строчку которую ваша МТ обработает некорректно. Если нет, то зачем вы пытались сдать нерешенную работу? Вы что сами свое собственное решение не тестировали? В общем, как обычно. Для того чтобы понять условие задачи (что именно должна делать МТ) приведите побольше примеров входных и выходных строк. Не как в первом сообщении, а корректно, на одну входную строку должно быть ровно по одной выходной. Крайние пустые ячейки обозначать не надо, все и так знают, что лента бесконечна в обе стороны и все остальные ячейки пустые. Обозначайте только те пустые ячейки, которые находятся внутри входной и выходной строк. Пока не надо. Без ясности с условием задачи любые варианты решения бесполезны. А потом да, показывайте, только не фотографией из тетрадки, а файлом для эмулятора.
0
|
0 / 0 / 0
Регистрация: 19.11.2016
Сообщений: 33
|
|
05.01.2017, 10:35 [ТС] | 5 |
Я тут посмотрел своё старое "решение", и преподаватель оттолкнул моё решение из-за того, что оно работало только для буквенного алфавита со строчными буквами. Пустые ячейки отмечены звёздочками, так как преподаватель сказал, что между массивами не может быть пустых ячеек. А примеры лент вот. Пробелы для наглядности а пустые ячейки обозначу звёздочками.
1 2 3 => 1 2 3 * * 1 2 3 a c b => a c b * * a c b 7 b A 8 F => 7 b A 8 F * * 7 b A 8 F И преподаватель сказал, что если не получится получить на ленте 2 массива, то надо перенести на 2 ячейки вправо (эту фразу я сам не очень понял).
0
|
456 / 385 / 117
Регистрация: 23.05.2016
Сообщений: 1,547
|
|
05.01.2017, 14:46 | 6 |
Так для какого же алфавита должно работать решение? Если для {0,1,...,8,9,a,b,c,...,x,y,z,A,B,C,...,X,Y,Z}, то это не задача, а издевательство. И не ждите чуда, пока вы не выясните у преподавателя точное задание, помочь вам никто не сможет.
Вы и преподаватель точно одну и ту же задачу имеете в виду? Показывайте ваше решение для алфавита с строчными буквами.
0
|
0 / 0 / 0
Регистрация: 19.11.2016
Сообщений: 33
|
|
05.01.2017, 16:15 [ТС] | 7 |
Преподаватель сказал, что если мне будет сложно, то сделать машину лишь для числового массива в любой системе счисления, т.е. алфавит состоит только из чисел. А так как она сказала, что между массивами не может быть пустых клеток, то надо вписать в них любой символ, не входящий в алфавит(но мне кажется ,что это бред и не обязательно к выполнению). Файл эмулятора в архиве. Там программа копирует массив из двух символов, но без отступа и потом не останавливается((
0
|
456 / 385 / 117
Регистрация: 23.05.2016
Сообщений: 1,547
|
|
05.01.2017, 20:00 | 8 |
Во-первых ваша машина не работает, т.е. совсем не работает. Я задал для примера строчку "abba", ничего похожего ни на "abbaabba", ни на "abba**abba" на ленте не появилось. Идея копировать массив "из двух символов" порочная изначально. По смыслу таких задач, программа должна корректно обрабатывать массив абсолютно любой длины. Вероятнее всего, именно это и не понравилась преподавателю. Вернитесь к моему первому сообщению, там описан общий алгоритм для таких задач.
0
|
0 / 0 / 0
Регистрация: 19.11.2016
Сообщений: 33
|
|
06.01.2017, 11:54 [ТС] | 9 |
Я пересмотрел своё решение. Как думаете, оно правильное?
0
|
456 / 385 / 117
Регистрация: 23.05.2016
Сообщений: 1,547
|
|
06.01.2017, 12:41 | 10 |
Не совсем.
1. Строчку "aca" ваша программа не копирует, также как спотыкается на любых строчках содержащих "c" не последним символом. 2. А почему "*" одна, надо же две? В целом (после устранения указанных недостатков) задача решена для входных строк содержащих {a,b,c}. Если преподаватель будет настаивать на Переделайте её для входных строк из {0,1}, это числа в двоичной системе счисления. Другое дело, не слишком ли просто вы поняли условие? Получается что "массив" эквивалентен понятию "строка". Фактически вы копируете строку символов не содержащую пробелов (пустых ячеек). Не могло ли имется в виду что-то вроде такого: (101_11_110) => (101_11_110**101_11_110) (1_10)=>(1_10**1_10) (10100111_11_1111111_1_0_1111)=>(10100111_11_1111111_1_0_1111**10100111_11_11111 11_1_0_1111) Где "_" - пустая ячейка. ? Добавлено через 17 секунд Не совсем. 1. Строчку "aca" ваша программа не копирует, также как спотыкается на любых строчках содержащих "c" не последним символом. 2. А почему "*" одна, надо же две? В целом (после устранения указанных недостатков) задача решена для входных строк содержащих {a,b,c}. Если преподаватель будет настаивать на Переделайте её для входных строк из {0,1}, это числа в двоичной системе счисления. Другое дело, не слишком ли просто вы поняли условие? Получается что "массив" эквивалентен понятию "строка". Фактически вы копируете строку символов не содержащую пробелов (пустых ячеек). Не могло ли имется в виду что-то вроде такого: (101_11_110) => (101_11_110**101_11_110) (1_10)=>(1_10**1_10) (10100111_11_1111111_1_0_1111)=>(10100111_11_1111111_1_0_1111**10100111_11_11111 11_1_0_1111) Где "_" - пустая ячейка. ?
0
|
0 / 0 / 0
Регистрация: 19.11.2016
Сообщений: 33
|
|
06.01.2017, 12:46 [ТС] | 11 |
Преподаватель говорил, что массив сплошной и между символами никак не может быть пустых клеток. А как сделать так, чтобы было две * я не знаю.
0
|
456 / 385 / 117
Регистрация: 23.05.2016
Сообщений: 1,547
|
|
06.01.2017, 13:01 | 12 |
Сообщение было отмечено Eveigh как решение
Решение
Хватит уже бояться машины Тьюринга, все что можно сформулировать в виде словесного алгоритма легко превратить в программу для неё. {a,b} у вас качественно написано, две "*" добавляются минимальными правками:
1_1.zip откорректированы только по одной ячейки у состояний q1 и q2, добавлено состояние q7
1
|
0 / 0 / 0
Регистрация: 19.11.2016
Сообщений: 33
|
|
06.01.2017, 13:34 [ТС] | 13 |
Т.е. получается типа этого?
0
|
456 / 385 / 117
Регистрация: 23.05.2016
Сообщений: 1,547
|
|
06.01.2017, 13:50 | 14 |
да.
1
|
06.01.2017, 13:50 | |
06.01.2017, 13:50 | |
Помогаю со студенческими работами здесь
14
Написать программу для машины Поста, которая движется вправо, останавливается на последнем символе последовательности 11 Написать программу для машины Тьюринга, которая движется влево, останавливается на последнем символе последовательности Указатели: написать программу, которая по данному списку L строит два новых списка Программа машины Тьюринга Построить программу машины Тьюринга, которая будет вычислять функцию Описать процедуру, которая по одной очереди строит две новых - из положительных и остальных Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |