Машина тьюринга определить сбалансировано ли слово p по круглым скобкам

Машина Тьюринга и нормальные алгоритмы Маркова.

Доброго всем времени суток. Прошу помощи, срочно надо, решить не могу. Помогите, кто чем может.

____________________________________________________________ ____________________
Машина Тьюринга:

A=. Определить, входит ли в слово P символ a. Ответ: слово из
одного символа a (да, входит) или пустое слово (нет).

A=<(, )>. Определить, сбалансировано ли слово P по круглым скобкам.
Ответ: Д (да) или Н (нет).

A=. Пусть длина слова P кратна 3. Удалить правую треть этого слова.

A=. Если слово P содержит одновременно символы a и b, то заменить
P на пустое слово.

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

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

Нормальные алгоритмы Маркова, сложение и умножние
Как можно реализовать умножние в нормальных алгоритмах Маркова? Умножение в единичной системе.

Нормальные алгоритмы Маркова и их применение к словам
Умножить двоичное число на 2, приписав к нему 0 в конце. 10101

Нормальные Алгоритмы Маркова (НАМ). Проблемы с решением задачи
Дана вот такая задача по нормальным алгоритмам Маркова (НАМ). Нужно написать программу для.

Нормальные алгоритмы Маркова. Переставить каждую пару символов местами
Помогите,пожалуйста.. A=. Если в слове P не менее двух символов, то переставить каждую.

Нормальные алгоритмы Маркова: числа в единичной системе счисления уменьшить на 1
Помогите пожалуйста решить нормальные алгоритмы Маркова, преподаватель не хочет объяснить как это.

Алгоритм Маркова и машина Тьюринга!
A=. Пусть длина слова P кратна 3. Удалить правую треть этого слова. A=. Если слово P.

Источник

Доброго всем времени суток. Прошу помощи, срочно надо, решить не могу. Помогите, кто чем может.

____________________________________________________________ ____________________
Машина Тьюринга:

A=. Определить, входит ли в слово P символ a. Ответ: слово из
одного символа a (да, входит) или пустое слово (нет).

A=<(, )>. Определить, сбалансировано ли слово P по круглым скобкам.
Ответ: Д (да) или Н (нет).

A=. Пусть длина слова P кратна 3. Удалить правую треть этого слова.

A=. Если слово P содержит одновременно символы a и b, то заменить
P на пустое слово.

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

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

Нормальные алгоритмы Маркова, сложение и умножние
Как можно реализовать умножние в нормальных алгоритмах Маркова? Умножение в единичной системе.

Нормальные алгоритмы Маркова и их применение к словам
Умножить двоичное число на 2, приписав к нему 0 в конце. 10101

Нормальные Алгоритмы Маркова (НАМ). Проблемы с решением задачи
Дана вот такая задача по нормальным алгоритмам Маркова (НАМ). Нужно написать программу для.

Нормальные алгоритмы Маркова. Переставить каждую пару символов местами
Помогите,пожалуйста.. A=. Если в слове P не менее двух символов, то переставить каждую.

Нормальные алгоритмы Маркова: числа в единичной системе счисления уменьшить на 1
Помогите пожалуйста решить нормальные алгоритмы Маркова, преподаватель не хочет объяснить как это.

Алгоритм Маркова и машина Тьюринга!
A=. Пусть длина слова P кратна 3. Удалить правую треть этого слова. A=. Если слово P.

Источник

Решение задач. Машина Тьюринга

Написать программу на машине Тьюринга, прибавляющую число 2 к введенному числу.

Написать на машине Тьюринга программу, прибавляющую 3 к введенному числу.

Перенести первый символ непустого слова P в его конец. Алфавит : A=.

Если первый символ – это a, то надо перейти в состояние q2, в котором автомат бежит вправо и записывает в конце a. Если же первым был символ b, тогда надо перейти в состояние q3, где делается всё то же самое, только в конце записывается символ b. Если же первым был символ c, тогда переходим в состояние q4, в котором автомат дописывает за входным словом символ c.

Для решения этой задачи предлагается выполнить следующие действия:

В противном случае уничтожить всё входное слово ( q ₇ ).

Запомнить первый символ, стереть второй символ и установить на его месте первый.

Сдвиг символов осуществляется так: в очередной клетке записываем b (если в q ₁ ) или c (если в q ₂ ), переходим вправо и меняем состояние на q ₁ (если в текущей клетке было записано b ) или на q ₂ (если было записано c ), где осуществляется дальнейшая запись. Если в очередной клетке записано a или пробел, то записываем в нее запомненный символ и останавливаем программу.

После этого возвращаемся к началу входного слова.

Вначале записываем знак = за входным словом. Затем возвращаемся под первый символ входного слова.

Источник

Пример 1 (перемещение автомата, замена символов)

А=<0,1,2,3,4,5,6,7,8,9>. Пусть Р – непустое слово; значит, Р – это последовательность из десятичных цифр, т.е. запись неотрицательного целого числа в десятичной системе. Требуется получить на ленте запись числа, которое на 1 больше числа Р.

Для решения этой задачи предлагается выполнить следующие действия:

Перегнать автомат под последнюю цифру числа.

Если это цифра от 0 до 8, то заменить её цифрой на 1 больше и остановиться; например:

Если же это цифра 9, тогда заменить её на 0 и сдвинуть автомат к предыдущей цифре, после чего таким же способом увеличить на 1 ту предпоследнюю цифру; например:

Особый случай: в Р только девятки (например, 99). Тогда автомат будет сдвигаться влево, заменяя девятки на нули, и в конце концов окажется под пустой клеткой. В эту пустую клетку надо записать 1 и остановиться (ответом будет 100):

В виде программы для МТ эти действия описываются следующим образом:

Задачи для решения

1) В задачах рассматриваются только целые неотрицательные числа, если не сказано иное.

1. A=. Приписать слева к слову P символ b (P → bP).

2. A=. Приписать справа к слову P символы bc (P → Pbc).

3. A=. Заменить на a каждый второй символ в слове P.

4. A=. Оставить в слове P только первый символ (пустое слово не менять).

5. A=. Оставить в слове P только последний символ (пустое слово не менять).

6. A=. Определить, является ли P словом ab. Ответ (выходное слово): слово ab, если является, или пустое слово иначе.

7. A=. Определить, входит ли в слово P символ a. Ответ: слово из одного символа a (да, входит) или пустое слово (нет).

8. A=. Если в слово P не входит символ a, то заменить в P все символы b на с, иначе в качестве ответа выдать слово из одного символа a.

9. A=. Определить, является ли слово P идентификатором (непустым словом, начинающимся с буквы). Ответ: слово a (да) или пустое слово (нет).

10. A=. Определить, является ли слово P записью числа в двоичной системе счисления (непустым словом, состоящем только из цифр 0 и 1). Ответ: слово 1 (да) или слово 0.

11. A=<0,1>. Считая непустое слово P записью двоичного числа, удалить из него незначащие нули, если такие есть.

12. A=<0,1>. Для непустого слова P определить, является ли оно записью степени двойки (1, 2, 4, 8, …) в двоичной системе счисления. Ответ: слово 1 (является) или слово 0.

13. A=<0,1,2,3>. Считая непустое слово P записью числа в четверичной системе счисления, определить, является оно чётным числом или нет. Ответ: 1 (да) или 0.

14. A=<0,1>. Считая непустое слово P записью числа в двоичной системе, получить двоичное число, равное учетверенному числу P (например: 101 → 10100).

15. A=<0,1>. Считая непустое слово P записью числа в двоичной системе, получить двоичное число, равное неполному частному от деления числа P на 2 (например: 1011 → 101).

16. A=. Если P – слово чётной длины (0, 2, 4, …), то выдать ответ a, иначе – пустое слово.

17. A=<0,1,2>. Считая непустое слово P записью числа в троичной системе счисления, определить, является оно чётным числом или нет. Ответ: 1 (да) или 0. (Замечание: в чётном троичном числе должно быть чётное количество цифр 1.)

18. A=. Пусть P имеет нечётную длину. Оставить в P только средний символ.

19. A=. Если слово P имеет чётную длину, то оставить в нём только левую половину.

20. A=. Приписать слева к непустому слову P его первый символ.

21. A=. Для непустого слова P определить, входит ли в него ещё раз его первый символ. Ответ: a (да) или пустое слово.

22. A=. В непустом слове P поменять местами его первый и последний символы.

23. A=. Определить, является P палиндромом (перевёртышем, симметричным словом) или нет. Ответ: a (да) или пустое слово.

24. A=. Заменить в P каждое вхождение a на bb.

25. A=. Заменить в P каждое вхождение ab на c.

26. A=. Удвоить слово P (например: abb → abbabb).

27. A=. Удвоить каждый символ слова P (например: bab → bbaabb).

28. A=. Перевернуть слово P (например: abb → bba).

29. A=<0,1>. Считая непустое слово P записью двоичного числа, получить это же число, но в четверичной системе. (Замечание: учесть, что в двоичном числе может быть нечётное количество цифр.)

30. A=<0,1,2,3>. Считая непустое слово P записью числа в четверичной системе счисления, получить запись этого числа в двоичной системе.

31. A=<0,1,2>. Считая непустое слово P записью положительного числа в троичной системе счисления, уменьшить это число на 1.

32. A=< | >. Считая слово P записью числа в единичной системе счисления, получить запись этого числа в троичной системе. (Рекомендация: следует в цикле удалять из «единичного» числа по палочке и каждый раз прибавлять 1 к троичному числу, которое вначале положить равным 0.)

33. A=<0,1,2>. Считая непустое слово P записью числа в троичной системе счисления, получить запись этого числа в единичной системе.

35. A=< | >. Считая слово P записью числа в единичной системе, определить, является ли это число степенью 3 (1, 3, 9, 27, …). Ответ: пустое слово, если является, или слово из одной палочки иначе.

36. A=< | >. Считая слово P записью числа n в единичной системе, получить в этой же системе число 2n.

37. A=< | >. Пусть слово P является записью числа 2n (n=0, 1, 2, …) в единичной системе. Получить в этой же системе число n.

38. Пусть P имеет вид Q+R, где Q и R – непустые слова из символов 0, 1 и 2. Трактуя Q и R как записи чисел в троичной системе счисления (возможно, с незначащими нулями), выдать в качестве ответа запись суммы этих чисел в той же троичной системе.

39. Пусть P имеет вид Q–R, где Q и R – непустые слова из символов 0, 1 и 2. Трактуя Q и R как записи чисел в троичной системе счисления (возможно, с незначащими нулями) и считая, что Q≥R, выдать в качестве ответа запись разности этих чисел в той же троичной системе.

40. Пусть P имеет вид Q=R, где Q и R – любые слова из символов a и b. Выдать ответ a, если слова Q и R одинаковы, и пустое слово иначе.

41. Пусть P имеет вид Q=R, где Q и R – непустые слова из символов 0 и 1. Трактуя Q и R как записи двоичных чисел (возможно, с незначащими нулями), выдать в качестве ответа слово 1, если эти числа равны, и слово 0 иначе.

42. Пусть P имеет вид Q>R, где Q и R – непустые слова из символов 0 и 1. Трактуя Q и R как записи двоичных чисел (возможно, с незначащими нулями), выдать в качестве ответа слово 1, если число Q больше числа R, и слово 0 иначе.

43. A=<(, )>. Определить, сбалансировано ли слово P по круглым скобкам. Ответ: Д (да) или Н (нет).

44. A=. Если в P символов a больше, чем символов b, то выдать ответ a, если символов a меньше символов b, то выдать ответ b, а иначе в качестве ответа выдать пустое слово.

[1] Эмуля́ция (англ. emulation) — воспроизведение программными или аппаратными средствами либо их комбинацией работы других программ или устройств. Эмуляция позволяет выполнять компьютерную программу на платформе (компьютерной архитектуре и/или операционной системе), отличной, или в некоторых случаях идентичной той, для которой она была написана в оригинале. Эмуляцией также называют сам процесс этого выполнения. В отличие от симуляции, которая лишь воспроизводит поведение программы, при эмуляции ставится цель точного моделирования состояния имитируемой системы, для выполнения оригинального машинного кода.

[2]Если надо указать, что после выполнения некоторого такта МТ должна остановиться, то в третьей позиции этого такта будем писать знак «!». Например, такт b,L,! означает следующие действия: запись символа b в видимую клетку ленты, сдвиг влево и останов.

Источник

Машина Тьюринга. Определить, входит ли в слово P символ a

Машина Тьюринга: оставить в слове P только последний символ (пустое слово не менять)
Помогите решить A=. Оставить в слове P только последний символ (пустое слово не менять).

Машина Тьюринга: оставить в слове Р только последний символ (пустое слово не менять)
A=. Оставить в слове Р только последний символ (пустое слово не менять).Помогите

Машина Тьюринга: если P-непустое слово, то за его первым символом вставить символ а
Если P-непустое слово, то за его первым символом вставить символ а. Алфавит А:.

Машина Тьюринга: Если первый и последний символ непустого слова различаются, то заменить слово пустым
Здравствуйте,помогите решить задачу. Если первый и последний символ непустого слова различаются.

Определить, какое слово перерабатывает машина Тьюринга из данных слов.
Вот собственно два задания Помогите решить, одно начал, но не знаю как дальше 1 задание: 2.

Машина Тьюринга: после знака «=» вывести символ алфавита, входящий в слово в минимальном количестве
Слово в алфавите abc. После знака = вывести символ алфавита, входящий в слово в минимальном.

Машина Тьюринга. В итоговом ответе записать что получившиеся слово = a0 a0 a0 a0 a0 или слово = 0
Я решил задачу: После применения машины Тьюринга к слову a=11*11, у меня вышло после применения.

Источник