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

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

Выдать ответ a, если слова Q и R одинаковы, и пустое слово иначе (машина Тьюринга)
Машина Тьюринга. Пусть P имеет вид Q=R, где Q и R – любые слова из символов a и b. Выдать ответ a, если слова Q и R одинаковы, и пустое слово иначе. Правила форума: пункт 4.3. Создавайте темы с...

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

Построить ориентированный граф по регулярному выражению
Здравствуйте, уважаемые пользователи форума, возникла проблема с построением графа по регулярному выражению. (d+a^2)(ab)* Пункт 4.7. Правил форума. Как можно более полно описывайте суть проблемы...

Реализовать алгоритм в виде команд на Машине Тьюринга - удалить все вхождения символа b кроме последнего
Реализовать алгоритм в виде команд на Машине Тьюринга. А={a,b,c}. Если Р – непустое слово, то удалить все вхождения символа b кроме последнего, последнее заменить на !. Пример! (должно работать...

Машина Тьюринга: перевести ленту из конфигурации " число" 0... в конфигруацию " число" 0X0f(X)...
Добрый день! Есть задача: Приняты следующие правила кодирования чисел в алфавите {0; 1}: число 0 кодируется одним символом " 1" ; число N кодируется N+1 символом " 1" . Напишие...

Нормальный алгоритм Маркова - заменить в слове на "аа" последнее вхождение символа "а", если такое есть
Необходимо: Задать нормальный алгоритм в алфавите А = {a, b, *, #} схемой, заменяющей в слове на "аа" последнее вхождение символа "а", если такое есть, и не выполняющей никаких преобразований в...

Реализовать машину Тьюринга для нахождения истоков матрицы смежности ориентированного графа
Здравствуйте, помогите пожалуйста реализовать машину Тьюринга для нахождения истоков матрицы смежности ориентированного графа. на вход подается слово длины n^2 состоящее из 0 и 1, которое является...

Приписать слева к слову Р столько палочек, сколько всего символов входит в Р (машина Маркова)
2.27 Л=(a,b}. Приписать слева к слову Р столько палочек, сколько всего символов входит в Р (например: babb → | | | Правила форума: пункт 4.3. Создавайте темы с осмысленными и понятными названиями -...

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

Считая слово Р записью числа n в единичной системе, получить в этой же системе число 2^n (машина Тюринга)
8 1.36 А=(13. Считая слово Р записью числа п в единичной системе, 9 1.37 А=(13. Пусть слово Р является записью числа 2° (т-0, 1, 2,.) в получить в этой же системе число 2". единичной системе....

Нормальный алгоритм Маркова - добавить символ в конец слова
Задание: Задать нормальный алгоритм в алфавите А = {a, b, *} схемой, приписывающей символ "a" к концу слова. Пункт 4.7. Правил форума. Как можно более полно описывайте суть проблемы или вопроса,...

Нужно нарисовать данную диаграмму jk триггера
Ребят, пожалуйста, объясните как решить данное задание Правила форума: пункт 4.7. Как можно более полно описывайте суть проблемы или вопроса, что было сделано для ее решения и какие результаты...

Получить в этой же системе число пИ (машина Тьюринга)
1.37 А=(1). Пусть слово Р является записью числа 2° (т=0, 1, 2,..) в единичной системе. Получить в этой же системе число пИ. МАШИНА ТЬЮРИНГА ЕСЛИ НЕ СЛОЖНО ТО В ВИДЕ ФОТОГРАФИИ Правила форума: пункт...

Нормальный алгоритм Маркова - удалить из непустого слова его первый символ, при этом не меняющей пустое слово
Задать нормальный алгоритм в алфавите А = {a, b, *} схемой, удаляющей из непустого слова его первый символ, при этом не меняющей пустое слово. Пункт 4.7. Правил форума. Как можно более полно...

Определить, является ли слово Р идентификатором (непустым словом, начинающимся с буквы) (Машина Тьюринга)
1.9 A={a,b,0,1}. Определить, является ли слово Р идентификатором (непустым словом, начинающимся с буквы). Ответ: слово а (да) или пустое слово (нет). МАШИНА ТЬЮРИНГА ЕСЛИ НЕСЛОЖНО ЕЩЕ В ВИДЕО...

Определить, является Р палиндромом (перевёртышем, симметричным словом) (Машина Тьюринга)
9 1.23 А= (a.b). Определить, является Р палиндромом (перевёртышем, симметричным словом) или нет. Ответ: а (да) или пустое слово. МАШИНА ТЬЮРИНГА ЕСЛИ НЕ СЛОЖНО В ВИДЕО ФОТОГРАФИИ Правила форума:...

Разработать машину Тьюринга для функции
Последовательность неотрицательных целых чисел (x1, x2, ...) задается на ленте машины Тьюринга как слово 01x1 , где 1x обозначает слово, состоящее из x единиц (остальные клетки ленты ...

Сделать неоднозначную грамматику однозначной
Задана грамматика, она не однозначная, по ней построить однозначную. Потом этот алгоритм алгоритм я должен буду реализовать на C++ или на чём-нибудь ещё, пока что просто хотел бы узнать сам алгоритм,...

Нормальные алгорифмы Маркова: произвольное слово уменьшить наполовину с начала
Нужно разработать нормальный алгоритм Маркова для задачи на эмуляторе Маркова. Задача: произвольное слово из A = {a, b, c, d} уменьшить на половину с начала. Например, abccb → ccb, cb или abc →...

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

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

Машина Тьюринга, умножающая число на 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. Поразрядно сложить два двоичных числа, разделенных знаком +.

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

Дана грамматика. Построить вывод заданной цепочки и дерево вывода.
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...

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

Машина Тьюринга, оставить в 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ух чисел (Левое всегда больше правого) Каретка вначале стоит на правой крайней позиции вычитаемого числа.

Доказать, что функция примитивно рекурсивна
Здравствуйте,нужна помощь: Доказать, что функция 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, а что делать...

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

Машине Поста: умножение унарного числа на 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) Построить дерево вывода (левосторонний и правосторонний вывод)...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сложение двух чисел в двоичной СС в Машине Тьюринга
Помогите решить задачу для Машины Тьюринга, адекватное решение не гуглится(( Задача: Сложение двух чисел в двоичной системе счисления(каждое число имеет не более 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 определить язык,который порождает грамматика Не понимаю как решать,...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Создать машину Тьюринга, которая прибавляет 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 больше, чем символов 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 минут Есть...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Доказательство нерегулярности языка
Приветствую. Есть 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} =...

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

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

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

Построить нормальный алгоритм Маркова, который в любом слове из алфавита А удваивал все буквы, стоящие на четных местах
Построить нормальный алгоритм Маркова, который бы в любом слове из алфавита А={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} удваивал все буквы, стоящие на четных местах в исходном слове.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Закодировать алфавит методом Шеннона-Фано и Хаффмана
Нужно закодировать алфавит 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 Выполнил задание, но не...

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

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

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

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

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

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

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

Построение автомата с магазинной памятью по кс грамматике. Определить входную строку
Здравствуйте! Дана контекстно-свободная грамматика: 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).

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

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

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

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

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

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

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

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

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

Машины Тьюринга. Является ли Р словом 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 ...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Построить конечный автомат по заданной регулярной грамматике
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) Построить конечный автомат по заданной регулярной...

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

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

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

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

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

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

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

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

Построить контекстно-свободную грамматику, порождающую язык
Построить кс грамматику пораждающею язык: 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...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Построить граф автомата Мили
Построить граф автомата Мили, реализующего полученный автоматный оператор. Х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 ...

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

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

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

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

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

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

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

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

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

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

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

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

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

Построить машину Тьюринга, вычисляющую следующие функции
Помогите, пожалуйста! Требуется построить машину Тьюринга, вычисляющую следующие функции: 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Как построить граф автомата Мили по уже построенному графу автомата Мура
Подскажите как построить граф автомата Мили по уже построенному графу автомата Мура А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}, состоящий из множества слов, в которых число нулей делится на четыре, а число единиц нечетно.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Выполнить редукцию выражения лямбда-исчисление
Выплнить редукцию в аппликативном порядке. До форм 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) ...

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

Выяснить, применима ли машина Тьюринга 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} Есть, предположение, но...

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

Построить язык, порожденный такой грамматикой. Определить тип грамматики
Дано грамматику 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 - начальный символ. Построить язык, порожденный...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Доказать примитивную рекурсивность 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.

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

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

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

МНР
целая часть корня из (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 в степени звездочка? Очень прошу.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Построить машину Тьюринга для преобразования слова Р в слово 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...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Определить тип грамматики и язык, который порождает грамматика
Дана следующая грамматика: 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} ...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вычислить функцию, полученную операцией примитивной рекурсии
Функция 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. Пример выполнения задачи приложен

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Построить оптимальные коды по методу Хаффмана
Для заданных распределений вероятностей появления букв построить оптимальные коды по методу Хаффмана. 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+2 . 5-2. , и что с этим делать...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Построить грамматику порождающую язык
1. Построить грамматику порождающую язык L = {1^n 0^m 1^p | n+p>m; n, p, m>0}. 2. Для полученной грамматики построить диаграмму состояний конечного автомата. 3. Показать работу конечного автомата...

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

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

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

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

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

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

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

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

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

Построить приведенную грамматику, эквивалентную данной КС-грамматике
2.Построить приведенную грамматику, эквивалентную данной КС-грамматике: S → aAB | E A → dDA | Ɛ B → bE | f C → cAB | dSD | a D → eA E → fA | g Заранее спасибо!

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

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

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

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

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

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

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

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

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

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

Алгоритм Маркова. Удалить из слова все буквы «б», если их нечётное количество
Задание: Составьте нормальный алгорифм Маркова, выполняющий следующие преобразования: Удалить из слова все буквы "б", если их нечетное число. У меня были мысли добавить перед строкой, например,...

Реализовать алгоритм Маркова над алфавитом
Здравствуйте, помогите пожалуйста! Реализовать алгоритм над алфавитом A={x,y,"да","нет"} , который выдает «да», если в исходном слове четное количество y-ков, и «нет» в противном случае. Пытался...

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

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

Алгоритм Маркова: сложение чисел в унарном коде
представить в виде нормального алгоритма Маркова алгоритм сложения чисел в унитарном коде

Машина Поста - нап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стания. Нахождение наименьшего есть,...

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

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

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

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

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

Машина Тьюринга - как перевести символ 8сс в 2сс
Как перевести символ 8сс в 2сс, не совсем понимаю как тут это реализовать, ведь надо заменить 1 символ на 3

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

Доказать вычислимость функции по Тьюрингу.
Здравствуйте. Знающие люди, помогите-выручайте. У меня задание-Доказать вычислимость функции по Тьюрингу f(x)= \sqrt{x} Построить машину Тьюринга, правильно вычисляющую эту функцию. (еще...

Для данного множества найти кодовое расстояние
Помогите,пожалуйста,справиться с этим заданием: Для данного множества С найти кодовое расстояние: С= {00001, 11111, 10100, 01010) Определить а)число ошибок,которые код С обнаруживает б)число...

Организация ввода грамматики и проверка ее на принадлежность к классу КС-грамматик
Разработать программное средство, автоматизирующее процесс эквива- лентного преобразования КС-грамматик. Программное средство должно вы- полнять следующие функции: 1) организация ввода...

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