@Eveigh

Здравствуйте, я не могу разобраться, как переписать числовой массив, отступающий на две клетки вправо от исходного. Прошу помочь.
Должно получиться что-то типа: (a0 1 2 3 a0) => (a0 1 2 3 * * 1 2 3 a0).
Или : (a0 1 2 3 a0) => (a0 * * 1 2 3 a0)
Пожалуйста помогите.
можно использовать для примера любые системы счисления.

Вот точное условие задания:
На ленте напечатан массив символов, состоящий из элементов. Составить программу для машины Тьюринга, которая строит массив, равный данному и отстоящий от него вправо на две неотмеченные ячейки.

0

@Sindbad_M

Задача копирования строки записанной на ленте не сложная - запоминаем символ в состоянии машины, заменяем его служебным символом чтобы найти точку разделяющую скопированную и нескопрированную части строки и тащим на нужное место, затем возвращаемся, восстанавливаем символ, запоминаем и стираем следующий и т.д.

Это общий подход. А вот ваши частности я не понял:

Во-первых это ерунда, т.к. входная строка должна однозначно определять выходную, а у вас для одной и той же входной строки две различных выходных.

2. Что такое "а0"? Это два разных символа или один? У него какое-то особое предназначение?

3. Пробелы в строках только для наглядности, они не соответствуют пустым ячейкам? Пустые ячейки обозначены "*" ?

0

@Eveigh

Пробелы для наглядности, "а0" - это пустая клетка, а "*" - это символ не входящий в алфавит. Я пробовал вариант с заменой символа но преподаватель отверг его и сказал, что машина не имеет памяти и не может различить, какой символ я менял, а я должен вычитать из числа по единице и переносить его на место после двух "*". А мои примеры это то ,что, как она сказала мне, должно получиться. Но я не понимаю, почему моё вариант неверный, и что тогда мне необходимо сделать. Т.е. она сказала мне, что я должен вычитать из числа по единице и получить два таких числа, между которыми две "*", или одно число, равное исходному, но перенесённое после двух "*". Если необходимо, то я могу прислать мой первоначальный вариант решения.

0

@Sindbad_M

Eveigh, вы меня пугаете.

1. Базовым условием задачи от которого отталкиваемся было:
т.е. остальное должно пояснять, но никак не противоречить этому условию. "неотмеченные ячейки" это обычно пустые ячейки, т.е. ячейки не содержащие вообще никаких символов. Вдруг оказывается, что
Т.е. ячейка не просто не пустая, а содержащая какой-то таинственный символ. Но в какой алфавит он не входит? И сколько вообще этих алфавитов?

2. Еще более непонятно. Ваше решении работало? Если да, то преподаватель должен был задать входную строчку которую ваша МТ обработает некорректно. Если нет, то зачем вы пытались сдать нерешенную работу? Вы что сами свое собственное решение не тестировали?

В общем, как обычно. Для того чтобы понять условие задачи (что именно должна делать МТ) приведите побольше примеров входных и выходных строк. Не как в первом сообщении, а корректно, на одну входную строку должно быть ровно по одной выходной. Крайние пустые ячейки обозначать не надо, все и так знают, что лента бесконечна в обе стороны и все остальные ячейки пустые. Обозначайте только те пустые ячейки, которые находятся внутри входной и выходной строк.

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

0

@Eveigh

Я тут посмотрел своё старое "решение", и преподаватель оттолкнул моё решение из-за того, что оно работало только для буквенного алфавита со строчными буквами. Пустые ячейки отмечены звёздочками, так как преподаватель сказал, что между массивами не может быть пустых ячеек. А примеры лент вот. Пробелы для наглядности а пустые ячейки обозначу звёздочками.
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

@Sindbad_M

Так для какого же алфавита должно работать решение? Если для {0,1,...,8,9,a,b,c,...,x,y,z,A,B,C,...,X,Y,Z}, то это не задача, а издевательство. И не ждите чуда, пока вы не выясните у преподавателя точное задание, помочь вам никто не сможет.
Вы и преподаватель точно одну и ту же задачу имеете в виду?

Показывайте ваше решение для алфавита с строчными буквами.

0

@Eveigh

Преподаватель сказал, что если мне будет сложно, то сделать машину лишь для числового массива в любой системе счисления, т.е. алфавит состоит только из чисел. А так как она сказала, что между массивами не может быть пустых клеток, то надо вписать в них любой символ, не входящий в алфавит(но мне кажется ,что это бред и не обязательно к выполнению). Файл эмулятора в архиве. Там программа копирует массив из двух символов, но без отступа и потом не останавливается((

Вложения

2.7z (221 байт, 2 просмотров)

0

@Sindbad_M

Во-первых ваша машина не работает, т.е. совсем не работает. Я задал для примера строчку "abba", ничего похожего ни на "abbaabba", ни на "abba**abba" на ленте не появилось. Идея копировать массив "из двух символов" порочная изначально. По смыслу таких задач, программа должна корректно обрабатывать массив абсолютно любой длины. Вероятнее всего, именно это и не понравилась преподавателю. Вернитесь к моему первому сообщению, там описан общий алгоритм для таких задач.

0

@Eveigh

Я пересмотрел своё решение. Как думаете, оно правильное?

Вложения

2.7z (428 байт, 10 просмотров)

0

@Sindbad_M

Не совсем.
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

@Eveigh

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

0

@Sindbad_M

Хватит уже бояться машины Тьюринга, все что можно сформулировать в виде словесного алгоритма легко превратить в программу для неё. {a,b} у вас качественно написано, две "*" добавляются минимальными правками:
1_1.zip
откорректированы только по одной ячейки у состояний q₁ и q₂, добавлено состояние q₇

1

@Eveigh

Т.е. получается типа этого?

Вложения

машина Тьюринга.7z (432 байт, 52 просмотров)

0

@Sindbad_M

да.

1