Приписать слева к слову p символ b машина тьюринга
Машина Тьюринга. Приписать слева к непустому слову P его первый символ
Машина Тьюринга. Приписать слева к слову P символ b
A=
Машина Тьюринга. Приписать справа к слову P символ bс
Помогите решить: A=
Составьте Нормальный алгоритм Маркова для следующих условий: A=
НАПИСАТЬ ПРОГРАММУ НА ЯЗЫКЕ С\С++. Составьте Нормальный алгоритм Маркова для следующих условий.
Совершенно уверен, что вам это не поможет. Нужно действовать в соответствии с рекомендацией из предыдущего сообщения.
Если учебника/лекций нет, начните вот с этого
Еще раз, полностью решенная задача (описание машины Тьюринга для решения поставленной задачи, программа машины Тьюринга) находится в сообщении № 4. Я не знаю, какими еще синонимами мне написать это простое утверждение.
Для решения задачи я не пользовался никакими программными или аппаратными средствами имитирующими работу машины Тьюринга, так что ни скриншота, ни фотографии делать не с чего. Да и не нужны для этой задачи никакие костыли, это же, как я и написал в первом сообщении, задача типа «Hello world».
Машина Тьюринга: Удалить из слова Р его второй символ, если такой есть
Машина Тьюринга 1. А=
Выяснить, применима ли машина Тьюринга T к слову P?
Почему мой ответ неверен? Выяснить, применима ли машина Тьюринга T к слову P. Если применима, то.
Решение задач. Машина Тьюринга
Написать программу на машине Тьюринга, прибавляющую число 2 к введенному числу.
Написать на машине Тьюринга программу, прибавляющую 3 к введенному числу.
Перенести первый символ непустого слова P в его конец. Алфавит : A=
Если первый символ – это a, то надо перейти в состояние q2, в котором автомат бежит вправо и записывает в конце a. Если же первым был символ b, тогда надо перейти в состояние q3, где делается всё то же самое, только в конце записывается символ b. Если же первым был символ c, тогда переходим в состояние q4, в котором автомат дописывает за входным словом символ c.
Для решения этой задачи предлагается выполнить следующие действия:
В противном случае уничтожить всё входное слово ( q 7 ).
Запомнить первый символ, стереть второй символ и установить на его месте первый.
Сдвиг символов осуществляется так: в очередной клетке записываем b (если в q 1 ) или c (если в q 2 ), переходим вправо и меняем состояние на q 1 (если в текущей клетке было записано b ) или на q 2 (если было записано c ), где осуществляется дальнейшая запись. Если в очередной клетке записано a или пробел, то записываем в нее запомненный символ и останавливаем программу.
После этого возвращаемся к началу входного слова.
Вначале записываем знак = за входным словом. Затем возвращаемся под первый символ входного слова.
Машина Тьюринга. Приписать справа к слову P символ bс
Машина Тьюринга. Приписать слева к слову P символ b
A=
Машина Тьюринга. Приписать слева к непустому слову P его первый символ
Помочь найти в интернете решение задачи. А=
Выяснить, применима ли машина Тьюринга T к слову P
Помогите решить задачу. Выяснить, применима ли машина Тьюринга T к слову P. Если применима, то.
red_bess, если вы внимательно посмотрите на другие темы в этом разделе, то увидите, что буквально через пару тем вниз уже создана тема с вашей задачей. Вообще-то правила форума предполагают, что перед созданием новой темы автор попробует найти ответ, например с помощью поиска. Однако и в предыдущей теме ответа (пока) никто не дал. Объясняю почему:
1. Нет собственных попыток решения или объяснения что именно непонятно.
2. Задача очень легкая. Это даже не задача, а простейший пример-упражнение на понимание того, что такое машина Тьюринга. Чтобы её решить достаточно внимательно прочитать любое описание МТ в учебнике/методичке.
Но сходу посылать человека читать конспекты несколько неприлично, а решать задачу уровня таблицы умножения желающих не нашлось, вот и нет ответов.
Выяснить, применима ли машина Тьюринга T к слову P?
Почему мой ответ неверен? Выяснить, применима ли машина Тьюринга T к слову P. Если применима, то.
Правила, когда применима машина Тьюринга к слову
Возник вопрос, применима ли машина Тьюринга к слову, если выполнение не останавливается? она в двух.
Выяснить, применима ли машина Тьюринга, заданная программой Р, к слову S
Что-то очень подозрительное с Машиной Тьюринга Здравствуйте! Нужно решить задачу, но не могу.
Лекция 3. Нормальные алгорифмы Маркова
Лекция 3. Нормальные алгорифмы Маркова
Рассмотрим примеры, в которых демонстрируются типичные приёмы составления НАМ. Для сокращения формулировки задач будем использовать следующие cоглашения:
– буквой Р будем обозначать входное слово;
– буквой А будем обозначать алфавит входного слова, т. е. набор тех символов, которые и только которые могут входить во входное слово Р (но в процессе выполнения НАМ в обрабатываемых словах могут появляться и другие символы).
Пример1 (вставка и удаление символов)
А=
Прежде всего отметим, что в НАМ, в отличие от машины Тьюринга, легко реализуются вставки и удаления символов. Вставка новых символов в слово – это замена некоторого подслова на подслово с бóльшим числом символов. Например, с помощью формулы bb→ddd два символа будут заменены на три символа. При этом не надо заботиться о том, чтобы предварительно освободить. Место для дополнительных символов, в НАМ слово раздвигается автоматически. Удаление же символов– это замена некоторого подслова на подслово с меньшим числом символов; например, удаление символа c реализуется формулой c→λ. При этом никаких пустых позиций внутри слова не появляется, сжатие слова в НАМ происходит автоматически. С учётом сказанного нашу задачу должен, казалось бы, решать такой НАМ:
Однако это не так. Проверим этот НАМ на входном слове abbcabbca (над стрелками указаны номера применённых формул, а в словах слева от стрелок подчёркнуты для наглядности те части, к которым были применены эти формулы):
abbcabbca →adddcabbca →adddcadddca →adddabbca →…
Как видно, заменив первое вхождение bb на ddd, этот НАМ не перешёл сразу к удалению символов c, а стал заменять и другие вхождения bb. Почему? Напомним, что на каждом шаге работы НАМ формулы подстановки всегда просматриваются сверху вниз начиная с первой из них. Поэтому, пока применима первая формула, она и будет применяться, блокируя доступ к остальным формулам. Этот означает, что в НАМ важен порядок перечисления формул подстановки.
Учтём это и переставим наши две формулы:
Проверим этот новый алгоритм на том же входном слове:
abbcabbca →abbabbca →abbabba →adddabba →adddaddda
Итак, НАМ сначала удалил все символы c и только затем заменил первое вхождение bb на ddd. Однако НАМ на этом не остановился и стал заменять остальные вхождения bb. Почему? Дело в том, что, пока применима хотя бы одна формула, НАМ продолжает свою работу. Но нам этого не надо, поэтому мы должны принудительно остановить НАМ после того, как он заменил первое вхождение bb. Вот для этого и нужны заключительные формулы подстановки, после применения которых НАМ останавливается. Следовательно, в нашем алгоритме обычную формулу bb→ddd надо заменить на заключительную формулу bb->.ddd:
Проверим наш НАМ ещё и на входном слове, в которое не входит bb:
К последнему слову(dab) неприменима ни одна формула, поэтому, согласно определению НАМ, алгоритм останавливается и это слово объявляется выходным.
А=
Задача решается с помощью НАМ, содержащего всего одну формулу:
Пока в слове P справа хотя бы от одного символа b есть символ a, эта формула будет переносить a налево от этого b. Формула перестает работать, когда справа от b нет ни одного a, это и означает, что все a оказались слева от b. Например:
babba →abbba →abbab →ababb →aabbb
Алгоритм остановился на последнем слове, т. к. к нему уже неприменима наша формула.
Этот и предыдущий примеры показывают, что в НАМ, в отличие от машины Тьюринга, легко реализуются перестановки, вставки и удаления символов. Однако в НАМ возникает другая проблема: как зафиксировать символ (подслово), который должен быть обработан? Рассмотрим эту проблему на следующем примере.
А=
Однако это неправильный алгоритм, в чём можно убедиться, применив его к слову bbaba:
Как видно, этот НАМ удалил не первый символ слова, а первое вхождение символа a, а это разные вещи. Данный алгоритм будет правильно работать, только если входное слово начинается с символа a. Ясно, что перестановка формул в этом НАМ не поможет, т. к. тогда он будет, напротив, неправильно Что делать? Надо как-то зафиксировать, пометить первый символ слова, например, поставив перед ним какой-либо знак, скажем *, отличный от символов алфавита слова. После этого уже можно с помощью формул вида *ξa (где ξ пробегает весь алфавит A) заменить этот знак и первый символ ξ слова на пусто и остановиться.
А как поставить* перед первым символом? Это реализуется формулой λ →*
Проверим его на том же входном слове:
bbaba →*bbaba →**bbaba →***bbaba →…
Как видно, этот алгоритм постоянно приписывает слева звёздочки. Почему? Напомним, что формула постановки с пустой левой частью применима всегда, поэтому наша формула(1) будет работать бесконечно, блокируя доступ к остальным формулам. Отсюда вытекает очень важное правило: если в НАМ есть формула с пустой левой частью, то её место– только в самом конце НАМ.
Казалось бы, всё в порядке. Однако это не так: наш алгоритм зациклится на пустом входном слове, т. к. постоянно будет применяться формула (3), а согласно условию задачи на таком слове НАМ должен остановиться. В чём причина этой ошибки? Дело в том, что мы ввели знак * для того, чтобы пометить первый символ слова, а затем уничтожить* и этот символ. Но в пустом слове нет ни одного символа, поэтому формулы (1) и (2) ни разу не сработают и постоянно будет выполняться формула (3). Следовательно, чтобы учесть случай пустого входного слова, надо после формул(1) и(2) записать ещё одну формулу, которая уничтожает «одинокую» звёздочку и останавливает алгоритм:
Вот теперь мы, наконец-то, составили правильный алгоритм.
Его также можно записать следующим образом:
При решении этой задачи мы использовали расширение алфавита A, которое можно записать следующим образом: B=A U (*).
Прежде чем перейти к следующим задачам, обобщим тот приём со звёздочкой, который мы использовали в примере 3.
Этот приём со спецзнаком следует запомнить, т. к. в НАМ он используется очень часто. Правда, остаётся ещё одна проблема: как спецзнак разместить рядом с нужным вхождением α? Следующие примеры показывают, как это делается.
Пример 4 (фиксация спецзнаком заменяемого символа)
А=<0,1,2,3>. Пусть Р – непустое слово. Трактуя его как запись неотрицательного целого числа в четверичной системе счисления, требуется получить запись этого же числа, но в двоичной системе.
Как известно, для перевода числа из четверичной системы в двоичную надо каждую четверичную цифру заменить на пару соответствующих ей двоичных цифр: 0→00, 1→01, 2→10, 3→11. Такая замена, казалось бы, реализуется следующим НАМ:
Но этот алгоритм неправильный, в чём можно убедиться на входном слове 0123:
Ошибка здесь в том, что после замены четверичной цифры на пару двоичных цифр уже никак нельзя отличить двоичные цифры от четверичных, поэтому наш НАМ начинает заменять и двоичные цифры. Значит, надо как-то отделить ту часть числа, в которой уже была произведена замена, от той части, где замены ещё не было. Для этого предлагается пометить слева спецзнаком * ту четверичную цифру, которая сейчас должна быть заменена на пару соответствующих двоичных цифр, а после того как такая замена будет выполнена, спецзнак нужно поместить перед следующей четверичной цифрой:
0123 →*0123 →00*123 →0001*23 →000110*3 →*
Как видно, слева от спецзнака всегда находится та часть числа, которая уже переведена в двоичный вид, а справа – часть, которую ещё предстоит заменить. Поэтому никакой путаницы между четверичными и двоичными цифрами уже не будет. Итак, спецзнак * сначала должен быть размещён слева от первой цифры четверичного числа, а затем он должен «перепрыгивать» через очередную четверичную цифру, оставляя слева от себя соответствующие ей двоичные цифры. В конце же, когда справа от * уже не окажется никакой цифры, спецзнак надо уничтожить и остановиться.
Как приписать* слева к входному слову и как уничтожить спецзнак с остановом, мы уже знаем по предыдущему примеру, а вот«перепрыгивание» звёздочки реализуется с помощью формул вида*α→βγ*, где α– четверичная цифра, а βγ– соответствующая ей пара двоичных цифр.
Итого, получаем следующий алгоритм перевода чисел из четверичной системы в двоичную:
*0→01*| *1→01* | *2→10* | *3→11* | * →. λ | λ →*
Проверим этот НАМ на входном слове 0123:
0123 →*0123 →00*123 →0001*23 →000110*3 →* →
Пример 5 (перемещение спецзнака) – рассмотрено на лекции
А=
Например: bbab →bbaba
Прежде всего напомним, что формула λ →a приписывает символ «a» слева к слову P, а не справа. Чтобы приписать «a» справа, надо сначала пометить конец слова. Для этого воспользуемся спецзнаком, который поместим в конец P, а затем заменим его на «a»:
Но как поместить спецзнак в конец слова? Делается это так: сначала спецзнак * приписываем слева к слову P, а затем «перегоняем» звёздочку через все буквы слова:
bbab →*bbab →b*bab →bb*ab →bba*b →bbab*
А как сделать такой перегон? Нетрудно заметить, что«перепрыгивание» звёздочки через какой-то символ ξ– это замена пары *ξ на пару ξ*, которая реализуется формулой *ξ→ξ*.
С учётом всего сказанного получаем следующий НАМ:
Отметим, что при пустом входном слове этот НАМ сначала введёт звёздочку, а затем тут же заменит её на символ «a» и остановится.
Пример 6 (смена спецзнака)
А=
Например: bababb →babaabb
Удвоение символа a реализуется формулой a→aa. Но чтобы она применялась не к первому вхождению символа «a», а к последнему, надо поставить, скажем, справа от последнего символа «a» спецзнак * и применить формулу a* →.aa.
Теперь посмотрим, как поместить* рядом с последним вхождением символа «a». Поскольку последнее вхождение– это первое вхождение от конца, то предлагается сначала приписать * слева к слову P, затем перегнать * в конец слова(это мы уже умеем делать), а далее перегнать* справа налево через символы b до ближайшего символа a. Кроме того, надо учесть, что в Р может и не быть символа a; поэтому, если звёздочка снова достигнет начала слова, её надо уничтожить и остановиться.
Реализуем эту идею в виде следующего НАМ:
Здесь формула(6) приписывает* слева к входному слову P, формулы (1) и (2) перегоняют * в конец P, после чего формула(3) перемещает* справа налево через все b в конце слова до ближайшего, т. е. последнего, символа «a», и, наконец, формула(4) заменяет этот символ на aa и останавливает алгоритм. Формула же (5) нужна для входных слов, в которые не входит a. Проверим этот алгоритм на входном слове bababb.
bababb →*bababb→…→ bababb* →babab*b →bababb* →babab*b →…
Как видно, вместо того, чтобы двигаться справа влево до ближайшего символа «a», звёздочка начала «прыгать» вокруг последнего символа слова. Почему? Дело в том, что формулы (1) и (2), перегоняющие* вправо, мешают формуле(3), перегоняющей * влево. Отметим, что перестановка этих формул не поможет, т. к. тогда * начнёт «плясать» вокруг первого символа входного слова.
Что делать? Ошибка произошла из-за того, что мы используем спецзнак * в двух разных целях – как для движения вправо, так и для движения влево. Так вот, чтобы этой ошибки не было, надо просто ввести еще один спецзнак, скажем #, распределив между этими спецзнаками обязанности: пусть* движется вправо, а # – влево. Появиться же спецзнак # должен тогда, когда * дойдет до конца слова, т. е. когда справа от * не окажется других символов. Такая замена спецзнака «исключит из игры» все формулы со звёздочкой в левой части, поэтому они уже не будут мешать формулам со спецзнаком #. Если так и сделать, то получим следующий НАМ:
Проверим этот алгоритм на прежнем входном слове:
bababb →*bababb →…→bababb* →bababb# →babab#b →baba#bb→ babaabb
Если же во входное слово не входит символ a, тогда имеем:
bb →*bb →b*b →bb* →bb# →b#b →#bb →abb
Пример 7 (перенос символа через слово)
А=
Например: bbaba →babab
Для решения этой задачи предлагается выполнить следующие действия.
1. Помечаем первый символ слова P спецзнаком *.
2. Заменяем * и этот символ на новый символ: a на A, b на B. Этим мы фактически вводим два новых спецзнака A и B, которые нужны, чтобы отличить первый символ слова от остальных символов при его переносе в конец слова.
3. Перегоняем новый символ A или B через все символы слова P в его конец.
Такое перемещение реализуется аналогично перегону звёздочки– с помощью формул вида Aξ→ξA и Bξ→ξB
4. Наконец, заменяем A или B в конце слова на прежний символ (A на a, B на b) и останавливаем алгоритм.
Все эти действия реализуются в виде следующего НАМ:
*a→A | *b→B | Aa→aA | Ab→bA |Ba→aB | Bb→bB | A→.a | B→.b | *→. λ| λ →*
Здесь формулы (1) и (2) заменяют первый символ слова (вместе с *) на А или В. Формулы (3) – (6) перегоняют А и В в конец слова. Формулы (7) и (8) применяются только тогда, когда А и В окажутся в конце слова (когда за ними уже нет символов), и восстанавливают исходный вид первого символа. Формула (9) нужна на случай пустого входного слова. Формула же(10) ставит спецзнак * перед первым символом.
Проверим этот алгоритм на входном слове baba и на входном слове из одного символа:
bbaba →*bbaba →Bbaba →bBaba →baBba →babBa →babaB→babab
Разработайте алгорифм Маркова, для вычисления функции f(x)=x*4910+1110, где x задано в семеричной системе счисления. Покажите правильность его работы на двух примерах, выбранных по вашему усмотрению.
Умножение семеричного числа на 49 означает добавление в его конец двух нулей. Далее к числу добавляется 147, что фактически означает, что вместо этих двух нулей нужно записать число 14. То есть задача сводится к добавлению в конец числа двух символов.
Написать алгорифм Маркова для вычисления функции f(x)=x–6, где x задано в шестеричной системе счисления и не содержит незначащих нулей, показать правильность его работы для x=1000, x=212, x=101. Ведущие нули в результате нужно удалить.
Вычитание из шестеричного числа 610 фактически означает вычитание значения 10. То есть последняя цифра числа останется неизменной. То есть сначала нужно найти предпоследний символ числа и проверить его значение. Если оно не равно нулю, то уменьшить его на 1. Если равно нулю, то заменить его на 5 и переместиться к предыдущей цифре. Для нее и всех последующих цифр повторить проверку. В итоге мы можем либо остановиться на одной из цифр (если среди них окажется значение больше нуля), либо дойти до крайней правой цифры и заменить ее на 0. В последнем случае получим незначащий ноль, который надо будет удалить.
*ξ→ ξ* | ξ*→#ξ | 1#→a0 | 2#→.1 | 3#→.2 | 4#→.3 | 5#→.4 | 0#→#5 | ξa→.ξ | a0→.λ | λ →*
Приписать слева к слову P символ a и справа символ c (P → aPc)
3) A=
Я ВЫПИСАЛ ТРИ ЗАДАНИЯ, НО НАДО РЕШИТЬ ТОЛЬКО ДВА, ЕСЛИ СМОЖЕТЕ ПОМОГИТЕ ПЛИЗ, ЛЮБЫЕ ДВА ИЗ ЭТИХ ТРЁХ
Машина Тьюринга. Приписать справа к слову P символ bс
Помогите решить: A=
Машина Тьюринга. Приписать слева к слову P символ b
A=
Машина Тьюринга. Приписать слева к непустому слову P его первый символ
Помочь найти в интернете решение задачи. А=
Выделить в строке символ пробелами слева и справа
Дана стартовая строка. Найти в ней символ, который вводится пользователем с клавиатуры, и отделить.
Приписать к числу 1022 слева и справа по одной цифре
Приписать к числу 1022 слева и справа по одной цифре так, чтобы полученное шестизначное число.
Дано натуральное число n. Приписать по единице справа и слева от этого числа
Дано натуральное число n. Приписать по единице справа и слева от этого числа.
Выяснить, какие цифры (по одной справа и слева) надо приписать к числу 1022
Выяснить, какие цифры (по одной справа и слева) надо приписать к числу 1022, чтобы полученное число.
Задача 56. Выяснить, какие цифры (по одной справа и слева) надо приписать к числу 1022,
Задача 56. Выяснить, какие цифры (по одной справа и слева) надо приписать к числу 1022, чтобы.