Форум программистов и сисадминов Киберфорум

Темы раздела Теория автоматов

Получить обратную кодировку для отрицательного числа с тем же абсолютным значением
Марков - перевод из десятичной системы в двоичную. Входное слово представляет собой десятичную запись целого неотрицательного числа в прямой кодировке. Получить обратную кодировку для...

Лемма о накачке для КС языков
Перепробовал все слова и ни одно не накачалось.

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

Как представить алгоритм в виде конечных автоматов?
Требования 1. Нарисовать граф-схему конечного автомата; 2. Выполнить кодирование входного алфавита и состояний автомата; 3. Заполнить таблицу переходов состояний автомата; 4. Составить функции...

Реализовать машину Тьюринга для вычисления заданной функции над целыми числами в унарной системе счисления
Задание: В JFLAP реализовать машину Тьюринга для вычисления заданной функции над целыми числами в унарной системе счисления, обязательно предложить представление неположительных чисел в унарной...

Построить автомат Тьюринга с применением таблиц Excel
Добрый день! Необходимо построить автомат Тьюринга, с применением таблиц Excel, для условия: A={ | }. Пусть слово Р является записью числа 2n (n=0, 1, 2, в единичной системе. Получить в этой же...

Проверить решение задачи по машине Тьюринга
Здравствуйте. У меня тут задача по машине Тьюринга, хочу понять правильно ли решил. В общем, по заданию нужно построить машину Тьюринга, применимую ко всем словам x1, x2, ..., xn в алфавите {a,b} и...

Построить НАМ (нормальный алгоритм Маркова) для преобразования
Построить нормальный алгоритм для преобразования слова Р в слово Q, при условии что в каждой подстановке Рi→(•)Qi алгоритма число букв удовлетворяет неравенству: Рi ≤ n, Qi ≤ n, где...

Помощь с доработкой нормального алгоритма Маркова
Мне необходимо составить нормальный алгоритм Маркова для ф-и f(x,y,z)=y+z+3. С горем пополам мне удалось составить приведённый на изображении алгоритм, но проблема в том, что он работает слегка...

Разобраться, как работает автомат и по какому принципу формируется очередной входной сигнал?
Сводная таблица на скриншоте. По всей видимости, это автомат Мили. Главный вопрос: по какому принципу формируется очередной входной сигнал? Он формируется на основе предыдущего состояния (конечный...

Составить программу, работая по которой машина Поста найдет этот массив и установит каретку на начало этого массива
Всем привет, столкнулся с такой задачей: Задача В. А. Успенского. На информационной ленте либо вправо, либо влево от секции, над которой расположена каретка, находится массив меток. Расстояние до...

Составить программу для машины Тьюринга для вычисления простой функции
Составить программу для машины Тьюринга: Функция: X+3 Правила форума: пункт 4.7. Как можно более полно описывайте суть проблемы или вопроса, что было сделано для ее решения и какие результаты...

Машина Тьюринга, умножающая число на 2
На ленте машины Тьюринга находится число, записанное в десятичной системе исчисления. Умножьте это число на 2, если каретка находится над крайней левой цифрой числа. Помогите, пожалуйста, завтра...

Машина Тьюринга: вычисление значения функции f(x,y)=2x y
Помогите, пожалуйста, построить машину Тьюринга для f(x,y)=2x+y

Нужна литература с большим количеством примеров алгоритмов Машины Тьюринга
Привет всем. Нужна литература с большим количеством примеров алгоритмов Машины Тьюринга. Кто-нибудь подскажет название книги и автора или др.

Машина Тьюринга, вычисляющая значение f(x)=x-y. Принцип работы.
Здраствуйте!Недавно на вашем сайте мне помогли с задачей, и я очень благодарна!Но вот помогите,как понять её,что она делает Построить Машину Тьюринга,вычисляющую значение функции f(x)=x-y q11->q11R...

Машина Тьюринга. Приписать слева к слову P символ b
A={a,b,c}. Приписать слева к слову P символ b (P → bP). Как решить данную задачу и как вообще решать машину Тьюринга?

Машина Тьюринга. Вычислить разность и сумму двух двоичных чисел
Реализовать заданные алгоритмы с помощью машины Тьюринга. 1. Вычислить разность двух двоичных чисел, разделенных знаком -. 2. Поразрядно сложить два двоичных числа, разделенных знаком +.

Отличия машины поста от машины тьюринга
Отличия машины поста от машины тьюринга?

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

Дана грамматика. Построить вывод заданной цепочки и дерево вывода.
2) Дана грамматика. Построить вывод заданной цепочки и дерево вывода. 1) S ->T | T+S | T-S 2) S->aSBC | abC T ->F | F*T CB -> BC F ->a | b bB -> bb Цепочка a-b*a+b bC -> bc cC...

Машина Тьюринга, оставить в P только средний символ
Помогите решить задачу! Не получается, то работает для строки длины 3, а для 5 нет и 7 соответственно, то все удаляет и не останавливается на центральном элементе. A={a,b,c}. Пусть P имеет нечётную...

Машина Тьюринга для чисел в унарной системе счисления div 2 и mod 2
Написать две машины тьюринга. X div 2 и X mod 2, где x- число в унарной сс.

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

Машина Тьюринга. Удалить из массива все элементы B.
На информационной ленте машины Тьюринга находится массив, состоящий только из символов A и B. Сожмите массив, удалив из него все элементы B. Помогите , пожалуйста,преподша злая...я у нее ничего не...

Для автомата, заданного таблично, построить диаграмму Мура
Для Автомата, заданного таблично, построить диаграмму Мура. Задать автомат системой булевых функций и каноническими уравнениями: 0 1 2 3 0 (2;1) (2;1) (2;1) (2;1) 1 (1;1) (3;1) (0;0) (1;0) ...

Машина тьюринга: посчитать кол-во единиц
Привет всем. Есть двоичное число, я перевел его в унарную систему. Т.к. необходимо посчитать кол-во единиц десятичной системы, а переводить унарную в десятичную кажеца мне жестью, то можно ли это...

Машина поста: разность 2-ух чисел
Добрый день. Нужно написать алгоритм разность 2ух чисел (Левое всегда больше правого) Каретка вначале стоит на правой крайней позиции вычитаемого числа.

Машина Тьюринга: вычисление остатка от деления
Здравствуйте Друзья, помогите пожалуйста с задачей. Необходимо построить машину Тьюринга вычисляющую остаток от деления. Входные данные: x*y Выходные данные: r Например x=10, y=3. r должно быть...

Доказать, что функция примитивно рекурсивна
Здравствуйте,нужна помощь: Доказать, что функция f(x,y)=2^{x^2+y}+y^{x!} примитивно рекурсивна. Как я делал: f(x,0)=2^(x^2) f(x,y+1)=2^(x^2+y+1)+(y+1)^x!,=2*2^(x^2)+y^x!+1, а что делать...

Машине Поста: умножение унарного числа на 2.
Привет. Столкнулся с проблемой алгоритмизаици решения задачи на машине Поста. Необходимо умножить число записанное в унарной системе счисления на 2. Каретка машины находится на первом знаке числа....

Синтез автомата-распознавателя последовательности.
Имеется задание, которое нужно сделать по учебнику Аляев Ю.А. Тюрин С.Ф. Дискретная математика и математическая логика. Постановка задачи синтеза. Дано: последовательность входных кодовых...

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

Составить грамматику, порождающую формальный язык
1) составить грамматику, порождающую формальный язык 2) построить цепочку языка по грамматике; 3) построить дерево вывода (левосторонний и правосторонний вывод) для этой цепочки. Эквивалентны ли...

Машина Тьюринга по заданной функции: f(x)=[1/x]
Здравствуйте, УВАЖАЕМЫЕ! Помогите, если можете пожалуйста!!!!!!!!! Плиз, не бросайте в беде(((( Описать принцип работы машины Тьюринга по заданной функции: f(x)=={1,если х=1 ...

Машина Тьюринга (целая часть от деления)
Здравствуйте, прошу помочь с реализацией "деление нацело" в Машине Тьюринга, есть ли пример ? Может быть алгоритм, ход какой - либо. Только использовать Алфавит = {1}

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

Преобразовать в нормальную форму Хомского КС-грамматики.
Преобразовать в нормальную форму Хомского КС-грамматики G=(N,\Sigma ,P,S) 1. S\rightarrow AB, A\rightarrow SA, A\rightarrow BB, A\rightarrow bB, B\rightarrow b, B\rightarrow aA, B\rightarrow...

Машина Тьюринга. Проверить, является ли бинарное слово палиндромом
проверить,является ли бинарное слово палиндромом.Машина Тьюринга.

Машина Поста: сложение а+b (проверьте решение)
Всем привет! Проверьте если не сложно, правильно ли решил? И если не так подправьте. Условие: Составьте программу сложения двух целых неотрицательных чисел a и b, расположенных на ленте машины...

Построение грамматики
А вот с такими задачами поможите....... 3.Построить грамматику, порождающая язык: L_4={ab^n c|n≥1} 4. Построить грамматику, порождающая язык: L_4={a^n b^m c|n,m≥1} 5.Построить КС –...

К какому типу по Хомскому относится данная грамматика? Какой язык она порождает?
Люди помогите, пожалуйста... Вот с такие вопросами: 1.К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? S→aSBa|aba; aB→Ba; bB→bb; 2. К какому...

Перевернуть слово, используя машину Тьюринга
A {a,b} Перевернуть слово Р ( пример:abb->bba) Не могу никак решить эту задачу машиной Тьюринга

Построить грамматику, порождающую формальный язык
L(G) = {(ab)^n (cb)^m | n, m>=0} 1) Построить грамматику, порождающую формальный язык. 2) Построить цепочку языка по грамматике. 3) Построить дерево вывода (левосторонний и правосторонний вывод)...

Машина Тьюринга. Удвоить слово P (например: abb → abbabb)
Удвоить слово P (например: abb → abbabb). У меня уже есть часть программы, но проблема в том, что пока моя программа умеет только копировать слово без остановки и я не знаю, как её завершить. Скорее...

Алгоритм Маркова для перевода четверичного числа в двоичную систему счисления
Разработать алгорифм Маркова для перевода четверичного числа в двоичную систему счисления. Показать правильность его работы на примерах: а) 123 б) 3210

Машина Тьюринга: увеличить число в семеричной системе счисления на 2.
На ленте машины Тьюринга находится целое положительное число, записанное в семеричной системе счисления. Увеличить это числа на 2. Каретка обозревает крайнюю правую цифру числа.

Перевернуть слово в Машине Тьюринга
Ребята, помогите, пожалуйста. Нужна помощь с задачей. A={a,b}. Перевернуть слово P (например: abb → bba)

Машина Тьюринга: проверить число на четность
Определить машину Тьюринга, которая проверяет четное число или нет, если четное, то завершает работу иначе работает бесконечно.

Машина Тьюринга, заменить на a каждый второй символ в слове
Привет, как это сделать? A={a,b,c}. Заменить на a каждый второй символ в слове P. сделал, училка поставила 2 и написала: оц 2 на слове "сссввссввсвв" дает ошибку "нет команды" после замены...

Машина Поста: деление заданного числа на 5
помогите составить программы:1.Составить программу деления заданного числа на 5. Пояснение. Под делением понимается нахождение частного или неполного частного, так что результат деления 7 на 3 будет...

Нормальный алгоритм Маркова: умножение двух чисел, представленных символами 1
Дорогие, друзья, одна надежда на Вас, ибо перерыла интернет, но не нашла ничего существенного по своей задаче=( Вот собственно она: "Построить НАМ, реализующий вычитание двух заданных чисел в...

Нормальный алгоритм Маркова: сложение 2 десятичных чисел - уменьшение одного числа и увеличение другого на 1
Задание №1 Составьте нормальный алгоритм сложения двух десятичных чисел методом уменьшения одного числа на 1 и увеличением другого числа на 1 до тех пор, пока уменьшаемое число не станет равным 0. ...

Построение конечного автомата...
Задали лабу, но ничего не обьяснили. Что тут нужно вообще делать, пожалуйста, подскажите...

Алгоритм Маркова. Увеличить число, записанное в троичной системе, на 1
Здравствуйте, помогите, пожалуйста, написать программу для алгоритмов Маркова: увеличить число,записанное в троичной системе, на 1.

Составьте для машины Поста программу, придвигающую данный массив к данной ячейке.
Машина Поста На ленте имеется массив из n отмеченных ячеек. Каретка обозревает крайнюю левую метку. Справа от данного массива на расстоянии в m ячеек находится еще одна метка. Составьте для машины...

Машина Тьюринга: заменить слово на пустое при выполнении данного условия.
Помогите пожалуста решить задачу в виде таблицы: А={а,b,с} Если первый и последний символы непустого слова Р одинаковы тогда это слово не менять, а иначе заменить его на пустое слово!

Машина Тьюринга: Разность чисел в троичной систем
Создать машину Тьюринга .которая находит разность двух чисел в троичной системе. Вот не понимаю я что то как разность делать

Машина Тьюринга: перевод числа из двоичной в 4-ричную систему счисления
Дана такая задача: А={0,1}. Считая непустое слово Р записью двоичного числа, получить это же число, но в четверичной системе. (Замечание: учесть, что в двоичном числе может быть нечетное количество...

Построить автомат, распознающий регулярный язык
Построить автомат: d*ac* + (dbc)*ac* Как это сделать. В интернете хорошей информации не нашел по данной теме.

Сложение двух чисел в двоичной СС в Машине Тьюринга
Помогите решить задачу для Машины Тьюринга, адекватное решение не гуглится(( Задача: Сложение двух чисел в двоичной системе счисления(каждое число имеет не более 3х разрядов). Между слагаемыми...

Машина Тьюринга: определить, является ли P словом ab
6. A={a,b,c}. Определить, является ли P словом ab. Ответ (выходное слово): слово ab, если является, или пустое слово иначе.

Рассчитать среднюю длину кода при методе Хаффмана
Совсем не понимаю, как это делается ._.

Определить язык,который порождает грамматика
Вообщем дана вот такая граммматика: S\rightarrow S0\mid A1\mid 0\mid 1 A\rightarrow A1\mid B0\mid 0\mid 1 B\rightarrow A0 определить язык,который порождает грамматика Не понимаю как решать,...

Машина Тьюринга. Приписать слева к непустому слову P его первый символ
Помочь найти в интернете решение задачи. А={a,b,c}. Приписать слева к непустому слову P его первый символ.

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

Машина Тьюринга: сортировка 0 и 1 в двоичном слове
Ребята помогите с задачей. Сортировка 0 и 1 в двоичном слове. Пример (01010 - входные данные , на выходе должно получится 00011).

Разработать машину Тьюринга, которая уменьшала бы заданное число n на 1
Дана десятичная запись натурального числа n . Разработать машину Тьюринга, которая уменьшала бы заданное число n на 1.

Машина Тьюринга. Считая непустое слово P записью числа в 4-ой СС, получить запись этого числа в 2-ой СС
Ребят, помогите пожалуйста сделать, ну никак не получается A={0,1,2,3}. Считая непустое слово P записью числа в четверичной системе счисления, получить запись этого числа в двоичной системе.

Машина Тьюринга. Перевод числа из десятичной системы счисления в двоичную систему счисления.
Всем привет! Помогите решить задачу по теме машина Тьюринга. Перевод числа из десятичной системы счисления в двоичную систему счисления. Нужно составить алгоритм и команды для машина Тьюринга.

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

Машина Поста.Вычислить разность массивов.
На ленте заданы два массива — m и n, m > n. Вычислить разность этих массивов. Каретка располагается над левой ячейкой левого массива (m).

Машина Поста. На ленте задан массив. Если он состоит из трех или менее меток, то удвоить его длину
Помогите пожалуйста с машиной поста.. Условие: На ленте задан массив. Если он состоит из трех или менее меток, то удвоить его длину. В противном случае оставить массив без изменения. Начальное...

Разработать машину Тьюринга для функции
На ленте записано число в унарной системе счисления. Разработать машину Тьюринга для функции f(x)=2x

Нормальные алгоритмы Маркова: числа в единичной системе счисления уменьшить на 1
Помогите пожалуйста решить нормальные алгоритмы Маркова, преподаватель не хочет объяснить как это работает, а я только начала обучаться и ничего не понимаю A={ | }. Считая слово P записью...

Машина Тьюринга - заменить каждое вхождение символа
A={a,b}. Заменить в P каждое вхождение a на bb.

Считая непустое слово P записью двоичного числа, удалить из него незначащие нули, если такие есть
A={0,1}. Считая непустое слово P записью двоичного числа, удалить из него незначащие нули, если такие есть. Помогите пожалуйста разобраться, если можно со скринами, буду очень признателен....

Машина Тьюринга. Найти наибольшее число в неупорядоченной последовательности унарных чисел
Здравствуйте. У меня задача: Задана неупорядоченная последовательность унарных чисел. Найти наибольшее число Я не понимаю, как мне посчитать в МТ количество единиц. Например на ленте у меня 1111...

Машина Тьюринга: если слово Р имеет четную длину, то оставить в нем только первую половину
Дан алфавит A={a,b,c}. Если слово Р имеет четную длину, то оставить в нем только первую половину. С частью про четность разобрался, а вот как оставить только первую половину - нет. Помогите,...

Машина Тьюринга. Умножение двух чисел
Здравствуйте. Никак не могу в машину Тьюринга. :( Нужно составить таблицу и правила для функции f(x,y)=x*y Есть подобное для деления, никак не могу переделать. Заранее спасибо.

Машина Тьюринга. Записать цифры числа в обратном порядке
Нужно помощь с алгоритмом Дано двоичное число. Справа через пробел записать цифры числа в обратном порядке. Начальное положение каретки – над крайней правой цифрой числа.

Построить машину Тьюринга, применимую ко всем словам в алфавите
Здравствуйте. есть задание 1. Построить машину Тьюринга, применимую ко всем словам в алфавите и переводящую их в слово . 2. Проверить работу машины Тьюринга над некоторыми словами. \alpha =...

Машина Тьюринга: уменьшить заданное число n на 1
Дано натуральное число n > 1. Разработать машину Тьюринга, которая уменьшала бы заданное число n на 1, при этом в выходном слове старшая цифра не должна быть 0. Например, если входным словом было...

Алгоритм Маркова. Вычитание двоичных чисел
Здравствуйте, мне задали с помощью НАМа сделать вычитание двоичных чисел, причем выглядеть это должно следующим образом Строка ввода:- Строка вывода:-= Помогите доработать код. Я скопировал...

Машина Тьюринга: удалить из слова Р его второй символ, если такой есть
1. A={a,b}. Удалить из слова Р его второй символ, если такой есть. 2. A={a,b,c}. Приписать слева к слову P символ b (P->bP) 3. A={a,b,c}. Оставить в слове Р только последний символ (пустое слово не...

Машина Поста: отыскать и стереть среднюю метку массива
На ленте машины Поста расположен массив из 2n-1 отмеченных секций. Постройте программу машины Поста, отыскивающую и стирающую среднюю метку массива, при этом каретка расположена слева от массива на...

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

Машина Тьюринга: вычисление значения функции f(x)=x-y
Здравствуйте!Помогите пожайлуста, очень нужна помошь :( Построить Машину Тьюринга,вычисляющую значение функции f(x)=x-y Заранее спасибо

Машина Тьюринга. Разность 2 двоичных чисел с логарифмической сложностью
Задача состоит из 3х условий: 1. Вычисление разности 2х двоичных чисел, без знака, при условии, что первое число больше 2го. 2. С логарифмической сложностью. 3. Ответ - модуль разности. В МТ...

НАМ: Считая слово P записью числа в единичной системе счисления, получить остаток от деления этого числа на 2
A={ | }. Считая слово P записью числа в единичной системе счисления, получить остаток от деления этого числа на 2, т.е. получить слово из одной палочки, если число нечётно, или пустое слово, если...

Написать алгоритм сложения в унарном коде (машина Тьюринга)
Здравствуйте! Меня уже долгое время мучает вопрос: Нужно написать алгоритм сложения двух чисел в унарном коде, причем данный алгоритм должен быть универсальным, т.е. работать для чисел любой длины....

Создать машину Тьюринга, которая прибавляет 1 к числу в восьмеричной системе счисления
Здравствуйте, помогите создать МТ которая прибавляет 1 к числу в восьмеричной сс. Например на ленте начальное число 777 ,итогом должно быть записано 777+1=1000 просто изменить число на это же...

Машина Тьюринга: проверить на четность число, записанное в двоичной системе счисления
Проверить на четность число, записанное в двоичной системе счисления. надо разработать тьюринговую функциональную схему. я нашла в инете пример, но если честно не очень понимаю его( может кто...

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

Машина Тьюринга: вычислить разность двух чисел в троичной системе счисления
Помогите, пожалуйста, написать машины Тьюринга для следующих задач: 1. Пусть P имеет вид Q-R, где Q и R - непустые слова из символов 0,1,2. Трактуя Q и R как записи чисел в троичной системе...

Машина Тьюринга. Определить, входит ли в слово P символ a
7. A={a,b,c}. Определить, входит ли в слово P символ a. Ответ: слово из одного символа a (да, входит) или пустое слово (нет).

Машина Тьюринга: удвоить каждую букву в каждом слове
Написать программу для машины Тьюринга, которая каждое слово {x}_{1}{x}_{2}...{x}_{n} в алфавите A={0,1} преобразует в слово {x}_{1,{x}_{1}{x}_{2}{x}_{2}...{x}_{n}{x}_{n} Головка в начале...

Как создавались языки программирования
На днях поймал себя на мысли: "Тысячи людей учат языки программирования. Про каждый язык написано бесчисленное количество книг. Ни один программист не знает в идеале свой язык. С помощью языков...

Алгоритм Маркова: нахождение максимума и минимума трех чисел
Помогите, пожалуйста, с задачей. пыталась понять, прочитала много информации так полностью и не додумала решение.. задача : "Написать программу нахождения максимума и минимума трех чисел при помощи...

Алгоритм Маркова для вычитания двоичных чисел
Доброго времени. Кто нибудь может написать алгоритм маркова для вычитания двоичных чисел? Очень надо, а найти не могу, допереть тоже.

Нормальные алгоритмы Маркова: проверить чётность числа
A={0,1,2,3}. Считая непустое слово P записью четверичного числа, про- верить, чётно оно или нет. Ответ: слово 0, если чётно, и слово 1 иначе.

Нормальный алгоритм Маркова: перевернуть слово P
A={a,b} Перевернуть слово Р (например abb->bba). ... что-то не могу хоть убей. была как-то на форуме, но не решили.хелп

Построить машину Тьюринга. Если в P символов a больше, чем символов b, то выдать ответ a
A={a,b}. Если в P символов a больше, чем символов b, то выдать ответ a, если символов a меньше символов b, то выдать ответ b, а иначе в качестве ответа выдать пустое слово.

Машина Тьюринга. Умножение двоичных чисел
Ребята, очень нужна помощь. Скиньте, пожалуйста полный алгоритм умножения двоичных чисел в машине Тьюринга. Хочу экзамен автоматом :(

Машина Тьюринга, которая рассчитывает функцию f(x)=2x
Доброго времени суток. Помогите пожалуйста! Нужно описать машину Тьюринга, которая рассчитывает функцию f(x) = 2x для чисел, заданных в унарной системе исчисления.

Алгоритм Маркова: поиск НОД (Алгоритм Евклида)
Здравствуйте, ребята, выручайте. Весь инет перерыл, всю голову сломал, но не могу сделать. Суть в чем, надо построить алгорифм Маркова, который ищет наибольший общий делитель (алгоритм Евклида)....

Описать язык, порождаемый заданной грамматикой
Необходимо описать язык пораждаемый грамматикой : S->0A|1S A-0A|1B B->0B|1B|Ʇ Помогите сделать,не понятно как это делается, а примеров в инете особо не нашел Добавлено через 6 минут Есть...

Построить машину Тьюринга для вычитания унарных чисел
Помогите, пожалуйста, разобраться в задаче. Дано условие: нужно построить машину Тьюринга, вычитающую число х из числа у. Оба числа записаны на ленте в унарной системе: n=1n+1. Соответственно,...

Машина поста и машина тьюринга: необходимо написать алгоритм к данному изображению
нужно решение в виде команд МТ и МП

Копирование слова в машине Маркова
есть набор текста qabbqqb . Что нужно сделать, что бы стало qabbqqbqabbqqb ?

Машина Тьюринга: является ли унарное число степенью трёх
Построить машины Тьюринга для вычисления функций A={ | }. Считая слово P записью числа в единичной системе, определить, является ли это число степенью 3 (1, 3, 9, 27, …). Ответ: пустое слово, если...

Нормальный алгоритм Маркова: f=3x+5
Здравствуйте, помогите решить Построить Нормальный алгоритм Маркова интерпретирующий функцию f=3x+5. и ответ записать в 8-ой системе счисления. и написать словесное описания алгоритма этого ...

Нормальный алгоритм Маркова. Если слово состоит из нечетного количества символов - удалить средний
Нормальные алгоритмы Маркова Буду признателен, если поможете с задачей (натолкнуть хотя бы на нужную мысль). Тут не получается посчитать кол-во элементов, как в МТ, перескочив на две клетки в...

Написать алгоритм Маркова, который в алфавите {a,b,c} удаляет в слове предпоследнюю букву, если в слове есть буквы b
Написать алгоритм Маркова, который в алфавите {a,b,c} удаляет в слове предпоследнюю букву, если в слове есть буквы b. Привести пример работы алгоритма.

Машина Тьюринга. Удаление подслова.Как его правильно провести?
По заданию необходимо удалить из текста подслова вида 'abc'. Понимаю, что сначала нужно прочитать текст, чтоб найти данные подслова. Затем, обнаружив их пометить-обозначить, например как 123, и...

Определите, в какое слово перерабатывает машина Тьюринга каждое из данных слов.
Имеется машина Тьюринга с внешним алфавитом А={a0 ,1}, алфавитом внутренних состояний Q={q0 ,q1} и программой, заданной командами: q0a0→ q01, q11→ q11П. Определите, в какое слово...

Машина Тьюринга: поменять слова местами
Построить машину Тьюринга. Нужно поменять слова местами. Не обязательно такие слова, могут быть любые.

Машина Тьюринга, которая считает сумму двух двоичных чисел
Подскажите код программы на машине тьюринга, которая считает сумму двух двоичных чисел

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

Машина Тьюринга и алгоритм Маркова: деление данных двоичных чисел.
На вход 2-а числа в двоичной системе, разделенные знаком деления. Необходимо за ними поставить знак равно и результат деления. ПОмогите пожалуста!!!! Напишите хотяб алгоритм Тьюринга и если кто...

Оценка стоимости схемы (аппаратные затраты по Квайну)
Здравствуйте! У меня несколько вопрос по оценке стоимости схемы по Квайну. Нашел 3 варианта алгоритма. какой же все таки верен? для ДНФ сложность схемы равна сумме количества букв,(букве со...

Машина Тьюринга. Перевод из двоичной в четверичную СС
Перевод числа из двоичной в четверичную СС.

Написать программу для машины Поста
На ленте машины Поста записаны два целых числа a и b соответствующими массивами меток (a>0,b>0,a>b). Данные массивы разделены любым количеством пустых ячеек. Написать программу для машины Поста,...

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

Машина Тьюринга: сложение двух двоичных чисел
Привет форумчани:) Помогите написать МТ для сложения двух двоичных чисел. Алгоритм должен быть применяем ко всем числам. Пример ленты: 101011+11101=. Каретка стоит на символе "=".

Машина Поста: сложение двух целых неотрицательных чисел а и Ь, расположенных на ленте
6. Составьте программу сложения двух целых неотрицательных чисел а и Ь, расположенных на ленте машины Поста. Каретка расположена над одной из меток, принадлежащих числу а. Число b находится правее...

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

Машина Поста: стереть все метки кроме крайних, и поставить каретку в исходное положение
Задание: Дан массив меток. каретка располагается где-то над массивом, но не над крайними метками. стереть все метки кроме крайних, и поставить каретку в исх положение. у меня есть решение но...

На информационной ленте машины Поста находится массив меток
привет) помогите пожалуйста решить задачи по машине Поста :) спасибо заранее ^^ 2. На информационной ленте машины Поста находится массив меток. Каретка находится где-то над массивом (но не над...

Машина Поста: вычислить остаток от деления длины заданного массива на 5.
На ленте задан массив. Вычислить остаток от деления длины заданного массива на 5 и через 2 пустых ячейки продублировать остаток отдельным массивом (т.о. в итоге должно получиться два массива). ...

Марков. Замена a на b и наоборот
Задано алфавит A = {а, b}. В слове p все символы а заменить на b, а все (бывшие) символы b - на а. Не понимаю каким образом алгоритм должен определять бывшие и заменённые b, пробовал добавлять...

A={ | }. Считая слово P записью числа n в единичной системе, получить в этой же системе число 2n.
Не могу толком понять что от меня требует задание: A={ | }. Считая слово P записью числа n в единичной системе, получить в этой же системе число 2n. Вот из этого надо слепить машину,ну и в итоге...

Машина Тьюринга. По заданной машине Тьюринга и начальной конфигурации К1 найти заключительную конфигурацию.
здравствуйте! тут надо решить два задания. очень надеюсь на вашу помощь! 1.Выяснить применима ли машина Тьюринга Т, задаваемая программой П, к слову Р. Если применима, то выписать результат...

Перевод из 16-ричной в 4 -ричную систему счисления. Машина Тьюринга
Добрый день. Требуется написать систему команд Машины Тьюринга для перевода шестнадцатиричного числа в четверичное. Первое что пришло в голову - перевести в двоичную, а потом в четверичную. ...

Нормальный алгоритм Маркова: если в P символов a больше, чем символов b, то выдать ответ a
A={a,b}. Если в P символов a больше, чем символов b, то выдать ответ a, если символов a меньше символов b, то выдать ответ b, а иначе в качестве ответа выдать пустое слово

Машина Тьюринга. Уменьшение двоичного числа на единицу
Построить машину Тьюринга, уменьшающую двоичные числа на единицу. Если я правильно понял, в качестве алфавита тут будет: A={0,1,*} Полагаю, нужно использовать звёздочку для того, чтобы определить...

Машина Тьюринга: проверить длину слова на четность
Помогите написать программу для Машины Тьюринга, даже не представляю как проверить слово на четность A={a,b,c}. ЕслиP – слово чётной длины (0, 2, 4, …), то выдать ответ a, иначе – пустое слово.

Машина Тьюринга и нормальные алгоритмы Маркова.
Доброго всем времени суток. Прошу помощи, срочно надо, решить не могу. Помогите, кто чем может. ________________________________________________________________________________ Машина Тьюринга: ...

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

Построить детерминированный конечный автомат
Построить детерминированный конечный автомат по регулярной грамматике G=(N, Σ, P, S). Определить язык, допускаемый коне G=(N, Σ, P, S). N={S, A, B, C}, Σ={a,b}, ...

Найти КС-грамматику, порождающую язык
Не могу догадаться, как их решать... Найти КС-грамматику, порождающую язык { 1^n 0^m 1^m 0^n | n≥0, m≥0}. Найти КС-грамматику, порождающую язык всех цепочек в алфавите {0,1}, содержащих...

Машина Тьюринга для функции f(x,y)=x+y
Здравствуйте! Помогите написать машину Тьюринга для функции f(x,y)=x+y. Для 2 представления, т.е. начальный символ 0, за ним x единиц, далее разделяющий 0, и за ним y единиц. Заранее спасибо!

Машина Маркова: удалить из слова P второе вхождение символа a, если такое есть
A={a,b,c}. Удалить из слова P второе вхождение символа a, если такое есть. Как сделать такое задания, я просто не могу понять как изменить символ чтобы удаляло именно вторую букву а. Помогите...

Машина Тьюринга (усеченная разность)
Функция f(x) = x - 2, где знак "-" это усеченная разность. 1. Построить машину Тьюринга (покомандно) правильно их вычисляющую.(алфавит 0 и 1) 2. Построить с помощью стандартных машин.

Машина Тьюринга. Нормированное сложение двоичных чисел
Доброго времени суток! Появилась задача - написать на эмуляторе машины Тьюринга в четверках программу нормированного (без изменения исходных данных) сложения двоичных чисел. Я написал решение для...

Машина Тьюринга, располагающая три цифры в порядке возрастания
1. На информационной ленте машины Тьюринга в трех секциях в произвольном порядке записаны три цифры: 1, 2, 3. Каретка обозревает крайнюю левую цифру. Необходимо составить функциональную схему машины...

Построить автомат, реализующий работу лифта
Здравствуйте форумчане, есть задание требующее построить КА реализующий работу 6-этажного лифта с возможностью приёма на борт пассажиров. Я бы это делал при помощи автомата с магазинной памятью так:...

Построить конечный автомат
Помогите, пожалуйста, построить КА (конеч. автомат), у которого алфавит из двух букв "a, b" и у которого язык состоит из слов, в которых буква a - встречается четное число раз, b - нечетное.

Построить диаграмму Мура.
пожалуйста помогите!!!

Построение автомата Мура
Здравствуйте! Имеется задание: построить автомат Мура, открывающий номерной замок с цифрами 1, 2, 3, 4, 5, как только сумма любых трех чисел последовательности, идущих подряд, станет нечетна....

Построить КС-грамматику
Построить КС-грамматику, порождающую цепочки в алфавите \sum = {0, 1}, в которых количество символов 0 на единицу больше, чем символов 1. Пжл :wall: :-[

Машина тьюринга для возведения в степень(в частности, в квадрат)
Требуется для написания курсовой механизм возведения числа в степень в унарном кодировании. алфавит А={^,|} .^-пусто.

Построить конечный автомат, выдающий остаток от деления вводимого троичного числа на 4
Всем привет, выдали вот такое задание по конечным автоматам : "Построить конечный автомат, выдающий остаток от деления вводимого троичного числа на 4. Построить два варианта автомата: для случая,...

Сортировка на машине Тьюринга
Помогите пожалуйста, у самой уже руки опускаются. На вход подается слово в алфавите аб, организовать сортировку с сохранением исходного слова, пример: абабаб=аааббб

Построить грамматику, порождающую формальный язык
1. L(G)={(ac)n| n>0, a∈{b, d}, c∈{+, -}} -составить грамматику, порождающую формальный язык -определить тип формальной грамматикии языка по классификации Хомского 2. В строке должна...

Задача по машине Поста и Тьюринга: Необходимо найти сумму чисел задданых в виде меток(для машины Поста) или единиц( для машины Тьюринга)
Необходимо найти сумму чисел задданых в виде меток(для машины поста) или единиц( для машины тьюринга) между числами не больше 1 пробела(если 2 пробела подряд это конец). каретка находится в крайней...

Машина Тьюринга: поменять местами нули и единицы
Дана последовательность из нулей и единиц. Написать программу машины, которая меняет местами нули и единицы (т.е. вместо нуля должна стоять единица, вместо единицы – нуль). S - множество внутренних...

Машина с бесконечными регистрами
Нужно на эмуляторе МБР написать программу для решения задачи. Задан массив из 10 элементов, определить является ли он монотонным. Команды МБР: S(n) // Увеличение значения регистра n на 1 ...

Как в интерпретаторе Машины Тьюринга в Алго200 поставить "стрелку вниз"
Здравствуйте. Скажите пожалуйста, как в интерпретаторе Машины Тьюринга в Алго200 поставить "стрелку вниз" (например, как в ячейке "Q3" -" " в таблице на видео...

Построить машину Тьюринга, вычисляющую след функции
Требуется построить машину Тьюринга, вычисляющую след функции: а) f(x,y)=0, если x=0 и =x-1, если x>0 б)f(x,y)=x, если x=2 и равно y во всех остальных случаях. Соображения по поводу первой...

Переставление букв в обратном порядке Реверс слова Нормальный алгортим Маркова
Доброго времени суток! :good: Суть заключается в том, чтобы переписать слово в обратном порядке: например aabbabbba -> abbbabbaa . Накидал вот такие подстановки: *a->x* *b->y* ay->ya

Разработать машину Тьюринга, которая увеличивала бы заданное число n на 1
Дано число n в восьмеричной системе счисления. Разработать машину Тьюринга, которая увеличивала бы заданное число n на 1. Автомат в состоянии q1 обозревает некую цифру входного слова. Кроме самой...

Машина Тьюринга. Найти произведение двух натуральных чисел m и n, заданных в унарной системе счисления
Здравствуйте. Помогите, пожалуйста, решить 1)Найти произведение двух натуральных чисел m и n, заданных в унарной системе счисления. Соответствующие наборы символов « | » разделены знаком « * », а...

Построить конечный автомат для распознания регулярного множества цепочек трехсимвольного алфавита
Построить конечный автомат (КА–распознаватель) для распознания регулярного множества цепочек трехсимвольного алфавита в соответствии с описанием: Содержит два символов “а”, заканчивается на “ b...

Нормальные Алгоритмы Маркова (НАМ). Проблемы с решением задачи
Дана вот такая задача по нормальным алгоритмам Маркова (НАМ). Нужно написать программу для алгоритмического эмулятора. Помогите с решением этой задачи, заранее благодарен:) Дан алфавит A = {0, 1}....

Алгоритм Маркова: деление нацело на числа в унарной СС
1. Разработать алгорифм Маркова для вычисления функции деления нацело на 2 числа в унарной системе счисления. 2. Написать алгорифм Маркова для вычисления функции f(x)=x –5, где x задано в...

Машина Тьюринга: перевод числа из троичной в единичную систему
Здравствуйте! Помогите, пожалуйста, составить алгоритм: Считая непустое слово Р записью числа в троичной системе, получить запись этого числа в единичной системе

Перевод двоичного числа в десятичное для машины Тьюринга
Пусть внешний алфавит состоит из символа “a0”, цифр 0, 1, 2, ..., 9 и символа “*”. На ленту записано натуральное число в двоичной системе счисления. Составьте функциональную схему для машины...

Машина Тьюринга Поменять местами буквы
Требуется реализовать алгоритм в алфавите A={0,1} , меняющий местами первую и последнюю буквы слова. Cамостоятельно реализовал такое же задание для Нормальных Алгоритмов Маркова, а вот с МТ...

Построение грамматик, конечные автоматы и регулярные выражения
Здравствуйте, поступил в забугорный институт на магистратуру, сразу появился предмет под названием Теория Информатики, прошло только 2 лекции на которых ничего толком не объяснили, ни примеров...

Алгоритм вычитания двух двоичных чисел для машины Тьюринга.
построить машину Тьюринга реализующую алгоритм вычитания двух двоичных чисел (заведомо известно первое больше 2)

Машина Тьюринга: f(x, y) = x + 3y
Всем привет! Нужно составить МТ для функции f(x,y)=x+3y, для чисел 0,1,2,3,4... . Допустим на вход подается 20#11. У меня получается, допустим, для | и О, но тут что-то не могу догадаться.

Машина Тьюринга. Умножение чисел в двоичной системе счисления
Подскажите, может кто-нибудь знает алгоритм для умножения чисел в двоичной системе счисления

Машина Поста: присоединить к массиву справа одну метку
2) На информационной ленте справа от каретки, стоящей под пустой клеткой, находится массив меток. требуется присоединить к этому массиву справа одну метку. протестируйте программу, при условии, что...

Машина Тьюринга: удвоение числа на ленте
Построить МТ, удваивающую число на ленте (п-р 01110 --> 01111110) ответ должен быть в таком виде (примерно) q10-> q20R q20 -> q21R q20 -> q30L q30 -> q41L q40 -> q01L Заранее спасибо :)

Построить машину Тьюринга, которая преобразует запись числа из двоичной системы счисления в восьмеричную
Построите машину Тьюринга, которая преобразует запись числа из двоичной системы счисления в восьмеричную. Я вообще не понимаю как создается машина Тьюринга и как с ней работать -> lf;t даже самые...

Машина Поста: сложение двух двоичных чисел
Помогите пожалуйста!!! Как реализовать сложение двух двоичных чисел на машине Поста?!?!? Заранее спасибо!

Как написать машину Тьюринга для такой функции?
пыталась сделать, но не получается подскажите, как это сделать?

Машина Поста. Как можно сравнить 2 массива меток (одинаковые они по длине или нет)
Подскажите, как можно сравнить 2 массива меток одинаковые они по длине или нет? Если я смогу при помочи алгоритма понять, что например эти массивы меток одинаковы, то я могу например стереть все...

Машина Тьюринга. Вычислить значение данной функции
f(x,y)=y-5x Составить программу реализующую машину Тьюринга, вычисляющую значение данной функции f(x,y). Числа x,y>0 соответствуют на ленте наборам из x и y единиц соответственно. Наборы единиц...

Построить автомат, распознающий все слова в алфавите (a,b,c) кроме слов bc, bac
Помогите решить задание: построить автомат распознающий все слова в алфавите (a,b,c) кроме слов bc, bac

Скопировать число, записанное в унарной системе счисления (машина Поста)
Машина поста! Спасите!) Скопировать число, записанное в унарной системе счисления. Каретка расположена на самой левой метке, входящей в число.

Машина Тьюринга - определить, является ли P словом ab
A={a,b,c}. Определить, является ли P словом ab. Ответ (выходное слово): слово ab, если является, или пустое слово иначе.

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

Составить программу умножения двух чисел a и b (машина Поста)
Составить программу умножения двух чисел a и b

Построить автомат с магазинной памятью и кс-грамматику
Построить автомат с магазинной памятью и кс-грамматику, задающие язык, содержащий те и только те слова в алфавите {0,1}, в которых число единиц больше числа нулей ровно на пять и которые содержат...

Построить все сентенциальные формы для грамматики с данными правилами.
Помогите пожалуйста, скоро зачёт!!! 3) Построить все сентенциальные формы для грамматики с правилами: S -> A+B | B+A A -> a B -> b В 3 задании сентенциальные формы: S->A+B->a+B->a+b...

Машина Тьюринга. Написать программу умножение произвольного числа в десятичной форме на 11
Доброго времени суток! Нужно написать программу умножение произвольного числа в десятичной форме на 11 на машине Тьюринга. Заранее спасибо P.S. Програму на емуляторе машини Тьюринге

Машина Тьюринга. Приписать справа к слову P символ bс
Помогите решить: A={a,b,c}. Приписать справа к слову P символ bс (P->Рbс) 3. A={a,b,c}. Оставить в слове Р только последний символ (пустое слово не менять).

Машина Тьюринга: вычисление функции f(x) = 4x
Здравствуйте. Мне нужен совет по машине Тьюринга. Допустим дана функция f(x)=4x. Алфавит {0,1 } и допускается использование пробела. Как я понимаю, на ленты мы вводим число, далее это число...

Построить конечный детерминированный автомат
Привет всем помогите построить точнее нарисовать нетдетермениванный и детерменированный автомат по следующему правилу, работаю и некогда учить притом что учёба не на родном языке. L(G)={w|w...

Структурный синтез автомата Мили!
Ребята помогите решить эту задачу!! Очень нужно. Требуется провести структурный синтез автомата каноническим методом. JK-тригер Базис - И/ИЛИ/НЕ Очень прошу помощи!

JK-триггер,карты Карно
Добрый вечер! Подскажите пожалуйста,как правильно заполнить таблички карт Карно для JK триггера. Вот составленная мною табличка управляющих сигналов счетчика: А вот эти таблички надо заполнить:...

Построить автомат с магазинной памятью, распознающий множество
в данный момент сижу на экзамене, кто может чем помочь, помогите 1) построить автомат с магазинной памятью, распознающий множество {10n1m01}, n,m > 0 , n<>m. нужны не программы, а просто текст,...

Построить нормальный алгоритм Маркова, который в любом слове из алфавита А удваивал все буквы, стоящие на четных местах
Построить нормальный алгоритм Маркова, который бы в любом слове из алфавита А={a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,r,s,t,u,v,w,x,y,z} удваивал все буквы, стоящие на четных местах в исходном слове.

Найти метку на машине Поста
Известно, что на ленте есть метка , напишете программу которая находит её

Опишите ДКА, допускающие такие языки над алфавит {0, 1} множество цепочек, в которых число нулей делится - на пять
Опишите ДКА, допускающие такие языки над алфавит {0, 1} множество цепочек, в которых число нулей делится - на пять, а число единиц - на три.

Машина Тьюринга: предикат "x^2 делится на 4"
Помогите, пожалуйста, составить программу для машины Тьюринга, вычисляющей заданную арифметическую функцию: Предикат "x^2 делится на 4"

Машина Тьюринга: если P-непустое слово, то за его первым символом вставить символ а
Здравствуйте, помогите пожалуйста. А) А= {a,b,c}. Если P-непустое слово, то за его первым символом вставить символ а. Б) Умножить число, в десятичной системе счисления на 2.

Схема преобразование кода 8421 в код 7421
Доброе время суток. Надо схема на логических элементах преобразования двоично-десятичного кода 8421 в двоично-десятичного кода 7421. Если есть у кого поделитесь пожалуйста, или посоветуйте...

Доказательство нерегулярности языка
Приветствую. Есть 2 алфавита и язык: A_1 = \{a,b,c\}\\A_2 = \{a,b,c,1,2\}\\L = \{w_11w_2| w_1, w_2 \in A_{1}^{*}, w_{1}^{a} = w_{2}^{c}\} \cup \{w_12w_2| w_1, w_2 \in A_{1}^{*}, w_{1}^{b} =...

Нормальный алгоритм Маркова. Если слово состоит из нечетного количества символов - удалить средний
Есть условие:А={а, b, c}. если слово Р нечетной длины - удалить средний символ. Подскажите, пожалуйста, как определить имеет ли слово нечетную длину и как найти положение середнего символа, чтобы...

Машина Тьюринга: целочисленное деление числа на 2
как записать программу для машины Тьюринга целочисленного деления чисел на 2. Головка расположена слева от числа.

Доказать, что следующий язык не является КС-языком
Доказать, что следующий язык не являются КС-языком: L = { a^n b^m a^m b^n | m>=0 ,n >=0}

Составить программу для машины Тьюринга, которая увеличивает двоичное число на 1
ПОМОГИТЕ ПОЖАЛУЙСТА Составьте программу для машины Тьюринга, которая увеличивает двоичное число на 1.

Машина Тьюринга: Определить, делится ли десятичное число на 5 без остатка
помогите разобраться. На ленте машины Тьюринга находится десятичное число. Определить, делится ли это число на 5 без остатка. Если делится, то записать справа от числа слово “да”, иначе — “нет”....

Транспозиция в машине Тьюринга
Помогите пожалуйста сделать транспозицию в машине Тьюринга (это когда на пример на ленте было число 111_11, а стало 11_111).

Алгоритм Маркова. Удалить вторую половину слова, состоящего из ab
Буду благодарна за помощь в решении данной задачи. Нужно удалить вторую половину слова, состоящего из ab, с помощью алгоритма Маркова.

Машина Тьюринга (НОД)
Ребят, всем привет! Может кто-нибудь помочь с задачкой? Задача такова: Есть два конечных набора из m и n единиц записанных на ленту подряд. Машина в начальном положении должна обозревать крайнюю...

Машина Поста: двукратное копирование группы единиц
Реализовать с помощью машины Поста двукратное копирование группые единиц. Помогите, пожалуйста. Хотя бы просто с копирование группы единиц, если с двукратным сложно будет. Очень жду ваших...

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

D триггер на элементах 2ИЛИ-НЕ, монтажное ИЛИ
Добрый вечер. Помогите пожалуйста построить синхронный D-триггер на элементах 2ИЛИ-НЕ, монтажное ИЛИ. Заранее спасибо.

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

Построить Машину Тьюринга вычисляющую сложение двух двоичных чисел
Не понимаю принцип, сколько бы не читал. Очень нужна ваша помощь

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

Составить грамматику, порождающую формальный язык
1. Составить грамматику, порождающую формальный язык: L(G)={wcwcw | wЄ{a, b}^+}; 2. Определить тип формальной грамматики и языка по классификации Хомского; Единственный вариант решения, который у...

Машина Тьюринга, поиск одинаковых слов на ленте
Помогите, пожалуйста, с заданием. Реализовать машину Тьюринга со стандартной заключительной конфигурацией для выполнения следующей задачи. На вход подается множество слов в алфавите {a,b,c},...

Написать программу для машины Тьюринга, которая движется влево, останавливается на последнем символе последовательности
Подскажите как решить 1. Написать программу для машины Тьюринга, которая движется вправо, не останавливаясь, каждый третий символ заменяет на 0. 2. На ленте записано последовательность нулей и...

Составьте Нормальный алгоритм Маркова для следующих условий: A={a,b,c}. Приписать слово bac слева к слову P
НАПИСАТЬ ПРОГРАММУ НА ЯЗЫКЕ С\С++. Составьте Нормальный алгоритм Маркова для следующих условий: A={a,b,c}. Приписать слово bac слева к слову P. Как это сделать я не знаю, помогите пожалуйста

Закодировать алфавит методом Шеннона-Фано и Хаффмана
Нужно закодировать алфавит K = {k1, k2, k3, k4, k5} двоичным кодом, если вероятности букв следующие: p(k1) = 0.05 p(k2) = 0.5 p(k3) = 0.05 p(k4) = 0.25 p(k5) = 0.25 Выполнил задание, но не...

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

Нормальный алгоритм Маркова: остаток при делении числа на 5
Здравствуйте. Помогите, пожалуйста, составить алгоритм Маркова, вычисляющий остаток при делении числа на 5. Алфавит A={0,1,2,3,4,5,6,7,8,9}

Выяснить, применима ли машина Тьюринга, заданная программой Р, к слову S
Что-то очень подозрительное с Машиной Тьюринга Здравствуйте! Нужно решить задачу, но не могу вообще понять, как это сделать. Поиск решений в гугле ничего не дал. Впервые сталкиваюсь с машиной...

Как записать цифры числа в обратном порядке в машине Тьюринга?
На ленте машины Тьюринга записано число в десятичной системе счисления. Каретка находится над крайней правой цифрой. Записать цифры этого числа в обратном порядке.

Нормальный Алгоритм Маркова. Получить в этой же системе число n
A={ | }. Пусть слово P является записью числа 2^n (n=0, 1, 2, …) в единичной системе. Получить в этой же системе число n. Добавлено через 2 минуты Видел на форуме про степени тройки,но все равно...

Построить грамматику, порождающую язык
Построить грамматику, порождающую язык L(G)=\left Добавлено через 15 часов 41 минуту S -> 22A1 A -> 2 Так чтоли ?

Алгоритм Маркова: деление нацело на 2 в унарной системе
Разработать алгорифм Маркова для вычисления функции деления нацело на 2 числа в унарной системе счисления. Наработки есть, но правильно работать никак не могу заставить. Буду благодарен за любые...

Построение автомата с магазинной памятью по кс грамматике. Определить входную строку
Здравствуйте! Дана контекстно-свободная грамматика: G=({S, R, T, X, Y}, {a, b, p, g, y}, P, S), где P: S→R|T; R→pX|paR|paT|ε; T→Tg|g; X→aXb; Y→aYa|y. Последовательность построения...

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

Машина Тюринга: приписать справа к слову P символы bc (P → Pbc)
A={a,b,c}. Приписать справа к слову P символы bc (P → Pbc).

Задача – Программирование машин Тьюринга
Разработать алгоритм решения задачи согласно индивидуальным заданием. Использование дополнительных символов, не входящих в алфавит А, должно быть обосновано. Составить программу для мышиных...

Машина Поста: выяснить, одинаковы ли массивы меток по длине
Помогите пожалуста На ленте машины Поста находятся два массива в m и n меток. Составить программу выяснения, одинаковы ли массивы по длине.

Алгоритм Маркова: если количество символов "а" - степень 2, то нужно оставить цепочку без изменения
Здравствуйте! Подскажите, пожалуйста, как можно построить алгоритм Маркова для следующей задачи: На вход подаётся цепочка, состоящая из символов "a". Если количество этих символов - степень 2, то...

Нормальный алгоритм Маркова: если в слове нечетное количество букв, то после каждой буквы поставить "!"
Здравствуйте, помогите, пожалуйста! Составить нормальный алгоритм маркова: если в слове нечетное количество букв, то после каждой буквы поставить !

Доказать, что язык нерегулярный
Довести что язык \left нерегулярный

Построить грамматику
Очень нуждаюсь в помощи. Не хочу плакаться, но с виду наверно так и смотрится. Учусь заочно. 1,5 года назад были лекции по Теории автоматов. Из-за работы попал только на несколько лекций. Сразу не...

Построить детерминированный автомат для регулярного выражения
Построить детерминированный автомат для регулярного выражения ((c+a)b*)* Я построил этот автомат какие состояния будут финальными и почему? Тут в регулярном выражение две звёздочки подряд как...

Машины Тьюринга. Является ли Р словом ab
Помогите, пожалуйста, выполнить 2 задания по теории алгоритмов на тему Машины Тьюринга. 1) A = {a, b, c}. Определить, является ли P словом ab. Ответ (выходное слово): слово ab, если является, или...

Сложение по модулю 2 в 32 степени
Помогите проверить правильно ли сложил по mod 2 в 32й степени R0: 11010001 11000000 11001101 11000100 X0: 11001101 11000101 11010001 11001010 K1: 10011111 10000110 10011111 ...

Построить детерминированный конечный автомат
Построить детерминированный конечный автомат, распознающий язык L над алфавитом {a,b}, состоящий из цепочек следующего вида: если цепочка содержит два или более вхождений символа a, то она содержит...

Машина Тьюринга. Выполнить деление исходного числа на 2
Начальная конфигурация – запись произвольного четного числа в унарной СС; обозревается произвольная цифра. Требуется выполнить деление исходного числа на 2.

Синтез синхронного автомата Мили и Мура
Здравствуйте , помогите пожалуйста как правильно построить таблицы выходов и как отметить на графе правильно Задание стоит такое 1. Получите автоматный граф для цифровых автоматов Мура и Мили, ...

Машина Тьюринга: перевод из троичной в двоичную систему
Помогите, пожалуйста, разобраться с переводом из 3-ой в 2-ую систему счисления на Машине Тьюринга. Обязательно ли сначала переводить в десятичную?

Построить машину Тьюринга для умножения числа на 2
Народ нужна помощь в данном задании, буду вам предельно благодарна: Построить машину Тьюринга для умножения числа на 2. Число задается в десятичной системе счисления , каждая цифра в отдельной...

Машина Тьюринга: умножение произвольного числа на 3
Здравствуйте. Надо умножить произвольное число на 3. Нашла готовое решение. Кто может, объясните, пожалуйста, шаг 11, 15, 21, 25 и вообще, что происходит когда машина возвращается к одному из...

Машина Тьюринга. Оставить в слове P только первый символ (пустое слово не менять)
A={a,b,c}. Оставить в слове P только первый символ (пустое слово не менять).

Написать машину Тьюринга, которая исправляет ошибку в слове «иксковотар»
1.Написать машину Тьюринга, которая исправляет ошибку в слове «иксковотар». 2.Дано натуральное число n > 1. Разработать машину Тьюринга, которая уменьшала бы заданное число n на 1, т.е. выполняла...

Построить в алфавите {0,1} машину Тьюринга
Построить в алфавите {0,1} машину Тьюринга, переводящую конфигурацию К1 в конфигурацию К0. К1 = 0q1 nn0 К0 = 0q0 n0, n≥1 (каретка находится в...

Машина Тьюринга: подсчитать количество буквосочетаний "аб" и "ба" во входном тексте
Помогите с решением задачи с помощью машины Тьюринга! Условие. Подсчитать количество буквосочетаний "аб" и "ба" во входном тексте. Считаем, что их не может быть больше 12.

Построить нормальную машину Тьюринга. P запись четверичного числа, получить остаток от деления этого числа на 4
Помогите пожалуйста. Построить нормальную машину Тьюринга. A={0,1,2,3}. Считая непустое слово P записью четверичного числа, получить остаток от деления этого числа на 4.

Построение таблицы для конечного автомата на основании диаграммы Мура
Второй день вникаю, разобрался как в примере на основании таблицы строить диаграмму. Однако в своем задании мне нужно наоборот на основании диаграммы Мура построить таблицу: на диаграмме...

Определить тип грамматики по Хомскому
Помогите пожалуйста определить тип грамматики по Хомскому, правила которой имеют вид S -> аbSba S -> a и объясните, почему вы пришли к такому выводу.

Алгоритм Маркова - считая непустое слово P записью двоичного числа, определить, является ли это число степенью 2
Добрый день. Подскажите, как создать машины Маркова для этих задач: 2. A={0,1}. Считая непустое слово P записью двоичного числа, определить, является ли это число степенью 2 (1, 2, 4, …). Ответ:...

Машина Тьюринга и алгоритм Маркова
помогите пожалуйста ребят, очень срочно надо. К Тьюрингу нужно составить только пример как на рисунках 2 и 3 во вложенном файле, а в Маркове доработать алфавит так чтобы входное слово осталось...

Прикладное применение теории автоматов
Добрый день, форум. Мучилась на днях с курсовиком по автоматам. И это оказалось довольно интересно, даже пожалела, что все пары прогуляла. Собственно вопрос такой, а что можно описать с помощью...

Машина Тьюринга: вычисление факториала числа в унарной системе
Уважаемые люди, прошу помочь с идеей осуществления вычисления факториала числа в унарной системе. Я умею писать в ней, но мне не понятно по какому принципу вообще это осуществить... Вобщем надо...

Построить конечный автомат по заданной регулярной грамматике
G=({a, b, c}, {S, A, B, C}, P, S), где P={ S→aA | bB | aC; A→bA | bB | c; B→aA | cC | b; C→bB | bC | a} 1) Построить конечный автомат по заданной регулярной...

Построить машину Тьюринга, вычисляющую числовую функцию
Приветствую :friends:. Помогите с заданиями: 1. Построить машину Тьюринга, вычисляющую числовую функцию f(x,y)={y, esli x=1,x+2, esli x\ne(не равен) 1} - не могу эту формулу в Латексе вбить (ну...

Машина Тьюринга. Алгоритм сложения чисел в троичной системе счисления.
Помогите пожалуйста написать программу для сложения двух чисел в троичной системе счисления.очень нужно,а я совсем понять не могу как это сделать!

Нормальный алгоритм Маркова. Как делается умножение
Подскажите пожалуйста как делается умножение ?

Реализовать возведение числа в квадрат на машине Поста
Привет. Нужно реализовать возведение числа в квадрат на машине Поста.

Машина Тьюринга вычисление предиката
помогите пожалуйста с задачей, очень нужно((( Построить машину Тьюринга, которая вычисляет предикат P(a) (a - последовательность нулей и единиц) определенный следующим образом: P(a) = И, если a...

Машина Тьюринга, написание программы для вычисления функции f(n)=n-2 (=0, если n=0,1)
Записать в алфавите {a,l,*} программу машины Тьюринга для вычисления функции f(n)=n-2 (=0, если n=0,1) Помогите, пожалуйста, до меня не доходит.....

Закодировать буквы методом Хемминга
закодировать буквы А и Р методом Хемминга А - 192 - 11000000 Р - 208 - 11010000 дальше сделайте плиzzz

Построение конечных автоматов "делимость на 4" и "делимость на 7"
Как строятся эти автоматы вообще? Это можно понять, не вдаваясь в глубины мат. логики..? Есть ли простой способ понимания этих построений?

построение Машины Тьюринга
Добрый день!Помогите пожалуйста объяснить как построить машину Тьюринга Дана задача: Постройте машину Тьюринга,вычисляющую след. функцию, заданную на N*N: {x}^{2}+3y Не могу никак понять как...

Построить Конечный детерминированный автомат, распознающий непустые цепочки символов в алфавите
Построить Конечный детерминированный автомат, распознающий непустые цепочки символов в алфавите {0,1} такие, что между двумя нулями содержится не менее 3 единиц. Его построил можете пожалуйста...

Построить контекстно-свободную грамматику, порождающую язык
Построить кс грамматику пораждающею язык: a^n b^3m a^5 b^3 c^2n c^m n>0 m>0:n>0 m>0 более точно написано на скриншоте Я построил вот так не знаю правильно ли это? S->ABCDKM A->a B->bbb...

Построить машину Тьюринга. Если P – слово чётной длины (0, 2, 4, …), то выдать ответ a, иначе – пустое слово
A={a,b,c}. Если P – слово чётной длины (0, 2, 4, …), то выдать ответ a, иначе – пустое слово.

Построить машину Тьюринга, переписывающую последовательность символов в обратном порядке
Всем привет!! ))) Дано задание: Построить машину Тьюринга, переписывающую последовательность символов из a,b,c в обратном порядке Наверное надо идти вправо до конца, менять знак, идти влево,...

Машина Тьюринга. Заменить каждый четвертый символ на символ «/» (отсчет символов начинается с правого края строки)
На информационной ленте машины Тьюринга содержится непрерывная последовательность символов «|». Сконструируйте машину Тьюринга, которая заменит каждый четвертый символ на символ «/» (отсчет символов...

Удвоить каждый символ в слове P (например: bacb → bbaaccbb)
A={a,b,c}. Удвоить каждый символ в слове P (например: bacb → bbaaccbb). Помогите решить задачу, я вообще не разбираюсь но нужно решить.

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

Машина Тьюринга: слово P имеет чётную длину, оставить в нём только левую половину
A={a,b,c}. Слово P имеет чётную длину оставить в нём только левую половину. Не могу понять как найти в слове середину, помогите

Машина Тьюринга. Разность двух чисел, если известно, что первое число больше второго.
Привет всем! Помогите, пожалуйста, разработать машину Тьюринга: Даны два целых положительных числа в десятичной системе счисления. Сконструировать машину Тьюринга, которая будет находить разность...

Алгоритм Маркова. Как завершить алгоритм?
Задание звучит так: На ленте записано выражение 2^n .Получить результат операции в двоичной СС. - Как его делать, с помощью препода более-менее разобралась. Система подстановок выглядит...

Машина Тьюринга: заменить на "а" каждый второй символ в слове P
1.Алфавит А={a,b,c}. Заменить на а каждый второй символ в слове P. Слово P произвольное. 2.Алфавит A={a,b,c}. Пусть слово P имеет нечётную длину. Оставить в этом слове только средний символ.

Как построить граф к автомату Мура?
Приветствую, делаю курсовую работу по ТА, но не могу построить граф для автомата Мура. Для автомата Мили понятно как делать. Здесь 1 начальное состояние, а вот в Муре всё более сложно, здесь...

Построить машину Тьюринга для вычисления функции "усеченная разность"
10. Построить машину Тьюринга для вычисления функции. Внешний алфавит состоит только из 0 и 1, 0 – пустой символ. Пояснения по построению программы для МТ обязательны. Проверить работу машины...

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

Машина Тьюринга: вычисление функции y=x/2
Как строить машину для вычисления следующей функции? x/2 Добавлено через 2 часа 32 минуты :):):):):)

Построить машину Тьюринга для преобразования слова P в слово Q
Построить машину Тьюринга для преобразования слова P в слово Q: правильно ли я построил взгляните хотяб одним глазком пожалуйста... или что то не так?!

Машина Тьюринга: бинарное умножение
Помогите пожалуйста с задачей : f(x)=x*4; По сути нужно чтоб машина умножала введенное число в двоичной системе исчисления на 4(то есть 100 в двоичной) Заранее спасибо за помощь

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

Машина Тьюринга с внешним алфавитом А=(а0, 1), которая каждое слово длиной n в алфавите А1=(1) перерабатывает в слово
сконструируйте машину Тьюринга с внешним алфавитом А=(а0, 1), которая каждое слово длиной n в алфавите А1=(1) перерабатывает в слово длиной n+1 в том же алфавите А. использовать алфавит внутренних...

Реверс слова. Нормальный алгортим Маркова
Доброго времени суток! Суть заключается в том, чтобы переписать слово в обратном порядке: aabab -> babaa Накидал такие подстановки: *a->x* *b->y* ay->ya ax->xa

Считая слово P записью числа n в единичной системе, получить в этой же системе число 2^n
Машина Тьюринга A={ | }. Считая слово P записью числа n в единичной системе, получить в этой же системе число 2^n. Хелп, не могу подобрать алгоритм. Даже не знаю, как это реализовать

Увеличение числа в унарной системе на 1
В двоичной машине Поста дан массив меток, который обозначает число в унарной системе исчисления. Требуется получить на ленте запись числа, которое на 1 больше входного. Вначале и в конце действий...

Построить кс-грамматику языка
Здравствуйте, помогите пожалуйста решить задачу. Как строить дерево я вроде как понимаю, а вот как построить кс-грамматику нет... Постройте КС-грамматику языка, определяющего для цепочек вида: xz...

Машина Тьюринга должна выдать 0, если число нулей больше и 1 – в противном случае
доброго времени суток Надо написать правила машины Тьюринга для решения задачи: На вход поступает последовательность из 0 и 1. Машина должна выдать 0 если число 0-ей больше и 1 – в противном...

Машина Тьюринга: поменять местами крайние буквы
Построить машину Тьюринга согласно заданию. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии. На информационной ленте машины Тьюринга в трех секциях в...

Машина Тьюринга. Удалить из слова P его третий символ, если такой есть
A={a,b}. Удалить из слова P его третий символ, если такой есть.

Написать алгоритм для машины Тьюринга (вычисление функции)
Построить машину Тьюринга для вычисления функции. Внешний алфавит состоит только из 0 и 1, 0 – пустой символ. Проверить работу машины Тьюринга для конкретных значений x,y Вот функция: f(x,y) =...

Регулярное выражение - множество цепочек, состоящих из нулей и единиц, в которых число нулей кратно пяти
Помогите, пожалуйста, составить регулярное выражение. "множество цепочек, состоящих из нулей и единиц, в которых число нулей кратно пяти." Вариант был (00000)?, но ведь нули то могут и не рядом...

В чём отличие таблицы переходов триггера от таблицы функций возбуждения?
В чём отличие таблицы переходов триггера от таблицы функций возбуждения?

Машина Маркова. Если слово четное - оставить правую половину слова, иначе стереть все
Нужно составить программу. А={а, b, c}. Если слово четной длины - оставить правую половину слова, иначе стереть все. Не могу понять, как определять количество символов в строке.

Машина Поста, составить программу целочисленного деления двух чисел
Составить программу целочисленного деления двух чисел a и b.

Машина Тьюринга: перенести первый символ непустого слова в его конец.
Составить программу для машины-Тьюринга: A={a,b,c}. Перенести первый символ непустого слова Р в его конец!

Машина Тьюринга: перевернуть слово Р
A {a,b} Перевернуть слово Р ( пример:abb->bba) Не могу никак решить эту задачу машиной Тьюринга

Как построить карту Карно для такой таблицы
Добрый день, форум. Я запуталась с картами Карно, подскажите пожалуйста, как для такой таблицы ее построить. Мне не понятно, что писать в результирующие ячейки, ведь на пересечениях строк таблицы...

Машина Тьюринга: разность двух чисел
Помогите пожалуйста разработать МТ Даны два целых положительных числа в десятичной системе счисления. Сконструировать машину Тьюринга, которая будет находить разность этих чисел, если известно, что...

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

Машина Тьюринга. Перевод числа из 4-ричной СС в 10-ичную СС
Здравствуйте. Может есть у кого алгоритм перевода числа из 4 СС в 10 СС? Или может кто хорошо разбирается, сможет помочь? Буду весьма признателен.:help:

Машина Тьюринга для распознавания равенства слов
Здравствуйте, у меня задача... Написал машину, которая распознает равенство двух слов.. Сориентируйте меня, пожалуйста Есть пример... Его я понимаю, но у меня сомнения достаточно ли такого алфавита...

Составьте для машины Поста программу, складывающую несколько чисел
На ленте записано несколько чисел (в виде массива из меток), каждое число отделяется от другого одним пробелом. Составить машину Поста сложения этих чисел (например, vvv v vv -> vvvvvv).

Описать язык, порождаемый грамматикой, имеющей следующее правило
Описать язык порождаемый грамматикой имеющие следующее правила S->bSS|a Нашёл вот такое описание L={u|u ∈ (a, b)* |a|=|b|+1 причём цепочка называется с терминала b и заканчивается терминалом a} ...

НАМ деления двух натуральных чисел
Здравствуйте, новичок на вашем форуме. Помогите пожалуйста составить НАМ вычисляющий деление двух натуральных чисел. Целый день потратил и ничего не смог придумать, очень нужна помощь. Просмотрел...

Алгоритм Маркова - преобразовать слово так, чтобы сначала шли символы a, затем – символы b и в конце – символы с
Добрый день. Подскажите, как создать машины Маркова для этих задач: 1. A={a,b,c}. Преобразовать слово P так, чтобы сначала шли все символы a, затем – все символы b и в конце – все символы c. ...

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

Заменить предпоследнее вхождение подстроки abc в слове на bca (нормальный алгоритм Маркова)
Дано слово состояшее из символов {a,b,c} необходимо заменить предпоследнее вхождение подстроки abc в слове на bca.

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

Построение модели конечного автомата: модель кодового замка с пятью кнопками
Построить модель кодового замка с пятью кнопками (А, Б, В, Г, Д), открывающегося при наборе кода В*Д и остающегося открытым, пока не нажата кнопка Д. Символ * \epsilon Y означает, что ни одна кнопка...

Необходимо реализовать на машине Тьюринга умножение на 9 целого троичного числа.
помогите решить задание в машине Тьюринга Необходимо реализовать умножение на 9 целого троичного числа Добавлено через 21 час 15 минут спасибо что переместили в нужную тему

Машина Тьюринга: преобразование чисел из двоичной системы счисления в десятичную и наоборот
Всем привет. Интересует такой вопрос: Как реализовать Машину Тьюринга для преобразования чисел из двоичной системы счисления в десятичную, и наоборот? Я с МТ вообще плохо разбираюсь :( Заранее...

Машина Тьюринга: поиск простого числа (с моим решением)
Здрасте =) Задача: построить МТ, высчитывающая сумму всех ПРОСТЫХ чисел, которые <=X. мне не нужно строить всю таблицу состояний и проч. Нужно объяснить преподу алгоритм, чтобы он сказал...

Машина Тьюринга, умножающая число на 11
На ленте машины Тьюринга находится число, записанное в десятичной системе исчисления. Умножьте это число на 11, если каретка находится над крайней правой цифрой числа. Помогите, пожалуйста, завтра...

Описание КС-грамматики входного языка в форме Бэкуса—Наура.
Описание КС-грамматики входного языка в форме Бэкуса—Наура. Что вообще не могу разобрать его незнаю с чего начать вот мое задание Входной язык содержит арифметические выражения, разделенные...

Машина Поста - удвоить массив
Удвоить массив из n-меток дважды. Каретка располагается над правой ячейкой

Написать программу МТ, которая удваивает любое входное слово в заданном алфавите
МТ я запрограммировал, работает, вроде бы... Но не понятно, правильный ли я получаю результат? Например мы вводим выражение "abba" на выходе получим "abba|abba". Смущает маркер | , который я...

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

Построить Машину Тьюринга для f(x,y)=2x-y
Построить следующую машину Тьюринга, вычисляющую функцию: f(x,y)=2x-y

Машина Тьюринга - подсчет букв в словах
Здравствуйте. На вход подается множество слов в алфавите {a, b, c}, разделенных одним пустым символом. На выходе должны быть написаны буквы, встречающиеся не менее чем в половине слов. Буду...

Машина Тьюринга. Уменьшение массива в 3 раза
Здравствуйте. Можете помочь? Никак не получается. На ленте машины Тьюринга находится массив 2N символов “*”. Уменьшите этот массив в 3 раза. Желательно с пояснениями, чтобы разобраться. Заранее...

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

Построить граф автомата Мили
Построить граф автомата Мили, реализующего полученный автоматный оператор. Х1 Х2 Х3 Х4 У1 У2 У3 У4 0 1 1 0 1 0 0 0 0 1 0 0 0 1 0 1 1 0 0 0 1 0 1 1 1 ...

Сложение четырех целых без знака (Машина Поста), Троичное вычитание "-1" (Машина Тьюринга).
Здравствуйте! Можете пожалуйста помочь с задачками: Машина Поста: Сложение четырех целых без знака? Машина Тьюринга: Троичное вычитание "-1"? Заранее спасибо!

Машина Поста, Вычислить разность массивов
На ленте заданы два массива m и n. m>=n. Вычислить разность этих массивов. Каретка располагается по середине этих массивов. (между массивами 3 клетки, каретка в средней)

Машина Тьюринга - приписать слева к непустому слову его первый символ
Друг попросил помочь найти в интернете решение двух задач. А={a,b,c}. Приписать слева к непустому слову P его первый символ. A={a,b,0,1} Определить, является ли слово P записью числа в двоичной...

Машина Тьюринга и алгоритмы Маркова. Машина Поста.
Нужна помощь с записью данных ниже задач на бумаге. В C++ с решением проблем нет, но как записать алгоритм на бумаге понятия не имею, надеюсь на вашу помощь. Машина Поста: На ленте машины Поста...

Машина Тьюринга и НАМ для f(x)=2 если y=2x; 1 иначе
Дорогие форумчане, у меня есть опыт написания машины тьюринга и нормального алгоритма Маркова для линейно заданных функций, но для системы, я не понимаю, как писать. Любые подсказки и ссылки на...

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

Машина Поста: сжать массив так, чтобы все n меток занимали n расположенных подряд ячеек
На ленте машины Поста расположен массив из n меток (метки расположены через пробел). Нужно сжать массив так, чтобы все n меток занимали n расположенных подряд ячеек. Как решить эту задачу?

Алгоритм Маркова: аннулировать слова вида x#x в алфавите {a,b}*
Здравствуйте! Подскажите пожалуйста... Задание: аннулировать слова вида x#x в алфавите {a,b}* т.е. аннулировать слова такие как abab, aabaab, aa, abba и тд. Предполагаю, что нужно найти...

Машина Тьюринга: перевернуть любое четырехбуквенное слово
Нужно составить машину Тьюринга, которая бы переворачивала любое четырёхбуквенное слово. Алфавит состоит из {A, B, C, *, 0, 1}, но 0 и 1 не могут быть в исходных данных. Если в слове количество букв...

Написать формулу числовой функции, вычислимой машиной Тьюринга
Приветствую :friends:. Нужна ваша помощь с машиной Тьюринга. 1. Написать формулу числовой функции f({x}_{1},x_2,...,x_n), вычислимой машиной Тьюринга с множеством внтуренних состояний...

Машина Тьюринга умножение в двоичной системе
Помогите пожалуйста написать программу 0,1 умножить на 7 ( или в двоичной системе 111)..... очень срочно надо

Составить регулярное выражение для языка
Есть 2 задания: -- На всех нечетных местах каждого слова находится a. -- В каждом слове не менее 4-х букв b. Алфавит А = {A, B, C} Для второго задания я сделал: (a|bbbb|c)* А для первого не...

Сравнение двух чисел в унарной системе счисления [Машина Тьюринга]
Здравствуйте, дорогие обитатели форума. Возникла такая проблема как сравнение к примеру двух чисел (111?11111) в Машине Тьюринга. Сама суть того, что я хочу сравнить два числа и заменить знак "?"...

Составить НАМ. Если слово P начинается с символа a, то заменить P на пустое слово, а иначе P не менять
Помогите понять, как сделать задание. A={a,b,c}. Если слово P начинается с символа a, то заменить P на пустое слово, а иначе P не менять

Таблица функций возбуждения триггеров
Нужна таблица функций возбуждения RS-триггеров. Знаю, что для ее получения нужно сделать преобразование таблицы переходов по характеристической таблице. А каким образом делать это преобразование?

Построить Машину Тьюринга, правильно вычисляющую функцию f(x)=[1/x-3]
Здравствуйте! Нужна помощь в решении задачи с Машиной Тьюринга. f(x)= не понимаю к чему тут скобки квадратные и как "ПРАВИЛЬНО ВЫЧИСЛИТЬ". Кто разбирается в МТ?

Построить нормальный алгоритм Маркова, применимый ко всем словам в алфавите
Построить нормальный алгоритм, применимый ко всем словам x1x2...xn в алфавите {a, b} и переводящий их в слово aa, если число букв b нечетно и x1x2...xn-1, если четно Добавлено через 9 минут...

Алгоритм Маркова. Если в слове P не менее двух символов, то переставить два первых символа
Помогите пожалуйста A={a,b,c}. Если в слове P не менее двух символов, то переставить два первых сим-вола.

Создать машину Тьюринга, которая будет увеличивать на 1 восьмеричное число
Помогите создать машину тьюринга, которая будет увеличивать на 1 число заданое в восьмеричной системе счисления

Построить машину Тьюринга, вычисляющую следующие функции
Помогите, пожалуйста! Требуется построить машину Тьюринга, вычисляющую следующие функции: 1) f(x,y,z,w)=y+z+1 2)f(x,y,z)=2y 3)f(x,y,z)=x+y, если z не равно 0, и y, если z=0

Задача про лифт
Пожалуйста, помогите!!! Завтра необходимо сдать.... Грузовой лифт, обсуживающий трехэтажный магазин, имеет кнопку вызова на каждом этаже и работает по следующим правилам: - если нажата одна...

Алгоритм Маркова: f(x,y)=(x+2)-y
Ребят, выручайте, нужно построить алгоритм Маркова, вычисляющий функцию f(x,y)=(x+2)-y. Протестировать алгоритм Маркова на всевозможных значениях аргументов функции. Саму задачу решил, а...

Машина Тьюринга: получить двоичное число, равное неполному частному от деления числа P на 2
Считая непустое слово P записью числа в двоичной системе, получить двоичное число, равное неполному частному от деления числа P на 2 (например: 1011 -> 101). A={0,1}. Пожалуйста помогите. Не могу...

Реализовать функцию выбор аргумента над числами в унарном коде
Реализовать функцию выбор аргумента над числами в унарном коде. Помогите, пожалуйста. Просто на словах как это можно реализовать.

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

Построить машину Тьюринга
Помогите, пожалуйста, с решением! 1. Построить машину Тьюринга, вычисляющую числовую функцию f(x1, x2,… , xn). 2. Проверить работу построенной машины над некоторыми наборами значений переменных....

Построить машину Тьюринга, вычисляющую функцию f(x)
построить машину тьюринга

Построить машину Тьюринга, которая увеличивает число, записанное в десятичной системе счисления, в 4 раза
Каким способом можно это записать? Помогите плес: Построить машину Тьюринга, которая увеличивает число записано в десятичной системе счисления в 4 раза.

Построение ДКА по НКА
Есть такое регулярное выражение: b {c V a} V {a V c} bc {a V b} По нему автомат получается недетерминированным, т.к. по состоянию 0 по b идем в состояние 1 и через 0 по b идем в 6 одновременно....

Найти метку на машине Поста
Известно, что на ленте машины Поста находится метка. Напишите программу которая находит её. Можно пожалуйста программу

Квадратный корень в Машине Тьюринга
Всем доброго дня! Задача перед мной стоит такая: Построить Машинку Тьюринга для f(x)=корень из x, x - целое число. Пожалуйста прошу помочь с данной проблемой, есть мастаки в этом деле?

Составить таблицу переходов конечного автомата
Здравствуйте. В этой тематике не так уж и хорош, так что нуждаюсь в помощи. И да, текст может быть не полностью точным, ибо я полностью не понял :D В курсовой работе задана такая таблица: x 0 1 ...

Машина Тьюринга: найти сумму чисел в десятичной системе исчисления
Даны два целых положительных числа в различных системах исчисления, одно – в троичной системе, другое – в десятичной. Разработайте машину Тьюринга, которая будет находить сумму этих чисел в...

Нормальный алгоритм Маркова: утроение букв в слове
Составить нормальный алгоритм Маркова по утроению букв в слове. Алфавит {a,b,c,d,a0}

Машина Тьюринга. Переменную ко всем словам х1,х2....хn в алфавите A ={a,b} и переводящую их в слово a
Помогите. Переменную ко всем словам х1,х2....хn в алфавите A ={a,b} и переводящую их в слово a. Записать все команды полученной машины Тьюренса в виде таблицы. Проверить работу МТ над некоромы...

Машина Поста. Выводит метку, если записанное на ленте число – четное
Напишите программу для машины Поста, выводит метку, если записанной на ленте число – четное. Каретка стоит над самой левой меткой. Помогите пожалуйста решить эту задачку

Машина Тьюринга. Вычитание в троичной СС
Здравствуйте. Помогите пожалуйста построить Машину Тьюринга, которая вычисляет разность первого и второго чисел в троичной СС(по условию первое число больше или равно второму). Буду безумно...

Какой язык порождается грамматикой с данными правилами?
Помогите пожалуйста, скоро зачёт!!! Не понимаю как тип языка определить. Вариант №1 1) Какой язык порождается грамматикой с правилами: a) S -> 1B b) S -> A | SA | SB B -> B0 | 1 A -> a...

Построить машину Тьюринга для вычисления функции (x,y,z)=у
Задание: Построить машину Тьюринга для вычисления функции (x,y,z)=у я немного не понимаю: у меня есть пример: Построить машину Тьюринга для вычисления функции (x,y,z)=z такое решение: g0 1 g0...

Нарисовать диаграмму состояний конечного автомата
Добрый день. Помогите нарисовать диаграмму состояний конечного автомата. Входной алфавит А={0,1}; выходной алфавит Z={0,1}; три внутренних состояния S={s1,s2,s3 } Функция переходов задается таблицей

Выяснить, применима ли машина Тьюринга, заданная программой Р к слову S и, если применима, то указать результат
Выяснить, применима ли машина Тьюринга, заданная программой Р к слову S и, если применима, то указать результат применения машины Тьюринга к заданному слову. При решении задачи следует учесть, что в...

Машина Поста: Сжать массив так, чтобы все N меток занимали N расположенных подряд секций
мне дали две задачи,на машину поста,помогите решить!!!! 2)На ленте машины Поста расположен массив из N меток (метки расположены через пробел). Нужно сжать массив так, чтобы все N меток занимали N...

Схема преобразователя из 8421 в 5421
Доброе время суток. Надо схема на логических элементах преобразования двоично-десятичного кода 8421 в двоично-десятичного кода 5421. Если есть у кого поделитесь пожалуйста, или посоветуйте...

Построить машину Тьюринга, дублирующую двоичный код
Всем привет. Какой принцип у алгоритма, дублирующий исходное число через символ "*"?. Например - Дано: 10111. Необходимо получить: 10111*10111. Помогите, нет идей(

Составить регулярное выражение
Необходимо составить регулярное выражения для языка, любое слово которого не содержит подслова bc A={a,b,c} Подойдет ли (a(a+b+c))* или (a(a+b+c)*)*?

Машина Тьюринга: вычислить x - 3
Реализовать на машине тьюринга функцию х-3

Алгоритм Маркова и машина Тьюринга!
A={a,b}. Пусть длина слова P кратна 3. Удалить правую треть этого слова. A={a,b}. Если слово P содержит одновременно символы a и b, то заменить P на пустое слово. Кто поможет!?

Машина Поста: перевод машинной записи числа n в машинную запись числа n+1
Постройте программу машины Поста, реализующей алгоритм перевода машинной записи числа n в машинную запись числа n+1, при этом каретка расположена слева от массива на произвольное количество пустых...

Построить ориентированный граф для автомата Мура
построить ориентированный граф для автомата мура по размену наличных денег.автомат может разменять одну купюру 10 рублей двумя монетами по 5 рублей или одну купюру 50 рублей пятью купюрами по 10...

Алгоритм Маркова. В слове P требуется удалить все вхождения символа b, а затем заменить все символы a на b
A={a,b,c}. В слове P требуется удалить все вхождения символа b, а затем заменить все символы a на b.

Построить контекстно-свободную грамматику, порождающую заданный язык
Здравствуйте, мог бы кто-нибудь помочь? Построить контекстно-свободную грамматику, порождающую заданный язык: L = \{0^i 1^j 2^k |\: i>= 2j\: or\: j>= 2k\}

Нарисовать помеченный ор. граф, который представляет язык, заданный регулярным выражением
Задание: нарисовать помеченный ор. граф который представляет язык заданный регулярным выражением: (abc+(cba)(a+(bc+cb)a)*) Подскажите пожалуйста, правильно ли я сделал или есть ошибки?Просто я...

Построить Машину Тьюринга
Построить МТ, удваивающую число на ленте (п-р 01110 --> 01111110) ответ должен быть в таком виде (примерно) q10-> q20R q20 -> q21R q20 -> q30L q30 -> q41L q40 -> q01L Заранее спасибо

Машина Маркова. Удалить из слова P первые 3 символа a и первые 2 символа b
A = {a,b,c}. Удалить из слова P первые 3 символа a и первые 2 символа b. Помогите решить задание как бы не пытался ничего не получается.

Машина Тьюринга, сдвинуть ответ на одну клетку вправо
Заранее спасибо за идеи. Буду рада. Не получилось у самой. Есть прога, нужно, чтобы в конце весь ответ сдвигался на одну "кдетку" вправо. как на скрине: // Прибавление единицы // к двоичному...

Нормальный алгоритм Маркова: вычисление функции f(x)=2x+2,(3)
Составьте нормальный алгоритм Маркова, вычисляющий функцию (в скобках указана система счисления): f(x)=2x+2, (3); f(x)=2x+2, (3);

Кодирование по Хэммингу
Имеется задача: "Построить матрицу Хэмминга, уравнения кодирования и декодирования для заданного количества информационных разрядов: n=14 ". первый вопрос, который возникает и не очень внятно...

Тьюрмиты
Как запрограммировать поведение тьюрмита ?

Составить грамматику, порождающую формальный язык. Определить тип формальной грамматики и языка по классификации
Помогите, пожалуйста с данным заданием: 1. Составить грамматику, порождающую формальный язык; 2. Определить тип формальной грамматики и языка по классификации Хомского; 3. Разработать программное...

Построить алгоритм Маркова. Вместо символа, который находится на четном месте вставить символ *, остальные буквы
Добрый день, уже второй день не могу разобраться как реализовать алгоритм Маркова. Задание такое: A = {a,b,c} Вместо символа который находится на парном месте - вставить символ *, остальные буквы не...

Машина Тьюринга: перенос первого символа слова в конец
Переноса первого символа слова в конец, если алфавит состоит из {a,b,c} и каретка находится на первом символе правого края слова

Увеличить строку B в 2 раза. Машина Тьюринга
Здравствуйте! Помогите с задачей. Нужно разработать машину Тьюринга, которая переместит все буквы A в левую, а буквы B в правую часть строки, далее удвоить количество В. Не понимаю как делать

Машина Тьюринга: вычисление функции f(x)=x-26
Необходимо построить машину Тьюринга для функции f(x) = x-26: Подскажите, что писать в состояния q2, q3 и хватит ли 3х? И правильно ли записано состояние q1?

Машина Тьюринга. Развернуть бинарное слово задом наперед, используя дополнительные построения на ленте при решении
Машина Тьюринга. Развернуть бинарное слово задом наперед, используя дополнительные построения на ленте при решении.

Составить грамматику, порождающую формальный язык
1. Составить грамматику, порождающую формальный язык: L(G)={a1a2...ana1a2...an | ai Є {c, d}};

Машина Тьюринга. Перевод в восьмеричную сиситему счислении.
На ленте машины Тьюринга записан набор палочек. Постройте функциональную схему машины, которая выразит данное количество палочек числом в восьмеричной системе счисления. Каретка машины находится под...

Построить автомат, распознающий язык, заданный регулярным выражением
(a^2+(a^2(a^2)^2)* как правильно раскрыть и построить такой сложный автомат? попытался что то сделать получилось вот такое

Нормальный Алгоритм Маркова: выдать запись разности данных чисел в троичной системе
Пусть P имеет вид Q-R, где Q и R - непустые слова из символов 0,1,2. Трактуя Q и R как записи чисел в троичной системе счисления (возможно, с незначащими нулями) и считая, что Q >= R, выдать в...

НАМ: если в непустом слове P совпадают первый и последний символы, то удалить оба этих символа
A={a,b}. Если в непустом слове P совпадают первый и последний символы, то удалить оба этих символа, а иначе слово не менять.

Как построить граф автомата Мили по уже построенному графу автомата Мура
Подскажите как построить граф автомата Мили по уже построенному графу автомата Мура А0 А1 А2 А3 А4 А5 А6 А7 А8 А9 А10 А11 C W0 W0 W0 W0 W1 W1 W0 W1 W1 W1 W0...

Построить ДКА
Построить ДКА, допустимым для которого является язык над алфавитом {0,1}, состоящий из множества слов, в которых число нулей делится на четыре, а число единиц нечетно.

Существует ли примитивно-рекурсивная функция для решения следующей задачи?
Здравствуйте, нужна помощь по теории алгоритмов. Существует ли примитивно-рекурсивная функция для решения следующей задачи? Если да, то привести алгоритм, если нет, то обосновать. Задание: ...

Частное от деления на машине Поста
Дорогие друзья. Душевно молю вас о помощи в написании данной мозговышибательной программы на машине Поста. Задание: На ленте даны два числа, разделенные одним пробелом, справа через один пробел...

Машина Тьюринга. Вычитание двух чисел
Написать МТ которая отнимает от одного числа унарно представленного, другое унарно представленное число(***-**=*).

Опишите ДКА, которые допускает следующие языки над алфавитом {0,1}
Опишите ДКА, которые допускает следующие языки над алфавитом {0,1}: множество всех цепочек, начинающихся с 1, и если рассматривать их как двоичное представление целого числа, то это число кратно...

Машина Тьюринга. Построить
0|a|b|c|a|b|c|a|a|a|0 '''''''''''''''''''''''''''^ '''''''''''''''''''''''''''| Для указанной ленты конфигурация K1=0^(2)q1^(3)0 Построить в алфавите {0, 1} машину Тьюринга, переводящую...

Алгоритмы Маркова
A={a,b}. Пусть слово P имеет нечётную длину. Удалить из него средний символ. Помогите кому не сложно пожалуйста.

Машина Поста: разделить серию на две пробелом по k меток в каждой
Здравствуйте, надо написать "словесный" и программу для Машины Поста к задачи На ленте машины Поста расположена серия из 2k меток. Разделить эту серию на две пробелом по k меток в каждой ...

Определить тип по Хомскому
S\rightarrow aQb | \varepsilon Q\rightarrow cSc Определить тип по Хомскому и указать максимально возможный номер типа грамматики и языка. Если можно то и объяснить как вы делаете это, я прочитал...

Построить машину Тьюринга, вычисляющую числовую функцию
Построить машину Тьюринга, вычисляющую числовую функцию f. f(x,y) = \begin{cases} & \text{ 0, x\geq y}\\ & \text{ 1, x\prec y }\end{cases} Алфавит не ограничен.

Машина Тьюринга: Отсортировать алфавит {1,2,3} по возрастанию
Отсортировать алфавит {1,2,3} за по возроастаниемю. Например 11321332311→ 11111223333.

Машина Тьюринга: умножение числа на три
Составить программу для машины Тьюринга умножающую число на три.

Машина Тьюринга, найти сумму чисел и ответ записать в десятичной системе счисления
Дано число в десятичной системе счисления и число в троичной системе счисления. Найти их сумму и ответ записать в десятичной системе счисления (например, 576+100). Каретка располагается над крайней...

Гомоморфизм и изоморфизм
Можете простыми словами обьяснить ,что такое в теории автоматов Гомоморфизм и Изоморфизм и чем они отличаются?

Машина Тьюринга для нахождения модуля разности чисел в унарном коде
Помогите пожалуйста с алгоритмом для функции |x-y| в унарном коде. На данный момент я сделал что-то приблизительное для обычной разности чисел x-y, а как для модуля как-то совсем не пойму. * это...

Какому классу по Хомскому принадлежит грамматика?
Люди помогите Какому классу по Хомскому принадлежит грамматика из правилами S → AS|ε; A → a|b?

Тест по дискретной математике
Отметьте правильные утверждения о двоичных функциях. Выберите один или несколько ответов: a. Эквивалентные формулы всегда можно преобразовать друг в друга посредством элементарных...

Определить степень равносильности формул.
Определить степень равносильности формул.A ~ и B~ при условии, что X~ и Y~ принимают значения степеней истинности из множеств {α; β} и (γ, θ) .

Составить грамматику, порождающую формальный язык
составить грамматику, порождающую формальный язык, заданный в соответствии с заданием; L(G)={(ab)^n (cb)^m | n, m≥0}

Прямое произведение конечных автоматов
Не могу найти пример прямого произведения конечных автоматов. Повсюду голая теория. Где всё-таки можно найти пример?

Составить программу, по которой машина Поста раздвинет на расстояние в одну ячейку две половины данного массива
На ленте машины Поста расположен массив из 2n ячеек. Составить программу, по которой машина Поста раздвинет на расстояние в одну ячейку две половины данного массива. Помогите, пожалуйста, составить...

Нормальный алгоритм Маркова. Получить в этой же системе число n
A={ | }. Пусть слово P является записью числа 2n (n=0, 1, 2, …) в единичной системе. Получить в этой же системе число n. Вообще не понимаю как это решить

Составить Программы для машины Поста и Тьюринга
Составить программу для Машины Тьюринга: 1) A={a,b,c}. Удвоить каждый символ в слове P (например: bacb → bbaaccbb). Каретка расположена над самой левой меткой. 2) Машина выдаёт результат 1, если...

Как нарисовать конечный автомат
Допустим я перешел к своему базису ИЛИ-НЕ, и получилась функция u1=\bar{x1\bar{x2}x3x4}\vee\bar{x1x2\bar{x3}x4} Как мне ее изобразить?

Преобразовать НКС-грамматику в эквивалентную КС-грамматику, не содержащую цепных правил.
Преобразуйте НКС-грамматику G=(N,\Sigma ,P,S) в эквивалентную КС-грамматику, не содержащую цепных правил. 1. S\rightarrow LA, S\rightarrow LB, L\rightarrow P:=, L\rightarrow Q:=, P\rightarrow i,...

Нормальный алгоритм Маркова(НАМ) - переместить точку из конца слова в середину
Нормальный алгоритм Маркова(НАМ) переместить точку из конца слова в середину. В слове четное количество букв. Алфавит {0,1}. Пример 1001. станет 10.01

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

Нормальный алгоритм Маркова: частное и остаток от деления на 7 в унарной системе счисления
Составить нормальный алгоритм, который вычисляет частное и остаток от деления на 7 в унарной системе счисления.

Постройте машину Тьюринга, которая удаляла бы пары взаимных скобок
Доброго времени суток! Помогите решить задание по машине Тьюринга. Вернулся после академического отпуска, много чего закрыть нужно_) Буду безмерно благодарен. Дан массив из открывающихся и...

Метод Тьюринга. Удалить из слова его второй символ
a={0,1,∧} удалить из слова его второй символ

Машина Тьюринга. Поразрядно логическая сумма двух двоичных чисел
Помогите написать программу для алгоритмического эмулятора "Машина Тьюринга". Вычислить поразрядно логическое произведение двух двоичных чисел, разделенных знаками / \.

Построить граф автомата и найти язык L
Всем привет Может кто-нибудь помочь с задачей. Построить граф автомата и найти язык L, допускаемый автоматом Дано: Вход Qs = {4}, выход Qf = {1, 3}, Дуги: (1, 5, a), (1, 4, b), (2, 1, a), (3,...

Построить НАМ, который из всех слов в алфавите применим только к двум словам: пустому слову и ccabba
1. Задан алфавит A={a,b,c}.Построить НАМ, который из всех слов в алфавите применим только к двум словам: пустому слову и ccabba Первое совсем не представляю как делать. Даже и идей нет.

Составить программу для машины Поста которая удалит каждую вторую метку
1) на информационной ленте установили массив из N меток . Каретка автомата находится под крайней левой меткой. Составить программу для машины Поста которая удалит каждуй вторую метку....

Автомат Мили: автоматический перевод двухразрядного шестнадцатиричного числа в двоичный код.
прошу помочь составить автомат Мили для Автоматического перевода двухразрядного шестнадцатиричного числа в двоичный код....

Как сделать цикл для машины Поста?
Число k представляется на ленте машины Поста k+1 идущими подряд метками. Одна метка соответствует нулю. Составьте программу прибавления 1 к произвольному числу k. Каретка расположена над одной из...

Машина Тьюринга. На ленте даны два числа, разделенные одним пробелом, справа через один пробел напечатать сумму чисел
На ленте даны два числа, разделенные одним пробелом, справа через один пробел напечатать сумму этих чисел

Как строить Граф состояний системы
Дана резервированная система с постоянно включенным резервом кратности k=5. Интенсивности отказов и восстановлений являются постоянными число обслуживающих бригад r=1,2,3,4,5,6. 1. Постройте граф...

Построение модели конечного автомата
Монета многократно подбрасывается и делается отметка при четных выпадениях цифры в последовательности цифр и при каждом втором (не обязательно подряд) выпадении герба (х — сторона монеты, у — отметка...

Составьте программу сложения произвольного количества целых неотрицательных чисел
Доброго времени суток! Алгоритм сложения двух чисел написать мне было не трудно, а вот с этим что-то не получается Составьте программу сложения произвольного количества целых неотрицательных...

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

Машина Тьюринга: вычисление функции f(x) = [x/2]
Построить программу машины Тьюринга, вычисляющую следующую функцию: f(x) = , где - целая часть числа n ,т.е. наибольшее целое не превосходящее n.

Построить конечный автомат, распознающий цепочки в алфавите
Понятия не имею, как решать, нужно как можно скорее Построить конечный автомат, распознающий цепочки в алфавите {a, b}, в которых символ a не встречается два раза подряд.

Удаление из слова третьего вхождения буквы (нормальный алгоритм Маркова)
Дан алфавит A = {a, b, c}. Удалить из слова P третье вхождения символа a, если таковое имеется. Задача была решена. Вот сам алгоритм: ***a=>. **a=>a*** *a=>a** ***b=>b*** ***c=>c*** **b=>b**...

Эмулятор машины Тьюринга
Здраствуйте, дорогие форумчане! Помогите решить задачу через эмулятор машины Тьюринга. 1) A={a,b,c}. символдарды bc(P→ Pbc) P 2) A={a,b,c}. Приписать справа к слову P символы bc (P →...

Детерминизация конечного автомата
здравствуйте, надеюсь, пишу в тот раздел. более подходящего не нашел. перехожу от НКА к ДКА по данному алгоритму. но не понимаю, каким будет множество заключительных состояний после детерминизации?

Перевод в ПНФ И СНФ
Пока до ПНФ. Проверьте плз.

Составить программы машины Тьюринга для вычисления заданных одноместных функций
Составить программы машины Тьюринга для вычисления заданных одно-местных функций. В начале работы исполнитель располагается над самой крайней слева непустой ячейкой. С левой стороны чисел Задание...

Определить, является ли однозначной грамматика
Определить является ли однозначной данная грамматика: G1 ({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, – , “.”}, {<число>, <цел>, <дроб>, <цифра>, <осн>, <знак>}, P1, <число>) P1: <число> → <знак> <осн>...

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

Машина Тьюринга. На ленте через пустой символ записаны два бинарных слова, совпадают ли они?
Машина Тьюринга. На ленте через пустой символ записаны два бинарных слова. Совпадают ли они? Ответ: 0 или 1. Если можно, напишите пример.

Выполнить редукцию выражения лямбда-исчисление
Выплнить редукцию в аппликативном порядке. До форм NF и WHNF. Верно ли ход ? step_0\ \ \ \big( \lambda h.( \lambda x.h (x x)) (\lambda x.h (x x)) \big) \big((\lambda y.y) (+ 1\ \ 5)\big) ...

Построить язык, порожденный такой грамматикой. Определить тип грамматики
Дано грамматику G = (V, T, S, P), где , V={0, 1, S, A, B}, T={0,1}, P = {{S\rightarrow 0S, A\rightarrow A1, S\rightarrow A, A\rightarrow \Lambda }}, s - начальный символ. Построить язык, порожденный...

Для автомата, заданного таблицей, постройте диаграмму Мура. Задайте этот автомат системой булевых функций
Для автомата, заданного таблицей, постройте диаграмму Мура. Задайте этот автомат системой булевых функций

Заменить 2 символа на один "Машина Тьюринга"
В тексте возведение в степень обозначалось двумя звездочками: **. Необходимо заменить это обозначение знаком ‘^’. Как будет выглядить табличка состояний и сколько их подсказали что будет сдвиг и...

Применима ли машина Тьюринга?
Выяснить, применима ли машина Тьюринга, заданная программой P к слову S, и если применима, то указать результат применения машины Тьюринга к данному слову. 6 \ = \ \left\{\begin{matrix} \ {\ \...

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

Выяснить, применима ли машина Тьюринга T к слову P?
Почему мой ответ неверен? Выяснить, применима ли машина Тьюринга T к слову P. Если применима, то выписать результат T(P) применения машины Тьюринга T к слову P. q1 1 q1 0 E q1 0 q2 0 L q2 0 q3...

Построить диаграмму переходов конечного автомата
Задание:По регулярному выражению построить диаграмму переходов конечного автомата и проверить является ли он недетерминированным {(d+a)}^{2}{(ab)}^{*}c в алфавите {a,b,c,d} Есть, предположение, но...

Нормальный алгоритм Маркова: удалить правую половину данного слова четной длины
Помогите пожалуйста! Очень срочно нужно решить задачу. Нужно построить нормальный алгоритм Маркова: A={a,b}. Пусть слово P имеет чётную длину (0, 2, 4, …). Удалить правую половину этого слова.

Нужна реализация любого конечного автомата.
Народ, подкиньте реализацию любого конечного автомата, или подскажите, где взять. Заранее спасибо.

Устраните лишние символы из грамматики (Контекстно-свободные грамматики)
Помогите пожалуйста.

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

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

Сконструируйте машину Тьюринга, которая выступит в качестве двоично- восьмеричного дешифратора
Сконструируйте машину Тьюринга, которая выступит в качестве двоично- восьмеричного дешифратора

Алгоритм Маркова: вычисление функции f(x)=x-5
Написать алгорифм Маркова для вычисления функции f(x)=x-5, где х задано в десятичной сс и может иметь незначащие нули. ведущие нули нужно удалить.... Помогите, пожалуйста. Не знаю, как удалить...

Машина Поста: найти модуль разности длин массивов
На ленте заданы 2 массива. Найти модушль разности длин массивов. Каретка над первой ячейкой левого массива. Добавлено через 5 часов 53 минуты Решение. 1. –> 2 2. ? 3; 1 (идем до конца...

Машина Поста, раздвинуть на расстояние в одну ячейку две половины данного массива
Здравствуйте,помогите реализовать программу на машине Поста. На ленте машины Поста расположен массив из 2n ячеек. Составить программу, по которой машина Поста раздвинет на расстояние в одну ячейку...

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

Которые из языков программирования являются полными по Тьюрингу?
Которые из языков программирования являются полными по Тьюрингу ?(то есть на которых можно сделать все что захочешь)

Машина Поста. На ленте дано число. Справа через два пробела напечатать это число
На ленте дано число. Справа через два пробела напечатать это число Правила форума, пункт 4.3. Создавайте темы с осмысленными и понятными названиями - это серьезно повышает шансы, что на ваш вопрос...

Алгоритм Маркова вычитание 1
Построить алгоритм Маркова в алфавите B=A U {a,b}, где A={0,1,2,3,4,5,6,7,8,9} для вычисления функции f(x)=x-1 Помогите пожалуйста..

Построить контекстно-свободную грамматику
Необходимо с использованием системы JFLAP, построить контекстно-свободную грамматику, описывающую заданный язык, который может быть распознан алгоритмом перебора или управляемым пользователем, или...

Составить грамматику, порождающую формальный язык
Помогите идеями, может у кого есть уже решенное: 1) составить грамматику, порождающую формальный язык, заданный в соответствии с вариантом;

Построить регулярное выражение по регулярной грамматике
Здравствуйте. Необходимо построить по регулярной грамматике регулярное выражение. Сама грамматика: Получаем систему: До чего дошел я: В конце концов нужно прийти к . Ума не приложу, что делать...

Машину Тьюринга: вычисление заданной функции f(x)
построить машину Тьюринга для вычисления функции f(x) \begin{cases}0 & \text{ if } x=0 \\ 1 & \text{ if } x\ne 0 \end{cases}

Зачем нужна теория автоматов
Подскажите а зачем нужна теория автоматов ? Где ее в жизни можно применить ?

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

Диаграмма Мура для автомата, заданного таблицей
Пожалуйста помогите решить задачи. Для автомата заданного таблицей постройте диаграмму Мура. Задайте этот автомат системой булевых функций. ( можно даже написать или скинуть ссылку на понятный...

Машина Тьюринга: вычисление функции f=x-y
Здравствуйте. Нужная машина Тьюринга для вычисления функции F=x-y, если x>=y. Входное слово например такое - 01110110. Помогите, пожалуйста

Преобразование автомата Мили в автомат Мура
Имеется таблица переходов и выходов автомата Мили. Что нужно сделать с этой таблицей, чтобы преобразовать её в таблицу автомата Мура? В таблице автомата Мили иногда встречаются пропуски (-)

Устранить бесполезные и недостижимые символы из данной грамматики.
Здравствуйте. Помогите кто-нибуть выполнить задание на экзамен. Заранее благодарен за помощь. Устранить бесполезные и недостижимые символы из грамматики G=<N,T,P,S>, где N={A, B, C, D, E}, T={a,...

Машина Тьюринга: определить, является ли число в четверичной системе четным
Считая непустое слово P записью числа в четверичной системе счисления,определить,является оно четным числом или нет.Ответ :1(да) или 0.

Машина Тьюринга: Сумма двух чисел, представленных в унарной системе счисления
Машина Тьюринга. Даны два натуральных числа m и n, представленных в унарной системе счисления. Соответствующие наборы символов « | » разделены « – », вслед за последним символом набора n стоит...

Вычислить остаток от деления числа на 3
Всем здравствуйте! Очень сильно нуждаюсь в помощи по машине Тьюринга, вот задание: Дано число в десятичной системе счисления. Вычислить остаток от деления этого числа на 3. Я тот ещё чайник в...

Машина Тьюринга. Даны два натуральных числа m и n, представленных в унарной системе счисления
Машина Тьюринга. Даны два натуральных числа m и n, представленных в унарной системе счисления. Соответствующие наборы символов « | » разделены « – », вслед за последним символом набора n стоит знак...

Машина Поста. Нахождение меньшего массива среди двух
Здравствуйте, не могу понять логику данного задания.Если не трудно, то решите пожалуйста, а если трудно, то можете хотя бы объяснить, как оно должно работать? На ленте записано два массива меток....

Машина Тьюринга: перевод конфигурации К1 в конфигурацию К0
0|a|b|c|a|b|c|a|a|a|0 '''''''''''''''''''''''''''^ '''''''''''''''''''''''''''| Для указанной ленты конфигурация K1=0^(2)q1^(3)0 Построить в алфавите {0, 1} машину Тьюринга, переводящую...

Минимизация ДКА
Привет всем. Впервые минимизирую ДКА и прошу меня проверить, верно ли я все сделал. Дан следующий ДКА: A=(Q={1,2,3,4,5}, \sum={a,b}, f, q_0=1, F={4,5}). Функции переходов: f(1,a)={2}...

Построить КДА, который по двоичному разложению числа a строит двоичное разложение числа 3а
Построить кда который по двоичному разложению числа "a" строить двоичное разложение числа "3а" Можете пожалуйста обьяснить что вообще это за автомат такой? на вход подаётся только буква "a"? или...

Построить машину Тьюринга, умножающую число на 3
На ленте машины Тьюринга записано целое положительное число в двоичной системе счеления. Построить машину Тьюринга, умножающую это число на 3. Начальное положение-стандартное. Помогите пожалуйста,...

Построение ДМП-распознавателя на основе нисходящего разбора с возвратом
Суть такова: надо написать программу, которая могла бы по заданной КС-грамматике и цепочке строить детерминированный распознаватель со стековой(магазинной) памятью, используя алгоритм нисходящего...

Нормальные алгоритмы Маркова, сложение и умножние
Как можно реализовать умножние в нормальных алгоритмах Маркова? Умножение в единичной системе счисления, т.е. 1111*111=111111111111. Сложение реализовал просто убрав +, т.е. 1111+111=1111111. А...

Спроектировать автомат с 2х разрядным входом и одноразрядным выходом
Здравствуйте. Знаю что Теория автоматов раздел мат логики, но не где подходящий раздел под именно эту дисциплину не нашел. Так что рискнул выложить здесь. Спроектировать автомат с 2х разрядным...

Машина Тьюринга, распознающая четность натурального числа
Уважаемые участники форума,напишите пожалуйста решение следующей задачи: Построить машину Тьюринга, распознающую четность натурального числа. Задача требует срочного решения,поскольку срок её сдачи...

Нормальные алгоритмы Маркова. Перевести число с двоичной в унарную систему счисления
A = {0, 1}. Перевести число с двоичной в унарную систему счисления.

Выяснить, применима ли машина Тьюринга к слову
P = {1: q10 → 0Rq1; 2: q11 → 1Rq2; 3: q20 → 0Lq3; 4: q21 → 1Rq1; 5: q30 →0Rq0; 6: q31 → 1Rq2}; S = 111101. Помогите пожалуйста

Автомат Мура на RS-триггерах
В общем проблема следующая. Нужно построит автомат. Все как рассчитывается я понаходил. Но при включении(работаю в схематике) элементы памяти, эти тригеры самые, в запрещенном состоянии и все...

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

Нормальный алгоритм Маркова: записать число в десятичной системе счисления
Дано число в унарной системе, записанное с помощью символов «|». Построить НАМ, записывающий это число в десятичной системе счисления. Например, из ||||| должно получиться 5.

Как написать мнр для х/у
х/у

Описать язык, порождаемый грамматикой
Описать язык, порождаемый грамматикой с правилами S → 10S0 | e Просто хочу убедиться в правильности, у меня получилось так. {(1 0)^n 0|n>=0}

Машина Тьюринга: вычисление поразрядной дизъюнкции двух целых неотрицательных двоичных чисел
Помогите понять условие задачи. Не понимаю что нужно делать. Задание: Вычисление поразрядной дизъюнкции двух целых неотрицательных двоичных чисел Простым языком, если можно :)

Построить в алфавите {a,b} машину Тьюринга
Построить в алфавите {a,b} машину Тьюринга такую, что для любого слова U в исходном алфавите T(U) = { 1, если cодержит подслово baa 0, в обратном случае } Добавлено через 21 час 15...

Тип грамматики по Хомскому
Определите тип грамматики по Хомскому, правила которой имеют вид М -> аМа | аВ В -> ккВ | кс и объясните, почему вы пришли к такому выводу. Я считаю, что эту грамматику можно...

Машина Тьюринга: перевод из 2-ной и 16-тиричную систему счисления
Столкнулся с проблемой полного незнания Тьюринга и его машины , а надо ... Дано двоичное число .Построить машину Тьюринга ,преобразующее его в 16-ричное. Буду благодарен)

Доказать примитивную рекурсивность f(x) - количество цифр в числе x
Подскажите, пожалуйста, правильно ли я доказал данную функцию. f(0) = 1 f(x+1) = f(x) + \bar{sg}(rm(N(x),10)*sg(N(N(x)))-{10}^{f(x)}) rm(x, y) = остаток при делении x на y.

Алгоритм Маркова: если в слово P не входит символ a, то заменить в P все символы b на с
A={a,b,c}. Если в слово P не входит символ a, то заменить в P все символы b на с, иначе в качестве ответа выдать слово из одного символа a.

Составить НА, который в левом наборе оставлял бы столько единиц, на сколько единиц в левом наборе больше, чем в правом
Нужна помощь по заданию. собственно вот оно : На ленту подряд вписаны два конечных набора из m и n единиц, разделенные звездочкой. Причем в левом наборе единиц не меньше, чем в правом (m > n)....

Машина Тьюринга, определить, является ли P словом ab
Привет, помогите решить- A={a,b,c}. Определить, является ли P словом ab. Ответ (выходное слово): слово ab, если является, или пустое слово иначе. в машине тьюринга, я не понимаю задание объясните...

Нерегулярность языка палиндромов
Как доказать нерегулярность языка палиндромов?

Построить автомат с магазинной памятью
Помогите с заданием, пожалуйста Построить автомат с магазинной памятью (детерминированного типа), позволяющий идентифицировать цепочки над алфавитом {0,1} следующих языков: L= (01n010n|n>0) ...

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

Определите контекстно-свободную грамматику, которая порождала бы язык
Подскажите, как решать, пожалуйста. Определите контекстно свободную грамматику, которая порождала бы язык всех строк алфавита {0, 1}, где в каждой из них непосредственно справа от каждого символа...

Машина Тьюринга: нахождение наибольшего общего делителя для двух чисел в унарной системе счисления
Требуется написать машину Тьюринга для нахождения наибольшего общего делителя для 2 х чисел в унарной системе счисления. разделенных символом "!".Каретка обозревает крайний левый символ. третий день...

По заданной машине Тьюринга T и начальной конфигурации K1 найти заключительную конфигурацию
По заданной машине Тьюринга T и начальной конфигурации K1 найти заключительную конфигурацию (записать протокол обработки) .

Построить автомат, распознающий регулярный язык
Здравствуйте! Прошу помощи с выполнением следующего задания: Нужно построить автомат, распознающий регулярный язык: (ab)*\bigcup (ba)*

Автоматы Мили и Мура
Всем привет! Друзья помогите решить следующие задачи кто понимает как делать, задачи представлены на картинке.

Построить машину Тьюринга, которая каждое слово x1x2...x(n-1) в алфавите {a,b} преобразовывает в слово xnx(n-1)...x2x1
Помогите, пожалуйста, построить машину Тьюринга, которая каждое слово x1x2...x(n-1) в алфавите {a,b} преобразовывает в слово xnx(n-1)...x2x1

Разработать программное средство, распознающее тип введенной пользователем грамматики по классификации Хомского
3) разработать программное средство, распознающее тип введенной пользователем грамматики по классификации Хомского. L(G)={c^2n*d^n | n>0}

Машина Тьюринга: найти разность двух двоичных чисел
Найти разность двух двочных чисел, первое чило больше другого.

Машина Тьюринга, вычисляющая значение f(x)=x-y, при x>y
Вычисление функции f(x,y)=x-y в двоичной системе счисления при x>y Алфавит: 1,0, - Входное

Машина Тьюринга. Нужно правильно вычислить функцию f(x;y)=x+2y
В машине тьюринга вычислить функцию. Алгоритм выполнения есть, необходимо скинуть файл с ее выполнением. Вот алгоритм: МТ, которая вычисляет функцию f(x, y)=x+2y: q0|→ q0|R q0#→...

Машина Тьюринга. Перемещение 2 и последнего символа в слове местами
На ленте записано слово более чем из 3х букв. Надо переместить 2 и последнюю букву местами. :wall::help::help:

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

Выяснить, применима ли машина Тьюринга T к слову P
Добрый день. Прошу помочь в решение задачи и расписать по возможности подробно. Выяснить, применима ли машина Тьюринга T к слову P. Если применима, то выписать результат T(P) применения машины...

Нормальный алгоритм Маркова: замена в слове L каждого символа "a" на символ "c"
Задание в нормальных алгоритмах Маркова: Реализовать алгоритм, выполняющий замену в слове L в алфавите A={a,d,c} каждого символа a на символ c . Я не очень понимаю,как это сделать,но...

Машина Поста: справа через один пробел напечатать данные числа в порядке возрастания
Делаю контрольную по программированию. Нужно было решить 4-ре задачи на выч.машины (нейман, марков и т.д.). Из всех задач мне не дается только машина поста. общий принцип вроде бы понимаю, но начинаю...

МНР
целая часть корня из (x-y)/(3-z), z = 0,1,2,3,4,5,6. Добавлено через 58 минут 1)J(2,5,15) 2)S(5) 3)J(2,5,16) 4)S(5) 5)J(2,5,17) 6)S(5) 7)J(2,5,7)

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

Составить программу машины Поста, находящую остаток от деления числа n на 3
На ленте машины Поста расположен массив из n меток. Составьте программу машины Поста, находящую остаток от деления числа n на 3, при этом каретка расположена напротив произвольной секции записи или...

Написать программу для Машины Тьюринга с пяти-символьными командами.
Помогите разобраться с задачей плиз. "Написать программу для Машины Тьюринга с пяти-символьными командами Что значит 1 в степени y? и q в степени звездочка? Очень прошу.

Спроектировать цифровой автомат
Спроектировать цифровой автомат Мура операция деление на T триггерах - разработать алгоритм - разработать структурную схему операционного автомата Подскажите как сделать или где можно...

Машина Тьюринга (дробная часть от деления)
Подскажите пожалуйста, как можно решить задачу на машине Тьюринга. (в прикрепленном фаиле) Необходимо найти дробную часть от деления числа n на 3. Буду очень признателен и безмерно благодарен...

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

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

Машина Тьюринга. Удвоение
Докажите, что заданная функция вычисляется по Тьюрингу, для чего постройте машину Тьюринга которая ее вычисляет: f(x)=2x+1.

Построить по заданной регулярной грамматике конечный автомат. Преобразовать недетерминированный конечный автомат в ДКА
Помогите, пожалуйста, с заданием: 1. Построить по заданной грамматике конечный автомат. 2. Преобразовать недетерминированный конечный автомат(НКА) в детерминированный конечный автомат(ДКА).

Составить нормальный алгоритм Маркова
Написать алгорифм Маркова, который в алфавите {a,b,c} удваивает предпоследнюю букву "а" если в слове есть буква "с". Например ааbabbc = aabaabbc , abbabba = abbabba Добавлено через 6 часов 56...

Построить грамматику
Добрый вечер! Есть задание данное преподавателем. Читал литературу - мало что понятно. L = { alfaalfa | alfa ∈ {a,b}+} Кто может что подсказать? Добавлено через 2 часа 30 минут S->AA A->a|b...

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

Машина Тьюринга: f(x)=3x+1
Построить машины Тьюринга для правильного вычисления функций (в скобках указана система счисления): f(x)=3x+1, (5)

Машина Тьюринга Алго2000
Необходимо построить машина Тьюринга в программе Алго2000, описав функцию y = 4-2+16.

Машина Тьюринга. В бинарном слове все подпоследовательности из единиц, длина которых кратна трем, занулить
В бинарном слове все подпоследовательности из единиц, длина которых кратна трем, занулять.

Синтез полного одноразрядного двоичного сумматора
Помогите пожалуйста выполнить задания по Синтезу полного одноразрядного двоичного сумматора: 1.Используя таблицу истинности, записать систему уравнений для полного одноразрядного двоичного...

Нормальный алгоритм Маркова: вычисление функции f(x) - индикатора нечетности аргумента x
Здравствуйте, помогите , пожалуйста составить нормальный алгоритм маркова вычисляющий функцию f(x) - индикатор нечетности аргумента x (в десятичной системе счисления)

Построить в алфавите {1,0} машину Тьюринга, переводящую конфигурацию К1 в конфигурацию К0
Есть само уравнение Есть код,, но его надо отредактировать, но я не понимаю в чем ошибки, если не сложно, помогите)

На ленте машины Поста расположен массив в N отмеченных секциях
На ленте машины Поста расположен массив в N отмеченных секциях. Необходимо справа от данного массива через одну пустую секцию разместить массив вдвое больший (он должен состоять из 2N меток). При...

Машина Тьюринга - предикат для сравнения двух чисел
Закодировать предикат для сравнения двух чисел для Машины Тьюринга

Преобразовать формы к виду расширенных форм Бэкуса-Наура.
Формы Бэкуса-Наура (БНФ) Метаязык, предложенный Бэкусом и Науром, использует следующие обозначения: - символ «::=» отделяет левую часть правила от правой (читается: «определяется как»); ...

Доказать, что любой граф на n вершинах с n ребрами содержит простой цикл
Помогите, пожалуйста, решить задачу по теории графов. Нужно доказать, что любой граф на n вершинах с n ребрами содержит простой цикл.

Тест (Мат Логика)
1Что не нужно задавать при введении исчисления высказываний (Мат Логика) 1)алфавит 2)правила образования формул 3)аксиомы 4)правила действия с кванторами 5)правила доказательств 2Для машины...

Машина Тьюринга. Модуль разности двух унарных чисел
Доброго времени суток! Задание: необходимо найти разность двух унарных чисел по модулю. Сделал вот такую программу. Не могу выйти из цикла сдвига направо после нахождения разности. Также,...

Машина Тьюринга: деление двух натуральных чисел в 16-ной системе счисления
Здравствуйте, передо мной стоит задача построить и запрограммировать машину тьюринга вычисляющую результат деления двух натуральных чисел в 16-иричной системе счисления. Помогите пожалуйста, кто чем...

Машина Тьюринга: найти результат целочисленного деления числа на 2
На информационной ленте машины Тьюринга находится десятичное число. Найдите результат целочисленного деления этого числа на 2.

Машина Тьюринга: вычисление значения функции f(a)=a+5
Составить программу для Машины Тьюринга вычисляющей значение функции f(a)=a+5 Заранее спасибо. Начали проходить, но пока только изучаем готовые алгоритмы, а вот с составлением собственных -...

Построить машину Тьюринга для преобразования слова Р в слово Q
Добрый вечер. Необходимо построить машину Тьюринга для преобразования слова Р в слово Q, если P=abab, Q=abababcdab. Правильно ли я сделал? q0 a R q0 q0 b R q0 q0 S0 a q1 q1 a R q1 q1 S0 b...

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

Построить недетерминированный конечный автомат, допускающий язык, порожденный данной грамматикой
Дано грамматику G = (V, T, S, P), где V = {0, 1, S, A, B}, T = {0,1}, S - начальный символ. Построить язык, порожденную такой грамматикой P = {S → 1B0, B → 1B, B → 0}. Построить...

Построить машину Тьюринга для функции
Исправьте ошибки Построить машину тьюринга для функции: f(x)=x+1, в троичной системе счисления

Восстановить (и нарисовать) граф по данному коду Харари
Восстановить (и нарисовать) граф по данному коду Харари. Про-верить, действительно ли нумерация вершин каноническая (то есть является ли это число на самом деле кодом Харари). Код 795. Перевел в...

Машина Тьюринга: определить, является ли непустое слово записью степени двойки (в двоичной системе)
Помогите с решением Составить таблицу A={0,1}. Для непустого слова P определить, является ли оно записью степени двойки (1, 2, 4, 8, …) в двоичной системе счисления. Ответ: слово 1 (является)...

Алгоритм Маркова: заменить в десятичном числе все четные цифры на «1», а нечетные на «0»
Заменить в десятичном числе все четные цифры на «1», а нечетные на «0».

Построить нормальный алгоритм Маркова, подсчитывающий количество букв в произвольном слове над данным алфавитом
Алфавит НАМ {a, b, c, f, j, r } Я так понял каждую букву нужно превратить в единицу. И потом 11 -> 2 и тд, но в таком случае получается очень много правил. Может есть более правильный вариант

МТ. Считая слово P записью числа в единичной системе счисления, получить запись этого числа в троичной системе
Машина Тьюринга. A. = {| }. Считая слово P записью числа в единичной системе счисления, получить запись этого числа в троичной системе. Под единичной системой понимается если | то в троичной...

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

Машина Тьюринга: в слове все "о" поменять на "а"
Всем доброго времени суток, помогите пожалуйста написать алгоритм ( на машине тьюринга), который в слове, все о меняет на а А={-,a,b,c,o} пример до bcooo после bcaaa

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

Составить алгоритм Маркова в унарной системе счисления
Даны два числа в унарной системе счисления,разделённые пустой яйчейкой.Определить какое число больше,если первое число больше,то на ленте оставить только 1,иначе 2 .Например:||||||| ||| результат:...

Реализовать автомат Мили на триггерах К155ТМ2
Здравствуйте, в контрольной работе по схемотехнике у нас задание построить автомат Мили. Суть такая,что у нас идет умножение по определенному алгоритму, мы сами делаем ГСА и по ней собственно делаем...

Как на Машине Поста будет записано двоичное число
Вот задача: На ленте задано двоичное число, содержащее три разряда и каждая цифра (одна или две метки) которого, отделена от другой пустой ячейкой. Считаем, что старшая двоичная цифра – 1....

В слове P все символы a заменить на b, а все (прежние) символы b – на a
A={a,b}. В слове P все символы a заменить на b, а все (прежние) символы b – на a. Помогите решить задачу, я вообще не разбираюсь но нужно решить.

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

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

Построить граф автомата и найти язык L, допускаемый автоматом
Автомат задан набором ({a, b}, {q1, q2, q3, q4, q5}, Qs, Qf ), где {a, b} — алфавит, Qs — множество начальных состояний (входов), Qf — множество конечных состояний (выходов), и списком дуг с метками,...

Доказательство формулы перевода из кода Грея в двоичный код
Здравствуйте. Сдаю домашнее задание по микро-процессорной технике. Задание звучит следующим образом: "Синтезировать преобразователь пятиразрядного кода Грея в натуральный двоичный код на...

Нормальный алгоритм Маркова: умножение двух чисел, представленных символами 1
Вот такая задача: Построить НАМ, реализующий умножение двух чисел, представленных символами 1. Например, из 111*111 должно получиться 111111111 Подскажите с чего начать вообще построение алгоритма,...

Преобразование КС-грамматики в эквивалентную грамматику
Преобразование КС-грамматику G=(N, \Sigma , P, S) в эквивалентную грамматику, не содержащую бесполезных символов. S\rightarrow A|B A\rightarrow aB|bS|b B\rightarrow AB|Ba|Mb

Составить грамматику, порождающую формальный язык
L(G)={a1a2…anan…a2a1 | ai∈{0, 1}} Кто в этом шарит,помогите решением или дельным советом) Пример с обычной симметрией от центра,но вот как это реализовать на правилах,за любую помощь спасибо)

Машина Тьюринга: транспозиция
построить машину Тьюринга ,которая называется "транспозиция" и обозначается В, и производит перевод 01^x(состояние q1)01^y0 в 01^y(q0)01^x0.

Машина Тьюринга, отнимают от числа число 5, если получается меньше нуля, тогда добавляют 5
Построить МТ и НАМ, которые отнимают от числа число 5, а если получается меньше нуля, тогда добавляют 5. Помогите пожалуйста(

Машина Тьюринга. Сложить два бинарных числа, записанных через разделитель
На ленте через разделитель записаны 2 бинарных числа. Сложить 1е и 2е.

Код Хэмминга
Здравствуйте! Для числа 101110(2) будет код хэмминга 1110011110, это должно быть правильно. А вот для числа 10111(2) у меня получается 111001111, но оно не правильно, в инете не нашел подобных...

Построить автономный автомат Мура, управляющий светофором автоматического регулирования
Дорогие друзья! Нужна Ваша помощь в решение простой задачи. 12. Построить автономный автомат Мура, управляющий светофором автоматического регулирования транспорта на T-образном перекрестке, причем...

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

Машины Поста и Тьюринга. Посчитать количество букв имени (4) и фамилии (7), а затем указать разницу
Помогите решить задачу. На Машине Поста нужно написать программу Необходимо посчитать количество букв имени(4) и фамилии (7) А затем указать разницу.(на сколько фамилия больше имени) Тот же...

Машина Тьюринга: произвести замену буквы А на Б и подсчитать количество замен
произвести замену буквы А на Б и подсчитать количество замен. пожааалуйста помогите

Машина Тьюринга: переместить все буквы “a” в левую, а буквы “b” - в правую части строки
. Дана строка из букв “a” и “b”. Разработать машину Тьюринга, которая переместит все буквы “a” в левую, а буквы “b” — в правую части строки. Автомат в состоянии q1 обозревает крайний левый символ...

Составить алгоритм возведения числа в натуральной записи в квадрат
Задачка 1 курса по алгорифмам Маркова Братья и сёстры, прошу вас помочь мне в решении лабораторной задачи. Нужно составить алгоритм возведения числа в натуральной записи в квадрат. Понятия не...

Машина Тьюринга Прибавить единицу ко входу, заданному в двоичной системе счисления
3)Прибавить единицу ко входу, заданному в двоичной системе счисления

Машина Тьюринга - в слове из нулей и единиц все подпоследовательности из одной единицы занулить
Машина Тьюринга.В слове из нулей и единиц все подпоследовательности из одной единицы занулить, а все подпоследовательности из единиц большей длины, разделенные одним нулем, соединять заменой этого...

Триггер в мультисим
Здравствуйте. Требуется помощь в выборе D-триггера в Multisim . Нужен простой D-триггер для построения ЦА. Нужен триггер без Reset входа Спасибо

Машина Тьюринга, срабатывающая на деление числа на 3 без остатка
2. На ленте машины Тьюринга находится десятичное число. Определите, делится ли это число на 3 без остатка. Если делится, то запишите на ленте 1, если нет – запишите 0. Исходное число должно быть...

Определить конфигурацию, в которую переходит машина Тьюринга
Дана машина Тьюринга с алфавитом A={0,1} и программой q10→0Rq2, q11 → 1Hq2, q20 → 1Hq0, q21 →1Lq2 . Определить конфигурацию, в которую переходит машина Тьюринга после выполнения не более чем 5...

Построить машину Тьюринга, которая будет считать записанные подряд (без пропусков) единицы
Построить машину Тьюринга, которая будет считать записанные подряд (без пропусков) единицы (их число не превосходит n) и запишет их число в системе счисления с основанием n +1, здесь n=3+(mod 13) и N...

Автомат Мура для замка
Здравствуйте! Есть задание: построить автомат Мура, открывающий номерной замок с цифрами 1, 2, 3, 4, 5, как только сумма любых трех чисел последовательности, идущих подряд, станет нечетна. ...

Алгоритм Маркова: приписать слово bac слева к слову P
Составьте Нормальный алгоритм Маркова для следующих условий: A={a,b,c}. Приписать слово bac слева к слову P.

Композиция машин Тьюринга для нахождения количества нечетных цифр в восьмеричной записи числа
Помогите,пожалуйста,в составлении композиций машин Тьюринга для нахождения количества нечетных цифр в восьмеричной записи числа N. Примитивно рекурсивная функция понятно,как составляется к этому...

Сильно связные автоматы
Прошу помочь с доказательствами: Являются ли сильно связными автоматами прямая сумма и объединение сильно связных автоматов ? В случае отрицательного ответа приведите иллюстрирующий пример. ...

Составить программу для машины Тьюринга, оставляющую в непустом слове только первый символ
Составить программу для машины Тьюринга A={a,b,c}. Оставить в слове P только первый символ (пустое слово не менять).

Примените каждую из данных марковских подстановок к слову abcabcabcab максимально возможное количество раз
Пусть для слов в алфавите A={a,b,c} заданы следующие марковские подстановки: a) b → a; г) bc → ca; ж) bca → ⋀; к) bcab → ⋀; б) c → b; д)ca → ab; з) cab → ⋀; л) a → b; в) ab → bc; е)...

Логическая схема кодового замка
Помогите, пожалуйста, решить данную задачу: Вообще не имею представления как сделать эту работу, уже 2 недели ищу материалы в интернете, на завтра нужно Само задание: Построить логическую схему...

Доказать, что функция примитивно рекурсивна
Всем привет, помогите, пожалуйста, справиться с этими задачами: 1) Показать, что если f(x,y) - примитивно рекурсивна, то и f(y,x) - тоже. Видимо, надо плясать от определения, раз ничего не...

Найти язык, порожденный грамматикой
Пусть V=\left, T=\left. Найти язык, порожденный грамматикой G=\left с таким множеством продукций Р: P=\left Добавлено через 15 часов 2 минуты Шарит ктото?

Построить недетерминированный конечный автомат
Построить НКА, допускающий язык из цепочек из 0 и 1, в которых число нулей делится на пять нацело, а количество единиц четно. Это возможно?

Построить конечный автомат, распознающий среди цепочек из нулей и единиц такие, где на каждом третьем месте 0
Доброго времени суток! Помогите, пожалуйста, с решением задачи, а то совсем никак -_- Постройте конечный автомат, распознающий среди цепочек из нулей и единиц такие, в которых на каждом третьем...

Построить мп -распознаватель для цепочек
дан язык (0^n)(1^(m+1))(01)^m (скобки в язык не входят) . грамматика : <S>--><A>1<B> <A>--> e <B>-->e <A>-->0<A> <B>-->1<B>01 Нужно построить распознаватель .

Машина Тьюринга turun на эмуляторе
Можно ли каким-то образом запротоколировать сеанс работы программы на Машине Тьюринга в эмуляторе Unix? У меня cygwin, компьютер не поддерживает виртуальную машину, а ОС я не готов еще поменять. Если...

Машина Тьюринга: исправление ошибки в слове «пороллилагромм»
Написать машину Тьюринга, которая исправляет ошибку в слове «пороллилагромм». помогите, пожалуйста!)

Машина Поста - найдите среднюю метку последовательности и сотрите ее
На ленте машины Поста задана последовательность из 2N + 1 меток. Найдите среднюю метку последовательности и сотрите ее.

Машина Тьюринга, посчитать количество последовательностей
Если хотя бы проверите будет круто, но главный вопрос помечен красным Алфавит: 1,2,3,| и пустая клетка(_) задана последовательность из 1, 2, 3 без пробелов задача машины посчитать количество...

Нормальный алгоритм Маркова: реализация операции сравнения
Доброго времени суток, уважаемые!)) Помогите пожалуйста решить задачку!!!!!!!!!!!!!!!!!!!!! Задать нормальный алгоритм Маркова, реализующий операцию сравнения призначной части двух чисел, заданных...

На ленте машины Тьюринга находится целое положительное число, записанное в десятичной системе счисления
На ленте машины Тьюринга находится целое положительное число, записанное в десятичной системе счисления. Найдите произведение этого числа на число 11. Каретка обозревает крайнюю правую цифру числа.

Конечный автомат: реализация работы простейшего банкомата
При построении автомата необходимо, прежде всего, определить • множество входных сигналов, • множество выходных сигналов, • множество состояний. При этом рекомендуется каждое из состояний...

Машина Поста: определить количество массивов меток
Дано n-количество масивов меток в машине поста. Которые распределены с помошью свободных клеток между собой. Надо определить количество масивов при том что каретка находится напротив первой метки...

Преобразовать недетерминированный конечный автомат в конечный автомат
Здравствуйте, мне в задании дан недетерминированный конечный автомат и его мне надо преобразовать в конечный автомат, вот что у меня получилось S 0 1 a b c b ...

Перечислите отличие и сходство машины Тьюринга и машины Поста
Перечислите пожалуйста , отличие и сходство машины Тьюринга и машины Поста.

Построить КС-грамматику, эквивалентную грамматике с правилами:
Помогите пожалуйста с заданием: Построить КС-грамматику, эквивалентную грамматике с правилами: S : A B | A B S; A B : B A; B A : A B; A : 'a'; B : 'b'; Пытаюсь сделать сам, но никак не...

Машина Тьюринга: вычисление остатка от деления числа 3 в алфавите {|, a0}
Построить алгоритм для машины Тьюринга, вычисляющий остаток от деления числа 3 в алфавите {|,a0}

Из ЛСА построить ГСА
Подскажите в чем ошибка, вроде сделал, но сказали исправить.

Постройте контекстно-свободную грамматику, порождающую заданный язык
Добрый вечер. Помогите пожалуйста решить: постройте контекстно-свободную грамматику, порождающую заданный язык L = ( a^k b^i c^k | i,k \geq 1 )

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

Машина Тьюринга: вычисление функции f(x)=x 1
Добрый вечер, прошу помочь построить машину Тьюринга, вычисляющую функцию f(x) = x+1

Машина Тьюринга для поиска минимума в последовательности чисел
описать алгоритм и построить программу м.Т. для поиска имнимума в последовательности, заданной двоичным кодом. Вход имеет n_1*n_2*n_k выход 1 если m=min _____________ Подскажите с чего начать

Коды, сохраняющие разности
прошу дать пояснения по теме, везде где смотрел лишь один абзац, а на ютубе не нашел видео! как представить не большие целые в таких кодах? как совершать арифметические операции с такими кодами? ...

Заменить слово Р на пустое слово(т.е. удалить все символы)
1. A={a,b,c} Оставить в слове Р только первый символ(пустое слово не менять) 2. A={a,b,c} Заменить слово Р на пустое слово(т.е. удалить все символы)

Конечные автоматы. Книги
Доброго здоровья. На самом деле, литература по КА вполне доступна, ее относительно много, но. Как правило это академические вещи, лишенные практических примеров. В настоящий момент меня крайне...

Машина Тьюринга: вычисление f(x)=x-3, где x принадлежит множеству натуральных чисел, в семеричной системе счисления
составить программу машины Тьюринга для вычисления функции f(x)=x-3, где x принадлежит множеству натуральных чисел, в семеричной системе счисления. для определения q нужно определять закономерность...

НАМ Копирование слова в алфавите {0,1}
Реализовать операцию копирование в алфавите {0,1} , то есть получить из слова a слово a*a. Пример, почему-то не рабочий.

Машина Тьюринга: отыскать единицу, примыкающую слева к первому слева массиву из трех нулей («окаймленному» единицами)
1.Машина начинает работу с самой левой непустой ячейки и отыскивает единицу, примыкающую с левой стороны к первому слева массиву из трех нулей («окаймленному» единицами). Головка останавливается на...

Считая непустое слово P записью числа в троичной системе счисления определить является оно четным числом или нет
Приветствую уважаемые форумчане!!! Столкнулся с данной задачей, буду без мерно благодарен за помощь в ее решении... Машина Тьюринга A=(0,1,2) Считая непустое слово P записью числа в троичной...

Машина Тьюринга: проверить, можно ли составить треугольник с заданными сторонами
Помогите пожалуйста с задачей на машине Тьюринга: дано три числа в двоичной системе а, в,с , нужно проверить можно ли составить триугольник со сторонами а, в, с

Грамматика, порождающая формальный язык
Для формального языка L(G) = {a1a2...anan...a2a1 | ai є {0, 1}} составить грамматику

Привести к нормальной форме Хомского
Привести к нормальной форме Хомского грамматики с правилами: Поскольку удаление Эпсилон-правил может привести к появлению цепных правил, а удаление бесполезных нетерминалов — к появлению...

Построить машину Тьюринга в алфавите {a0, *, 1} для вычисления функции f(n)=2n
Приветствую всех! если нетрудно, помогите решить, совсем плохо логика работает( не доходит(

Машина Поста
На ленте записаны 2 числа в унарной системе счисления(как цепочки подряд идущих меток).Числа,разделены одной пустой ячейкой,над которой находится каретка.Число слева от каретки больше числа справа от...

Машина Тьюринга: реверс строки
Долго мучаюсь и не могу придумать, как правильно и за наименьшее число состояний написать программу для МТ, переворачивающую строчку в бин. алфавите(например: 11010->01011). Я составил свою за 6...

Машина Поста. Вычислить сумму нескольких чисел
Надо решить задачу с помощью Машины Поста! Задача: "Вычислить сумму нескольких чисел" Добавлено через 1 час 39 минут Промежуток между числами строго в одну клетку.

Машина Тьюринга: вставка символа A после первого символа непустого слова Р
нужно решение А={a,b,c}. Составьте программу для МТ вставки символа а после первого символа непустого слова Р.

Алгоритм для программы по вычислению двоичного логарифма двоичного числа в машине Тьюринга
Помогите придумать алгоритм для программы по вычислению двоичного логарифма двоичного числа в машине тьюринга

Машина Тьюринга: из E01011000E получить E111E (удалить все нули)
извините если подобный вопрос уже был, но не нашел аналога. помогите реализовать на машине тьюринга алгоритм, чтобы из E01011000E получить E111E, то есть удалить все нули. я думаю нужно просто...

Построить машину Тьюринга для следующей функции f(x,y)=2y-2x
Помогите, пожалуйста, построить машину Тьюринга для следующей функции f(x,y)=2y-2x. И какая конфигурация будет в начале работы на ленте?

Докажите, что следующая функция вычислима по Тьюрингу
Докажите, что следующая функция вычислима по Тьюрингу, построив соответствующую машину Тьюринга : f(x,y)=x+y

Машина Тьюринга: сложение двух целых чисел, заданных набором единиц
Написать программу для машины Тьюринга, складывающую два целых числа, заданных набором единиц. Пусть начальное состояние информационной ленты МТ: _11111_1111__ Головка находится напротив левой...

Дизъюнкция на машине Тьюринга
Всем привет! Есть такое задание: Построить машину Тьюринга, выполняющую операцию дизъюнкции. И вот тут не всё понятно. В какой системе это делать? До этого вся работа была в унарной системе. Если...

Алгоритм Маркова: x+3/2
Помогите. Построить алгоритм Маркова, вычисляющий функцию x+3/2

Эквивалентность двух машин Тьюринга
Как доказать, что машина Тюринга, которая не ограничена в оба конца эквивалента машине, которая неограничена лишь вправо?

Определить тип грамматики и язык, который порождает грамматика
Дана следующая грамматика: G = ({S, {L}_{a}, {L}_{b}, {R}_{a}, {R}_{b}, {W}_{a}, {W}_{b} }, {a, b}, P, S) P: S \rightarrow \lambda | {L}_{x}{R}_{x} {L}_{x} \rightarrow x|{L}_{x}y{W}_{y} ...

Машина Тьюринга. Требуется, если первый и последний символы слова одинаковы, заменить все слово этими символами
Здравствуйте! Буду крайне признателен, если поможете с задачей по Машине Тьюринга. Формулировка задачи: На ленте расположено слово из букв a, b и c, например: abcbca. Требуется, если первый и...

Машина Тьюринга. Нужно правильно вычислить функцию f(x;y)=2x+y
Нужно правильно вычислить функцию f(x;y)=2x+y. Благодарю заранее)

Выполнить циклический сдвиг двоичного числа влево на один разряд, используя Нормальные Алгоритмы Маркова
Условие задания (Помогите пожалуйста с защитой) Выполнить циклический сдвиг двоичного числа в лево на один разряд используя Нормальные Алгоритмы Маркова

Копирование блока едииниц машиной Поста
Добрый день, форумчане Последний разговор с преподавателем вылился в данную проблему: Машиной Тьюринга скопировать группу единиц - проще некуда, что мной и было сделано Но тут же была задана...

Составить нормальный алгоритм Маркова, который слово, отличающееся от слова "bbcca", перестроит в пустое слово
Задан алфавит A={a,b,c}. Составить нормальный алгоритм, который слово, отличающееся от слова "bbcca" перестроит в пустое слово. Нужна помощь в решении данной задачи. При построении алгоритма...

Создать машину Тьюринга для функции
Добрый вечер, уже третий день не могу понять как написать машину тьюринга для функции f(x, y) = 2(x – y) (x ≥ y). Заранее благодарю

Машина Тьюринга. Дано двоичное число. Слева записать десятичное значение, соответствующее количеству нечетных триад
Дано двоичное число, содержащее 3n разрядов. Слева записать десятичное значение, соответствующее количеству нечетных триад. Начальное положение каретки – над крайней правой цифрой числа.

Алгоритм Маркова: увеличение шестеричного числа на 3
Написать алгорифм Маркова для вычисления функции f(x)=x+3, где x задано в шестеричной системе счисления Наработка: Чего ещё не хватает? Не все числа считает. (точнее знаю, в каком месте не...

Машина Тьюринга, вычисляющая x+y+z
Помогите решить задачу Составить программу для машины Тьюринга, вычисляющую значения функции x+y+z. Заранее спасибо

Машина Тьюринга: вычисление функции f(x)=2x 4
Довести, что функция f(x)=2x+4 вычислимая по Тьюрингу, для этого записать Машину Тьюринга которая ее обчислит. Буду признателен за любую помощь! Можете хотя бы вкратце объяснить как функция будет...

Преобразовать КС грамматику в эквивалентную грамматику, не содержащую бесполезных символов
Подскажите, пожалуйста, как выполнять данное задание? Необходимо преобразовать КС грамматику G=(V,N,S,R) в эквивалентную грамматику, не содержащую бесполезных символов 1) 1. S->SRT|c 2. R -> aRa|b...

Машина Поста: нахождение разности двух неотрицательных целых чисел
Здравствуйте, не представляю как это должно выглядеть, помогите с заданием. Заранее спасибо. Составить программу нахождения разности двух неотрицательных целых чисел a и b, находящихся на ленте...

Построить детерминированный конечный автомат
Всем привет, есть такая задача: Построить ДКА (Детерминированный конечный автомат), допускающий в алфавите {0, 1} все строки, в которых модуль разницы количества символов 0 и символов 1 нацело не...

Построить машину Тьюринга, применимую ко всем словам
Привет, местные эксперты. Пришел за вашей помощью. Построить машину Тьюринга, применимую ко всем словам x_{1}x_{2}...x_{n} в алфавите {a,b} и переводящую их в слово \alpha =...

Нормальный алгоритм Маркова для умножения натуральных чисел
Построить НА для выполнения умножения натуральных чисел в десятичной системе счисления

Написать формулу числовой функции, вычисляемой машиной Тьюринга
Написать формулу числовой функции, вычисляемой машиной Тьюринга с множеством внутренних состояний {0, 1, 2, 3, 4, 5, 6}, где 0 - заключительное, а 1 - начальное состояния, если машина задана своей...

Машина Тьюринга: распознать строки с одинаковым числом 0 и 1
доброго времени суток! помогите пожалуйста решить следующую задачу: Распознать строки с одинаковым числом 0 и 1. в архиве прога и файлы к ним.

Создать машину Тьюринга, определяющую, содержит ли слово равное число единиц и нулей
Всем привет, не понимаю как решить задачу, помогите. Условие: Создать машину Тьюринга, что решает задачи определения, содержит ли слово в алфовите (0 , 1) равное число единиц и нулей. Например,...

Автомат Мура на JK-триггерах
Добрый день. Необходимо построить автомат Мура на JK-триггерах. Плюсом будет помощь в построении этого автомата в среде Quartus II в графическом виде.

Машина Тьюринга. Умножение целого положительного числа на 11
Помогите,пожалуйста,решить задачу по машине Тьюринга! На ленте маины Тьюринга находится целое положительное число,записанное в десятичной системе счисления.Найдите произведение этого числа на число...

Определить язык, распознаваемый данным автоматом
Задача №8. Имеется МП-автомат P=({q0,q1,q2,q3,q4,q5},{k,m,n},{Z,a},&,q0,Z,{q0}) Определить язык L, распознаваемый данным автоматом. Выписать минимальную цепочку языка. ...

Построить машину Тьюринга для удвоения слова
A ={a,b}. Удвоить слово P ( например авв->аввавв ). Машина Тьюринга.

Описать грамматику, порождающую язык
Ребята, выручайте срочно плиз! Зачет горит, срок - неделя, иначе... У всех вариант более или менее понятный, но у меня вот какая проблема: Описать грамматику, порождающую язык. Написать...

Машина Тьюринга: реализовать функцию выбор аргумента над числами в унарном коде.
кто что может подсказать.. реализовать функцию выбор аргумента над числами в унарном коде

Блок-схема деления чисел в формате с плавающей точкой в обратном коде
Доброе время суток! Может у кого есть готовая блок-схема деления чисел в формате с плавающей точкой в обратном коде? буду признательна, если поделитесь) Деление двоичных чисел с плавающей запятой,...

Машина Тьюринга: вычитание 1 из целого неотрицательного числа
Добрый день, помогите, пожалуйста.... 1. Построить машину Тьюринга (результат представить в форме таблицы): Вычесть 1 из целого неотрицательного числа (вычислить функцию F(x)=x–1). Операции...

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

Построить машину Тьюринга, вычисляющую числовую функцию, и проверить ее работу
Построить машину Тьюринга, вычисляющую числовую функцию f(x,y) и проверить ее работу. f(x,y)={x+y, если х>=y; 0, если x<y}

Построить Машину Тьюринга, правильно вычисляющую функцию
Надо написать Машину Тьюринга для вычисления функции. По функции: из трех переменных мы выбираем y, зачищаем x, а вот как прибавить два - не знаю, в q1 не должно переходить. По возможности описать...

Составить программу нахождения разности двух целых неотрицательных чисел a и b
Составить программу нахождения разности двух целых неотрицательных чисел a и b. Если a меньше b, то перед разностью через одну пустую ячейку поставить метку. Каретка находится над крайней левой...

Реализовать функцию на машине Тьюринга
f(x) = 2*x-3 реализовать на Машине Тьюринга

МТ + НАМ: если слово P содержит одновременно символы a и b, то заменить P на пустое слово
A={a,b}. Если слово P содержит одновременно символы a и b, то заменить P на пустое слово.

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

Найти все делители двоичного числа, используя машину Тьюринга
Как вообще такое делать, какие алгоритмы нужны, притом что в алфавите \sum \epsilon \left(0, 1 \right) расширять его нельзя

По заданной машине Тьюринга с алфавитом A={a,1} и алфавитом состояний Q={q0,q1}, определите выходное слово
По заданной машине Тьюринга с алфавитом A={a,1} и алфавитом состояний Q={q0,q1}, определите выходное слово, если автомат находится в состояние q1, и обозревает указанный символ входного слова. 1)...

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

Детерминирование автоматов
Кто-нибудь может объяснить как детерминировать автомат? или ссылку скиньте где это объясняется

По заданной регулярной грамматике построить НКА
А) По заданной регулярной грамматике построить НКА, Б) Детерминизировать полученный НКА, В) Полученный в Б) ДКА минимизировать, Г) По минимальному ДКА построить леволинейную грамматику....

Машина Тьюринга
Нужно реализовать машину Тьюринга на С++. Кто-нибудь, подскажите где можно найти код или как это сделать?

Построить Машину Тьюринга, вычисляющую значение функции f(x,y)=4-x/y2
Здравствуйте!Помогите,пожайлуста, с задачей,очень нужно!!!!!! Построить Машину Тьюринга,вычмсляющую значение функции f(x.y)=4-x/y2 Заранее спасибо!

Форма Бэкуса—Наура
Здравствуйте Уважаемые Форумчане. Есть такое задание: Входной язык содержит логические выражения, разделенные символом ; (точка с запятой). Логические выражения состоят из идентификаторов, констант...

Нормальные алгоритмы Маркова. Из слова P удалить второй символ, если такой есть
A={a,b,c}. Из слова P удалить второй символ, если такой есть.

Построить автомат Мура, открывающий номерной замок с цифрами 1, 2, 3, 4, 5
Построить автомат Мура, открывающий номерной замок с цифрами 1, 2, 3, 4, 5, как только произведение любых двух чисел последовательности, идущих через одно станет нечетно — указать входной алфавит;...

Построить регулярную грамматику
Помогите с решением 2 задач по курсу «Формальные языки и грамматики» 1.Построить регулярную грамматику, эквивалентную грамматике с правилами: S → AA A → B | BA B → 0 | 1

Построить схему на заданном базисе ИЛИ-НЕ
Привет! У меня курсовая работа сумасшедших масштабов, но на пункте разработки схемы при заданном базисе ИЛИ-НЕ, с использованием микросхем серии кр1553 я не могу понять: Могу ли я использовать...

Найти минимальный конечный детерминированный автомат, распознающий язык
Здравствуйте. У меня такой вопрос Найдите минимальный конечный детерминированный автомат, распознающий язык {b}^{*}({ab}^{*}{ab}^{*}ab\bigcup \lambda ) В ответе укажите количество выходных...

Алгоритм Маркова: если буквы в непустом слове P не упорядочены по алфавиту, то заменить P на пустое слово
A={a, b, c}. Если буквы в непустом слове P не упорядочены по алфавиту, то заменить P на пустое слово, а иначе P не менять.

Машина Маркова. Найти частное и остаток при делении числа на 3 (в кодах)
Найти частное и остаток при делении числа на 3 (в кодах). Примерно как это должно выглядеть я понимаю. |>* (|-пустое слово) *111>1* Но при таком алгоритме, он с первой строчки не уйдет. Как...

Машина Поста,Тьюринга и маркова
Привет,хочу по просить о помощи в написании программы на машинах поста,тьюринга и маркова Или хотя бы объяснить по подробнее....заранее огромное спасибо Пусть P имеет видQ-R , где Q и R -...

Построить машину Тьюринга применимую ко всем словам
Построить машину тьюринга применимую ко всем словам w=(x1,x2,....,xn) где xk={a,b}, которая слово w переводит в слово\alpha =\begin{cases} & \text{n-nechentoe } {x}_{1} \lambda {x}_{3} \lambda...

Описать автомат, который переводит десятичные цифры в двоичные последовательности
Описать автомат с двумя состояниями, который переводит десятичные цифры 0,1,2,...,9 поданные на вход, в двоичные последовательности 0000, 0001,....,1001 соответственно, а двоичные последовательности...

Машина Тьюринга: 8-разрядный сумматор положительных целых чисел, с помощью поразрядного сложения
Задача: Разработать 8-разрядный сумматор положительных целых чисел (в двоичной с.с.), с помощью ПОРАЗРЯДНОГО сложения. Исходные данные выглядят так: 10101010*10110101 Выходные данные: Если...

Cоставить алгоритм Заменить слово P на пустое слово (удалить из Р все символы)
Помогите пожалуйста составить алгоритмы, прям очень надо!!! 1)A{a,b,c}. Заменить слово P на пустое слово т.е. удалить из Р все символы.

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

Составить грамматику, порождающую формальный язык
Может, у кого есть решение? 1) составить грамматику, порождающую формальный язык, заданный в соответствии с вариантом; 2) определить тип формальной грамматики и языка по классификации Хомского;...

Алгоритм Маркова. Написать 2, если длина слова четная и 1, если нечетная
Помогите ч заданием: Дано алфавит : ( a, b , c) написать 2 если длина слова парная и 1 если не парная

Задачка по машине Поста, Тьюринга и нормальному алгоритму Маркова
Простите, если повторяюсь и данные задачи уже есть решенные на этом форуме. 1. Построить машину Поста: На ленте машины Поста расположен массив из N меток. Составьте программу, действуя по которой...

Расскажите как вам удалось выучить "Теорию Автоматов". Проблемы с изучением
Обращаюсь к тем у кого в универе было туго с математикой. Расскажите как вам удалось выучить "Теорию Автоматов", по какой литературе вы учили, и какие предварительные знания вам понадобились чтобы...

Вычислить функцию, полученную операцией примитивной рекурсии
Функция f(x,y) получена операцией примитивной рекурсии из функций g(x) и h(x,y,z). Вычислить f(A), если C=6, А=20, h(x,y)=4x+y Решение: f(0) =C=6 f(1)=h(0,f(0))=6 f(2) =h(1,f(1))=10...

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

Построить машину Тьюринга с внешним алфавитом {0,1}, реализующую вычисление функции f(x)=x+7
1. Построить машину Тьюринга с внешним алфавитом {0,1}, реализующую вычисление функции f(x)=x+7. Пример выполнения задачи приложен

Составить грамматику, порождающую формальный язык
1)составить грамматику, порождающую формальный язык, заданный в соответствии с заданием; 2) определить тип формальной грамматики и языка по классификации Хомского; 3) разработать программное...

Разработать алгоритм Маркова: вычисление функции f(x)=x/2
Помогите, пожалуйста, построить алгоритм Маркова для функции f(x)=x/2. Если нацело не делится, то округление идет в большую сторону. Заранее спасибо:)

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

Зачем нужно знать теорию автоматов простому человеку
Здравствуйте. Зачем нужно знать теорию автоматов простому человеку ? Какая ему от этого будет польза ?

На машине Тьюринга записано число в двоичной сист.счисления. Как определить, делится ли оно на 3
НА машине Тьюринга записано число в двоичной сист.счисления, как определить делится ли оно на 3? Иначе говоря как проверить делится ли число в двоичной сист.сч. на 3?

Составить грамматику, порождающую формальный язык
Дан формальный язык: L(G)={a1a2...ana1a2...an|ai∈{c, d}} Нужно составить грамматику, порождающую данный формальный язык и, желательно, определить тип грамматики по классификации Хомского. Сам я не...

Есть некое регулярное выражение, по которому нужно построить конечный автомат
Здравствуйте! Есть некое регулярное выражение, по которому нужно построить конечный автомат (x*|y)* , я не как не могу понять как его построить, знак итерации после скобор вводит меня в ступор :(

Построить ПЛ-грамматику, порождающую L
Язык над алфавитом Σ = {0, 1}, состоящий из всех слов, которые имеют четную длину тогда и только тогда, когда они содержат подслово 011. Задание: (i) Построить ПЛ-грамматику G, порождающую L; ...

Алгоритм Маркова: увеличение троичного числа на 1
Составьте нормальный алгоритм Маркова, вычисляющий функцию (в скобках указана система счисления): f(x)=x+1, (3);

Построить конечный автомат, распознающий множество
в данный момент сижу на экзамене, кто может чем помочь, помогите 2)построить конечный автомат, распознающий множество {10(10)n010, n>2} нужны не программы, а просто текст, который можно...

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

Объясните, что такое префикс в регулярном выражение
Множество всех цепочек, в которых поровну нулей и единиц и ни один префикс не содержит нулей на два больше, чем единиц, или единиц на две больше, чем нулей. Объясните, что такое префикс в регулярном...

Машина Тьюринга распознавание языков
Необходимо построить машину Тьюринга в системе JFLAP для распознавания языка L = {www^R: w принадлежит {a, b}}. w - любая строка, любой длины кроме нулевой, состоящая из символов a и b, например,...

Нормальный алгоритм Маркова: f(x,y)=x+y в двоичной системе счисления
Составить нормальный алгоритм Маркова,вычисляющий функцию (в скобках указана система счисления): f(x,y)=x+y, (2)

Найдите НКА конечные автоматы, которые допускают следующие языки
Найдите нка конечные автоматы, которые допускают следующие языки. Постарайтесь максимально использовать возможности нка:множество цепочек {0,1,...,9}, последняя цифра цепочки которых больше нигде в...

Доказательства по индукции
Если ^σD(q, w) =p, то ^σN(q, w) ={p}, где индукция велась бы по |w|. Моё доказательство : w=(x, a), где а- последний символ множества, тогда ^σD((q, х), а) =p и ^σN((q, x), a) ={p} . Так как...

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

Детерминированный конечный автомат из шаблонов поиска (wildcards) и регулярных выражений
С программным построение автомата для шаблона a*bc*d??e* проблем не возникает. Но с шаблоном, который не оканчивается на звёздочку (например a*b??c) появляются сложности. Т.к. автомат для шаблона...

Построить оптимальные коды по методу Хаффмана
Для заданных распределений вероятностей появления букв построить оптимальные коды по методу Хаффмана. 1) Р=(0,34;0,18;0,17;0,16;0,15); 2) Р=(0,6;0,1;0,09;0,08;0,07;0,06);...

В бинарном слове поменять местами символы (машина Тьюринга)
Машины Тьюринга В бинарном слове поменять местами каждый первый символ с каждым вторым. Помогите пожалуйста Правило 5.5: "Запрещено размещать тему в нескольких подразделах одного раздела...

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

На ленте машины Поста отмечен массив меток
2)На ленте машины Поста отмечен массив n меток. Найдите число 2n + 1 и проверьте, делится ли оно на 3. Если да, то после числа через одну пустую ячейку поставьте две метки, если нет — поставьте три...

Построить машину Тьюринга
Помогите с алгоритмом в данной задаче:

Создать нормальный алгоритм Маркова для поразрядного сложения двух двоичных чисел
Здравствуйте, помогите! задание: создать нормальный алгоритм Маркова для поразрядного сложения двух двоичных чисел

Алгоритм Маркова: из слова Р удалить третье вхождение символа "а"
Ребят, помогите, пожалуйста, сделать это чертово задание. Дано: Алфавит {a,b,c} Из слова Р удалить третье вхождение символа "а"

Построить машину Поста, которая выяснит, делится ли число на 3
помогите пожалуйста.. срочно нужно решение.. На ленте машины Поста расположен массив из N меток. Составьте программу, действуя по которой машина выяснит, делится ли число на 3. Если да, то после...

Машина Тьюринга
Помогите пожалуйста, на этой теме не был, болел, и теперь ни черта не могу понять, преподователь задал сделать лабу по теме "Машина Тьюринга" а задание вот такое : 5+2 . 5-2. , и что с этим делать...

Построить машину Тьюринга и нормальный алгоритм Маркова, правильно вычисляющие функцию f(x)=x-4
Построить машину Тьюринга и нормальный алгоритм Маркова, правильно вычисляющие функцию f(x)=x-4. Будьте добры помогите выполнить задание, в связи с обстоятельствами нужно сдать раньше срока.

Постройте конечный автомат
Добрый день!Помогите пожалуйста решить эти задачи,уже всё голову сломал. Задача 16. Постройте конечный автомат, выдающий на выходе символ “!”, всякий раз, когда во входной двоичной...

Алгоритм Маркова: вычисление функции f(x)=x–4(10-я), где x задано в семеричной системе счисления
Написать алгорифм Маркова для вычисления функции f(x)=x–4(10-я), где x задано в семеричной системе счисления и не имеет незначащих нулей. Ответ так же должен быть получен в семеричной системе...

Машина Тьюринга Если во входном слове чётное число символов, выдать 0, если нечётное - выдать 1
2)Если во входном слове чётное число символов, выдать 0, если нечётное - выдать 1.

Определите нормальный алгоритм логического сложения двух двоичных чисел
2. Определите нормальный алгоритм логического сложения двух двоичных чисел.

Машина Тьюринга - проверка делимости на 11
Помогите на Машине Тьюринга решить задачу на проверку делимости на 11!

Нарисовать для JK триггера временные диаграммы
Надо нарисовать для JCK триггера: Q1 i Q2 с запрещенным связью Q1 i Q2 для инверсии

Нормальный алгоритм Маркова: частное натуральных чисел
Постройте нормальный алгорифм, перерабатывающий всякую пару натуральных чисел M*N в частное этих чисел.

Построить машину Тьюринга
Здравствуйте! Чувствую, что мое решение неправильно, хотелось бы развеять эти сомнения. Построить машину Тьюринга в алфавите А={0,1}, которая, начав работу с последней единицы массива из единиц,...

Построить машину Тьюринга, вычисляющую функцию f(a,b)=a+b+1
Добрый день, может кто-нибудь помочь построить машину Тьюринга, вычисляющую функцию f(a,b)=a+b+1 ? или может у кого-нибудь что-то похожее на этот пример есть) Для представления чисел можно...

Машина Тьюринга. Перенести первые 2 символа в конец
Дан алфавит A ={1, 2, 3, ao }. Создайте МТ, действия которой заключались бы в переносе двух первых цифр в конец любого заданного в алфавите А слова. Примените созданную МТ к словам «132311» и «33112».

Считая непустое слово записью числа в троичной системе, получить запись этого числа в единичной системе
Разработка программ для алгорифмов Маркова Добрый вечер, форумчане! Помогите пожалуйста сделать задание, я пытался понять как реализовать, но то ли не с должным энтузиазмом старался, то ли...

Машина Тьюринга: найти результат целочисленного деления десятичного числа на 2
На информационной ленте машины Тьюринга находится десятичное число. Найти результат целочисленного деления этого числа на 2.

Машина Тьюринга: умножение в троичной системе счисления
Доброго здравия, прошу помочь с заурядной задачей с которой не в силах справиться. Алфавит машины Тьюринга: {0, 1, 2, ∅}. Разработать программу для машины Тьюринга, умножающую записанное на ленте...

Построить машину Тьюринга, умножающую число на 2
Построить машину Тьюринга для умножения целого неотрицательного числа на 2 в десятичной системе счисления.

Машина Тьюринга: найти произведение заданного числа на 3
На ленте машины Тьюринга находится целое положительное число, записанное в десятичной системе счисления. Найдите произведение этого числа на 3. Каретка обозревает крайнюю правую цифру числа.

Машина Поста: Стереть все метки, кроме крайних, таким образом, чтобы положение каретки при этом не изменилось.
мне дали две задачи,на машину поста,помогите решить!!!! 1)На информационной ленте машины Поста находится массив меток. Каретка находится где-то над массивом (но не над крайней меткой). Стереть все...

К какому типу по Хомскому относится данная грамматика?
К какому типу по Хомскому относится данная грамматика (указать максимально возможный номер)? Какой язык она порождает? Каков тип языка? Выписать подтверждающую ответ грамматику, в состав которой...

Машина Тьюринга: оставляет на ленте 001100, если число четное и 00100, если нечетное.
По словесному описанию машины Тьюринга построить ее программу (в алфавите {0,1}, слова из 1, разделенных одним 0, 00 – конец слова). Привести 2-3 примера обработки различных входных слов. ...

Алгоритм Маркова. Умножение данных двоичных чисел
Помогите написать правила для умножения двух двоичных чисел.

Машина Тьюринга. Считая слово P записью числа в единичной системе счисления, увеличить это число на 2
Помогите пожалуйста решить 2 задачки: 1) A={ | }. Считая слово P записью числа в единичной системе счисления, увели-чить это число на 2. 2) A={a,b,c}. Если в слове P не менее двух символов, то...

Поменять местами левую и правую половины числа (машина Тьюринга)
Дано двоичное число, состоящее из 6 цифр. Поменять местами левую и правую половины числа. Для решения поставленной задачи создать машину Тьюринга в табличном виде. Добавлено через 2 минуты Как...

Найти язык и построить таблицу состояний
Найти язык (множество цепочек) что распознается недетерминированным конечным автоматом без выхода. За диаграммой состояний конечного автомата с выходом построить таблицу состояний.

Реализовать соответствующую операцию в единичной системе счисления
как будет выглядеть решение задачи в машине тьюринга? Пусть слово P имеет следующий вид: где ⊗ – один из знаков +, –, ×, /, ÷, ↑ или ↓, слева от которого указано n палочек, а справа – m палочек....

Машина Тьюринга для функции
f(x) = x+2, если х - парное четное х+3, если х - непарное нечетное

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

Проверка делимости на машине Тьюринга
Как можно на ленте проверить делится ли оно число на другое помимо вычитания первого числа из второго пока не получу равное ему?

Машина Тьюринга - имитационное моделирование
На ленте находятся два числа N и Q, разделенные одной пустой ячейкой. Напишите программу работы одной из алгоритмических машин для нахождения суммы N+Q. Используя алгоритмическую машину Тьюринга...

Сконструируйте машину Тьюринга, которая выступит в качестве двоично- восьмеричного дешифратора
Сконструируйте машину Тьюринга, которая выступит в качестве двоично- восьмеричного дешифратора.

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

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

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

Удаление пустого правила
здравствуйте. я выполняю курсовую работу. для регулярного выражения построена праволинейная грамматика . необходимо выполнить приведение этой грамматики. для этого помимо прочего нужно удалить...

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

Машина Поста: умножение двух натуральных чисел, записанных на произвольном расстоянии друг от друга
Помогите пожалуйста с решением, никак не понимаю что делать нужно.... 1) На ленте находятся два числа K и F, решите задачу: умножение двух натуральных чисел, записанных на произвольном расстоянии...

Машина Тьюринга: если число в 5-чной системе счисления чётно, то прибавить к нему 1, если нет - стереть всё слово
Задано число в 5-чной системе счисления. Если оно чётное, то прибавить к нему 1, если нет – стереть всё слово. Построить машину Тьюринга. Проверить работу машины на примере. Головка автомата...

Построить машину Тьюринга, реализующую умножение на 3
Построить машину тьюринга (*, _, 1) реализующей умножение на 3 Доброго времени суток. Запрашиваю команду помощи - помогите написать эту программу. Через 4 часа ехать ее сдавать, есть только идея...

Вычитание в пятеричной системе на машине Тьюринга
Напишите, пожалуйста, вычитание в пятеричной системе на машине Тьюринга 123-34. Срочно!!! Заранее спасибо!!!

Алгоритм Маркова: вычисление функции f(x)=x*4+2
Разработать алгорифм Маркова для вычисления функции f(x)=x*4+2, где x задано в двоичной сс, а 4 и 2 в десятичной сс. Ответ оставить в двоичной сс.

Конструирование машины Тьюринга
Здравствуйте многоуважаемые обитатели форума. Я простой студент, не самый умный, и у меня до начала сессии очень много долгов по одной дисциплине. Я не прошу решения, просто объясните что тут...

Машина Тьюринга. Уменьшить на 1 число α (|α|≥1) в системе счисления (0,1,2,3,4,5)
Уменьшить на 1 число α (|α|≥1) в системе счисления (0,1,2,3,4,5). Записать последовательность конфигураций машины Тюринга для слова 2100000. В чём заключается задание? Нужно число 2100000...

Определить формулу числовой функции, вычисляемой машиной Тьюринга
Определить формулу числовой функции f(x1, x2,…, xn), вычисляемой машиной Тьюринга. Проверить формулу путем пошагового моделирования на 2 наборах входных данных. обьясните пожалуйста, как это...

Как обозначается команда на перемещение в программе Алго2000 в машине Тьюринга?
Как обозначается команда на перемещение в программе Алго2000 в машине Тьюринга?

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

Машина Тьюринга. Приписать справа к слову P символы bc (P  Pbc)
Приписать справа к слову P символы bc (P  Pbc)

Построить конечный автомат, распознающий конкатенацию языков, заданных конечными автоматами
Построить конечный автомат, распознающий конкатенацию языков, заданных конечными автоматами, диаграммы которых представлены на рис., в случаях, когда подмножества «хороших» состояний этих автоматов...

Грамматика. Какой язык она порождает?
Нужно подобрать L, G по графу Г( G ). Построил грамматику. Z->aZ Z->bB B->aB b->bK K->bZ Не могу понять какой язык она порождает. Помогите.

Машина Поста: умножение
можете объяснить умножение на машине поста?

Вопрос о символе в грамматике
Добрый день. В LL(k)-грамматике G = (N, Σ, P, S) каждое правило имеет вид (α→β)∈P, где: a - ЭТО НЕТЕРМИНАЛ. а что такое β? Заранее спасибо.

Построить машину Тьюринга для вычисления единицы из двоичного числа
Построить машину Тьюринга для вычисления единицы из двоичного числа. Каретка стоит на крайнем левом символе

Как понять, что машина Тьюринга зациклилась?
Доброго времени суток, обыватели. Никак не могу приложить ума, как определить, что машина зациклилась? Реализовал в программе эмулятор через консоль и нужно, чтобы программа сама определяла, что она...

Как выглядит машина Тьюринга для функции f(x,y)=x-y/3
Как выглядит машина для функции f(x,y)=x-y/3 ?

Составить алгоритм Маркова, вычисляющий функцию f(x,y) = x-y
Привет всем. Собственно, задание в названии темы. Алфавит A={0,1} Не могу понять, как составлять алгоритмы, если в функции 2 аргумента? Я искал по форуму подобные темы, но нашёл только алгоритм для...

Алгоритмы Маркова: подсчитать различные символы
Составить нормальный алгоритм Маркова, который будет подсчитывать из скольки различных символов состоит входное слово. Ответ получить в единичной системе счисления. acaac = ||

D-триггер на элементах ИЛИ, НЕ, И
Добрый день. Помогите пожалуйста построить D-триггер на элементах ИЛИ, НЕ, И. Заранее спасибо.

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

Машина Тьюринга: все символы A перенести в конец последовательности
Дана последовательность символов A и B Необходимо все символы A перенести в конец. В итоге должно быть ABAABA->*B**BAAAA Заранее спасибо)

Нормальный алгоритм Маркова: вычисление разности двух чисел в унитарном коде
Построить нормальный алгоритм Маркова, вычисляющий разность двух чисел в унитарном коде f(x1, x2) = x1 - x2 , причём x1 >= x2. как работать с двумя аргументами? я догадываюсь, что нужно в x1...

Построить в алфавите {0, 1} машину Тьюринга, переводящую конфигурацию К1 в конфигурацию К0
0|a|b|c|a|b|c|a|a|a|0 '''''''''''''''''''''''''''^ '''''''''''''''''''''''''''| Для указанной ленты конфигурация K1=0^(2)q1^(3)0 Построить в алфавите {0, 1} машину Тьюринга, переводящую...

Построить машину Тьюринга для перевода из одной заданной конфигурации в другую.
Помогите пожалуйста, ргз срочно нужно сдать((( Построить машину Тьюринга для перевода из начальной конфигурации в заключительную. На ленте МТ записаны лишь нули и единицы, при этом пустые ячейки...

Машина Тьюринга: вычислить поразрядную функцию Шеффера (штрих Шеффера – И-НЕ) двоичных чисел, разделенных знаками "|"
Помогите пожалуйста, что требуется в условии и как применить в машине тьюренга.(машину тьюринга - знаю) Вычислить поразрядную функцию Шеффера (штрих Шеффера – И-НЕ) двоичных чисел, разделенных...

Машина Тьюринга, вычисление функции х
Построить машину Тьюринга, которая вычисляет функцию f (x), где x натуральное число или 0. При этом учесть, что первоначальное число, которое является значением x, подается в виде 01х0 = 01111 ......

Минимизированный автомат Мили
Добрый день. Может кто знает как это делается.

Составить алгоритм Маркова для удаления в слове второй буквы а
3.10 A={a,b,c,d}. Дано слово любой длины, содержащее минимум две буквы а. Удалите в слове вторую букву а.

Проверка понятия создания автомата Мили :-)
У меня есть задание По данной кодовой комбинации (x y y x y y x x) построить дешифратор с входным алфавитом x, y и записать его: 1) диаграммой состояний; 2) таблицей состояний. Это задание...

Построить программу машины Тьюринга, которая будет вычислять функцию
Необходимо построить программу машины Тьюринга, которая будет вычислять функцию f(x,y) = x + y - 1. Алфавит состоит из 1 и пустого символа. Буду благодарен тому, кто поможет с задачей.

Произвести умножение двух чисел. Каретка располагается над пустой ячейкой, которая разделяет данные массивы.
Произвести умножение двух чисел. Каретка располагается над пустой ячейкой, которая разделяет данные массивы.

Машина Тьюринга - как перевести символ 8сс в 2сс
Как перевести символ 8сс в 2сс, не совсем понимаю как тут это реализовать, ведь надо заменить 1 символ на 3

Построить грамматику порождающую язык
1. Построить грамматику порождающую язык L = {1^n 0^m 1^p | n+p>m; n, p, m>0}. 2. Для полученной грамматики построить диаграмму состояний конечного автомата. 3. Показать работу конечного автомата...

Машина Поста: если количество меток в массиве кратно 3, то стереть метки в данном массиве через одну, иначе массив стереть полностью
На ленте машины Поста находится n массивов меток, после последнего массива на расстоянии более 3-х пустых секций находится 1 метка. Массивы разделены 3-я пустыми ячейками. Количество меток в массивах...

Построить конечный автомат (КА–распознаватель) для распознания регулярного множества цепочек трехсимвольного алфавита
Построить конечный автомат (КА–распознаватель) для распознания регулярного множества цепочек трехсимвольного алфавита. Представить логику (стратегию) работы конечного автомата в виде диаграммы...

Машина Поста - напeчaтaть два числa в пoрядкe возрaстания
Здравствуйте. Помогите с задачей, кто может. Нa лентe дaны двa числa, рaзделенные oдним пробeлoм, справa через oдин прoбeл напeчaтaть эти числa в пoрядкe возрaстания. Нахождение наименьшего есть,...

Алгоритм Маркова: сложение чисел в унарном коде
представить в виде нормального алгоритма Маркова алгоритм сложения чисел в унитарном коде

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

Алгоритм Маркова. Удалить из слова все буквы «б», если их нечётное количество
Задание: Составьте нормальный алгорифм Маркова, выполняющий следующие преобразования: Удалить из слова все буквы "б", если их нечетное число. У меня были мысли добавить перед строкой, например,...

Построить приведенную грамматику, эквивалентную данной КС-грамматике
2.Построить приведенную грамматику, эквивалентную данной КС-грамматике: S → aAB | E A → dDA | Ɛ B → bE | f C → cAB | dSD | a D → eA E → fA | g Заранее спасибо!

Напишите регулярные выражения для следующих языков
а) множество всех цепочек из нулей и единиц, в которых нет подцепочки 101; б) множество всех цепочек, в которых поровну нулей и единиц и ни один их префикс не содержит нулей на два больше, чем...

Разветвление машин тьюринга
Задание такое: По МТ Т1, Т2, Т3 построить разветвление машин Т2 и Т3 под управлением машины Т1. Ввод машин через конфигурации. (Написать программу) _________________________________________ Изучив...

Реализовать алгоритм Маркова над алфавитом
Здравствуйте, помогите пожалуйста! Реализовать алгоритм над алфавитом A={x,y,"да","нет"} , который выдает «да», если в исходном слове четное количество y-ков, и «нет» в противном случае. Пытался...

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

Построить машину Тьюринга применимую ко всем словам x1, x2, …, xk в алфавите {a, b} и переводящую их в слово β
1. Построить машину Тьюринга применимую ко всем словам x1, x2, …, xk в алфавите {a, b}и переводящую их в слово β. 2. Проверить работу машины Тьюринга над задаваемыми самостоятельно двумя разными...