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

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

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

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

Построить кс-грамматику
Добрый вечер. Помогите, пожалуйста, построить кс-грамматику. Не могу понять, как это сделать Заранее спасибо!

НАМ. Как мне удалить именно третий символ в слове
Есть слово A = {a, b, c d}. Как мне удалить именно третий символ .Очень буду благодарна за помощь

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

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

Найти короткую, допустимую и отвергающую цепочку
Подскажите правильно ли я делаю задание. Автомат: __0 1 A|C D|0 B|A A|0 C|B D|0 D|E C|0 E|B F|0 F|F C|1 а) найти самую короткую цепочку, распознаваемую автоматом: A->D->E->F

К какому типу относится заданная грамматика?
Добрый день. Помогите пожалуйста с этим заданием. Буду сильно благодарен. Все никак не могу разобраться

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

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

Построить в алфавите {0, 1} машину Тьюринга, переводящую конфигурацию к1 в конфигурацию к0
Построить машину тьюринга, переводящую конфигурацию к1 в конфигурацию к0 К1=0^(n+3)q1 0^(n+2)0 K0=0^n q0^3 0^n 0 (n>=1) Помогите пожалуйста построить машину. Правила форума, пункт 4.3....

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

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

Машина Тьюринга - в непустом слове поменять местами его первый и последний символы
В непустом слове P поменять местами его первый и последние символы. А = {a,b} Очень прошу Вашей помощи

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

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

Построить в алфавите {0,1} машину Тюринга, переводящую конфигурацию K1 в кофигурацию K0
k1=0q1^(n+1)^(3)0^(n+1)0 k0=0q0^(n)0^(n)0(n>=1) Начальное состояние – q1, конечное состояние – q0. Положение управляющей головки над ячейкой справа от указанного в конфигурации состояния (начального...

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

Считая непустое слово P записью числа в троичной системе счисления, получить запись этого числа в единичной системе
Машина Тьюринга Пример, входное слово 120(троичная система), и при выходе должно получиться 15(десятичная записанная единицами) A={0, 1, 2}. Правила форума, пункт 4.7. Как можно более полно...

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

Как построить машину Тьюринга (МТ) с объяснениями, переводящую
1^k 0^m 1^n -> 1^n 0^k 1^n

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

Машина Тьюринга. Как поменять местами количество единиц и нулей?
Всем привет, я не очень понимаю как сделать эту задачу. Имеется массив нулей и массив единиц, длины массивов заданы n и k соответственно. Мне нужно поменять количество нулей и количество единиц...

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

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

Детерминированный конечный автомат
Здравствуйте, выручайте пожалуйста! Попалась такая задача: G=(N,E,P,S) N={S,A,B,C} E={0,1} P={S->0|0A|1B, A->0C, B->1S|1, C->0A|0S|0} не могу толком разобраться в грамматике P={...}, в "этих ваших...

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

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

Нормальный алгоритм Маркова. Нужен алгоритм вычитания из слова двойки
Добрый день, подскажите пожалуйста реализацию алгоритма вычитания из слова двойки пример 530 - 2 = 52b что равно 884 - 2 = 882 алфавит = 1.2.3.4.5.6.7.8.9.0.a.b.c слово целое число больше или...

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

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

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

Коды, автоматы
Добрый день уважаемые форумчане, прошу о помощи с решением задания. Безумно буду благодарен за развёрнутый ответ;

Поменять местами первый и второй символы слова (Машина Тьюринга)
Можете помочь решить задачу с помощью машины Тьюринга? Дано слово в алфавите {a, b}. Поменять местами первый и второй символы слова. Каретка стоит на первом слева не пустом символе.

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

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

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

Построение и анализ алгоритмов. Построить таблицу и блок-схему алгоритма, реализующего вычитание 1 из двоичного числа
Помогите, пожалуйста, построить таблицу и блок-схему алгоритма, реализующего вычитание 1 из двоичного числа. Пример ряда последовательных двоичных чисел: 0000, 0001, 0011, 0011, 0100, 0101, 0110,...

Алгоритм Маркова. Переобразование чисел
С помощью НАМа преобразовать единичные числа в двоичные

Нормальные алгоритмы Маркова. Инвертировать число
Добрый день. Я сделал реверс двоичного числа, а с троичным не могу додуматься. Можете помочь допилить алгоритм либо написать другой? #10 -> 0#1 #11 -> 1#1 #00 -> 0#0 #01 -> 1#0 #0 -> <*0 ...

Построить конечный автомат
Задание: построить конечный автомат с заданным входным алфавитом, который допускает след. множество: входные цепочки, содержащие подцепочку "IEEE0EE", если входной алфавит {0,I,E}. 0 I E A ...

Составление таблицы машины Тьюринга для вычисления високосности года
Задание таково: Дан номер года. Определить, високосный он или нет. Как это реализовать на машине Тьюринга? Это понятно, как сделать на любом языке программирования: если год не делится на 4 - он...

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

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

Реализовать автомат Мура для разбора и преобразования циклов for -> while (Pascal)
Здравствуйте. Не очень понимаю, что от меня здесь требуется: Требуется реализовать автомат указанного типа для разбора и преобразования циклов, написанных на языке, соответствующих требованию...

Машина тьюринга
1. A={a,b,c}. Оставить в слове P только первый символ (пустое слово не менять). 2. См. скрин (сделать только пункт в) Пожалуйста, помогите!!! Запишите, пожалуйста в этом формате (см. скрин)

Машина поста, вычислить разность массивов
Найти разность двух натуральных чисел m и n. Причем m=>n. p - Количество пустых секций.

Определить, принадлежат ли цепочки к языку, порождаемому данной грамматикой
Дана грамматика S -> аScВ|A|b A-> cA|c B -> d|A Определить, принадлежат ли цепочки abcd, acccbd, acccbcc, acd, acc к языку, порождаемому данной грамматикой.

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

Машина Тьюринга. Заменить в P каждое вхождение a на bb. Составить протокол
A={a,b}. Заменить в P каждое вхождение a на bb Нужно составить протокол Пример: q0 ai→q1 ai П q1 ai→q1 ai П q1→q2 Л q2 2→q3 2Л q3 ai→q3 ai Л q3→qk П

Разработать конечный автомат, реализующий поведение автомобилиста на перекрестке со светофором
Разработать конечный автомат, реализующий поведение автомобилиста на перекрестке со светофором. Возможный входной алфавит: красный, желтый, зеленый, объезд, пробка. Возможные варианты поведения...

Нормальные алгоритмы Маркова. A={+,1} Пусть Р – непустое слово 111+11+1 .Найти значение суммы
Доброго времени суток:) Помогите решить, пожалуйста , вот такую задачку: A={+,1} Пусть Р – непустое слово 111+11+1 .Найти значение суммы.

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

Машина Тьюринга. Построить МТ, правильно вычисляющую функцию
Построить МТ, правильно вычислчющую функцию: f(x,y,z)=z mod 2+2.

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

Составить грамматику
Добрый день, голова горит, спал мало, нужно соорудить грамматику, которая порождает 2^n пар ab Последнее, к чему я пришел, это S->ab S->FF F->AA A->S F->S Этот вариант явно нерабочий из-за...

Дан алфавит A = {a, b, c,1,2}. Написать 1, если входное слово P чётной длины, иначе написать 2
Дан алфавит A = {a, b, c,1,2}. Написать 1, если входное слово P чётной длины, иначе написать 2. Помогите пожалуйста, я тупая

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

Теория алгоритмов. Нормальные алгоритмы Маркова
Нормальный алгоритм Маркова в алфавите А = {1,*,a,b} задан следующей системой ориентированных подстановок: 1) *11 -> a*1 2) *1 -> a 3) 1a -> a1b 4) ba -> ab 5) b1 -> 1b 6) a1 -> a...

Построить конечный автомат, который распознает заданный регулярный язык
Здравствуйте, задание такое: построить конечный автомат, который распознает заданный регулярный язык L = (ab + bc + bb)* Я сделал так, но это не совсем правильно, а ошибки найти я не могу....

Алгоритм Маркова. Вычитание десятичных чисел
Здравствуйте. Подскажите, пожалуйста, как написать алгоритм Маркова для вычитания десятичных чисел? И, если можно, объяснить: что делается, зачем и почему.

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

Реализовать автомат Мура для разбора и преобразования циклов while (…) do {…} (язык с++)
Здравствуйте, подскажите пожалуйста у меня аналогичная тема только у меня входной цикл while (…) do {…} язык с++ и для начала я даже не могу понять что это за while (…) do {…}, почему while и do...

Машина Тьюринга. Умножить два числа, заданных последовательностями единиц
Умножить два числа, заданных последовательностями единиц: на вход вида 1...1 1...1 (m единиц, пробел, n единиц) выдать mn единиц (например, 111 1111 7→ 111111111111)....

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

Построить машину Тьюринга, переводящую 1^k 0^m 1^n в 1^m 0^k 1^m
Построить машину Тьюринга, переводящуюю 1^k 0^m 1^n в 1^m 0^k 1^m Добавлено через 7 минут на ленте есть k единиц, m нулей и n единиц (k,m,n-количество). И надо сделать, чтобы было m единиц, k...

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

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

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

Написать НАМ, который уменьшает на единицу число, записанное в троичной системе счисления
Напишите НАМ, который уменьшает на единицу число, записанное в троичной системе счисления. Используйте специальные символы (например, # и *) для обозначения начала числа и того разряда, который нужно...

Машина Тьюринга: выбрать больший из наборов единиц, а меньший стереть
Среда - машина тьюринга к поляков. Условия - не больше 2 дополнительных символов алфавита (алфавит 1*AB_) Само задание: На ленте машины Тьюринга записаны два набора единиц, разделенные звездочкой....

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

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

Машина Тьюринга. Реализовать вычисление предиката X<Y в унарном коде сохранением (восстановлением) исходных данных
Доброго времени суток не как не могу решить данную задачу хоть она должна быть простая. Пытался делать несколько раз но не получилось. Условие: Реализовать вычисление предиката X<Y в унарном коде...

Построить МП-автомат, распознающий заданный КВ-язык
L=({(ab)}^{2n+1}{c}^{n}:n\geq 0)\bigcup ({a}^{n}{c}^{3m-1}:n\geq 1, m\geq 1) Кто может, помогите, пожалуйста.

Построить нормальный алгоритм Маркова. Получить результат поразрядной конъюнкции этих чисел
Входное слово НАМ представляет собой два двоичных числа без знака, разделенных символом «*». Получить результат поразрядной конъюнкции этих чисел. Ни во входных числах, ни в результате незначащих...

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

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

Для заданного языка, построить распознающий его ДКА
Для заданного языка, построить распознающий его ДКА \left(\sum = a, b, c )\right \alpha \in L тогда и только тогда, когда слово \alpha имеет длину не более 8 и содержит одинаковое число букв a и...

Машина Тьюринга. Какую команду вставить в таблицу, чтобы программа остановилась
Доброго дня интернет. У меня загвоздка в программе Алго2000: я не знаю, какую команду вставить в таблицу, чтобы программа остановилась. В инете писали про "_." или ".", но они не работают, программа...

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

Допустимо ли строить такой автомат (ДКА) для языка, не содержащего подстроку 110?
Допустимо ли строить такой автомат (ДКА) для языка, не содержащего подстроку 110? И если нет, то почему? (Полагаю, как-то связано с тем, что автомат умирает, но тогда как избавиться от момента, когда...

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

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

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

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

Составить порождающую грамматику
Помогите пожалуйста) Вот задание: Построить порождающую грамматику L = { αcβcγc | α, β, γ - любые цепочки из a и b}

Алгорифм Маркова. Найти максимальную длину среди этих слов и записать их с одинаковыми длинами
Дано 2 слова, с разными длинами(A={a,b}). Найти максимальную длину среди этих слов и записать их с одинаковыми длинами. Пример, aaa*bbbb => aaaa*bbbb Подскажите хотя бы алгоритм пожалуйста

Устранение левой рекурсии
Требуется помощь в устранении левой рекурсии S → S1 | A0 A → A1 | 0

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

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

Нормальные алгоритмы Маркова, реализация операции умножения
Задать нормальный алгоритм Маркова, реализующий операцию умножения.

Построить МП-автомат, распознающий КВ-язык
Добрый вечер. Задание : Построить мп-автомат, который распознает заданный КВ-язык L = {w є {a,b}*: |w| ₐ = 2|w|b}. Я сделал так, но препод сказал, что это неправильно. Помогите, пожалуйста, понять,...

Построить МТ, которая принимает лишь те слова, в которых первый символ встречается более одного раза
Помогите, пожалуйста, построить МТ, которая принимает лишь те слова (А={0, 1}), в которых первый символ встречается более одного раз. Например, принимаются слова 110, 1010, 01000, но отклоняются...

Что это за элемент (программа Proteus)?
Доброго времени суток, не могу никак найти данный элемент(КН) Произведите исследование триггера RS на элементах 2И-НЕ, записывая в него информацию (информация записывается при дополнительном...

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

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

Построить недетерминированный конечный автомат
Здравствуйте, нужна помощь. Построение недетерминированного конечного автомата читающий выражение: Ф=(a*c)*Ua(ab)*

Построить Машину Тьюринга для реализации алгоритма вычисления функции f(x) = 2х
Построить МТ для реализации алгоритма вычисления функции f(x) = 2х в алфавите {1, \lambda}. Число х – натуральное или 0 – представлено в виде х+1 единицы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Машина поста: разность 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, а что делать...

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

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

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

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

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

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

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

Преобразовать в нормальную форму Хомского КС-грамматики.
Преобразовать в нормальную форму Хомского КС-грамматики 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...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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