задача по машине Тьюринга и нормальным алгоритмам(алгорифмам) Маркова
1. На ленте машины Тьюринга находится целое положительное число, записанное в десятичной системе счисления. Найдите произведение этого числа на число 11. Каретка обозревает крайнюю правую цифру числа. (построить машину Тьюринга)
я представляю, как это должно выглядеть(слева 1-ая цифра, справа 2-ая цифра и между ними их сумма), но как написать- не знаю.
2. И по нормальному алгоритму Маркова: дан алфавит A={a,b,c}. В непустом слове P оставить только последний символ.
Помогите, пожалуйста :)
я представляю, как это должно выглядеть(слева 1-ая цифра, справа 2-ая цифра и между ними их сумма), но как написать- не знаю.
2. И по нормальному алгоритму Маркова: дан алфавит A={a,b,c}. В непустом слове P оставить только последний символ.
Помогите, пожалуйста :)
Марков:
"abc" -> "c"
"bac" -> "c"
"bca" -> "a"
"cba" -> "a"
"cab" -> "b"
"acb" -> "b"
"aa" -> "a"
"bb" -> "b"
"cc" -> "c"
"bc" -> "c"
"ba" -> "a"
"ca" -> "a"
"cb" -> "b"
"ab" -> "b"
"ac" -> "c"
"bc" -> "c"
"bac" -> "c"
"bca" -> "a"
"cba" -> "a"
"cab" -> "b"
"acb" -> "b"
"aa" -> "a"
"bb" -> "b"
"cc" -> "c"
"bc" -> "c"
"ba" -> "a"
"ca" -> "a"
"cb" -> "b"
"ab" -> "b"
"ac" -> "c"
"bc" -> "c"
Проверить можно тут.
я представляю, как это должно выглядеть(слева 1-ая цифра, справа 2-ая цифра и между ними их сумма), но как написать- не знаю.
Посмотри примеры кода на BrainFuck, это должно натолкнуть на реализацию.
А с Марковым нужно подумать.
C машиной Тьюринга много писать придётся.
Значит, так:
Лента 0000|______|0000. В обе стороны бесконечна и там находятся нули. Поскольку в условии нет ограничений на алфавит, то пусть алфавитом будут все буквы латинского и цифры от 0 до 9.
Слева на ленте ставится маркер начала ленты. Он не обязателен, просто так легче ориентироваться, пусть будет 'y': 0000|y____|0000.
Дале понадобится множитель - 11: 0000|y11____|0000.
Нужно как-то обозначить, что 11 - это количество сложений числа с самим собой, а не ответ или само число. Пусть меткой будет символ 'x': 0000|y11x___|0000
А все остальное место отведём под ответ.
Увы, величина ответа не может не быть ограниченной.
Ограничим её, например, 3-мя цифрами, для этого понадобится ещё один маркер - 'z': 0000|y11x___z|0000
А дальше задача заключается в том, чтобы написать кучу правил.
Начинаем идти слева на право пока не встретим символ 'x'. После этого символа смещаемся влево на 1 позицию, то есть, начинаем смотреть, сколько ещё сложений нужно произвести. Думаю, как вычитать из числа по 1 ты сам напишешь. Так вот, до тех пор, пока машина не натыкается на символ y, уменьшаем 11 на 1. Как прибавить к числу произвольное, думаю, тоже сам разберёшься. Уменьшаешь 11 на 1 и идёшь вправо, пока не наткнёшься на символ 'z'. Как наткнёшься, прибавляй к числу 2. Выполнил сложений? Передвигай каретку влево до символа 'x'. И так до тех пор, пока между 'x' и 'y' не будут нули. А если ты верно напишешь вычитание, то в тот момент, когда вместо 11 будет два нуля, ты снова перейдёшь на ячейку с 'y'. Останется только перейти в состояние, которое сотрёт y11x и z, а на поле останется только ответ. 'z' нужно стирать в последнюю очередь, что и будет остановом.
Значит, так:
Лента 0000|______|0000. В обе стороны бесконечна и там находятся нули. Поскольку в условии нет ограничений на алфавит, то пусть алфавитом будут все буквы латинского и цифры от 0 до 9.
Слева на ленте ставится маркер начала ленты. Он не обязателен, просто так легче ориентироваться, пусть будет 'y': 0000|y____|0000.
Дале понадобится множитель - 11: 0000|y11____|0000.
Нужно как-то обозначить, что 11 - это количество сложений числа с самим собой, а не ответ или само число. Пусть меткой будет символ 'x': 0000|y11x___|0000
А все остальное место отведём под ответ.
Увы, величина ответа не может не быть ограниченной.
Ограничим её, например, 3-мя цифрами, для этого понадобится ещё один маркер - 'z': 0000|y11x___z|0000
А дальше задача заключается в том, чтобы написать кучу правил.
Начинаем идти слева на право пока не встретим символ 'x'. После этого символа смещаемся влево на 1 позицию, то есть, начинаем смотреть, сколько ещё сложений нужно произвести. Думаю, как вычитать из числа по 1 ты сам напишешь. Так вот, до тех пор, пока машина не натыкается на символ y, уменьшаем 11 на 1. Как прибавить к числу произвольное, думаю, тоже сам разберёшься. Уменьшаешь 11 на 1 и идёшь вправо, пока не наткнёшься на символ 'z'. Как наткнёшься, прибавляй к числу 2. Выполнил сложений? Передвигай каретку влево до символа 'x'. И так до тех пор, пока между 'x' и 'y' не будут нули. А если ты верно напишешь вычитание, то в тот момент, когда вместо 11 будет два нуля, ты снова перейдёшь на ячейку с 'y'. Останется только перейти в состояние, которое сотрёт y11x и z, а на поле останется только ответ. 'z' нужно стирать в последнюю очередь, что и будет остановом.
за Маркова спасибо большое)
а с Тьюрингом суть ясна, но как-то надо без букв. Додумаю)
благодарю.
а с Тьюрингом суть ясна, но как-то надо без букв. Додумаю)
благодарю.