Форум программистов, компьютерный форум, киберфорум

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


КиберФорум - форум программистов и системных администраторов. Бесплатная помощь в решении задач по программированию, математике, физике и другим наукам, решение проблем с компьютером, операционными системами.
Войти
Регистрация
Восстановить пароль

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

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

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

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

Грамматика. Только начал изучать формальные языки, как долг в универе. Можете подсказать, это имеет смысл, правильно ли?
Здравствуйте. Я только начал изучать формальные языки, как долг в универе. У меня имеется язык L(G)={c^2n d^n | n>0} S -> CD C -> cC | λ D -> dD | λ Я сделал такую грамматику:...

Машина Тьюринга в четверках: побитовое перемножение двух двоичных чисед
Машина Тьюринга в четверках Помогите! Очень срочно надо Программа арбитров перемножает два двоичных числа. Почему она не работает просто на 0 и 1? (на более сложные числа работает) 00, ,!,01...

Машина Тьюринга. Удвоить исходное слово (например, abb → abbabb)
A = {a,b}. Начальная конфигурация – произвольное слово из знаков алфавита; обозревается произвольный знак. удвоить исходное слово (например, abb → abbabb).

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

Нормальный алгоритм Маркова.Найти количество символов в строке
Заменить непустую строку из символов a,b и c на количество символов в ней (в строке максимум 3 символа) Пример ввода: aa Пример вывода: 2 Я придумал только решение с перебором, какие еще...

Разработать программу для машины Тьюринга, добавляющую букву «с» после каждой буквы «о»
Добрый вечер, суть задания: Алфавит машины Тьюринга: {а, б, в, г, д, е, ѐ, ж, з, и, й, к, л, м, н, о, п, р, с, т, у, ф, х, ц, ч, ш, щ, ъ, ы, ь, э, ю, я, ∅}. На ленте записано слово. Разработать...

Машина Тьюринга. В непустом слове P поменять местами его первый и последний символы
A={a,b}. В непустом слове P поменять местами его первый и последний символы. Нужно решить с помощью данного алгоритма Заранее спасибо!

Построить автомат с магазинной памятью для распознавания и трансляции выражений (LL(1) транслирующие грамматики)
Для следующей транслирующей грамматики: На вход подаются логические выражения со скобками. Операнды: 0,1. Операции: | (дизъюнкция), & (конъюнкция), ! (унарное отрицание). Приоритет операций: !, &,...

Построить машину Тьюринга, вычисляющую числовую функцию f(x1,x2,.,xn)
Построить машину Тьюринга, вычисляющую числовую функцию f(x,y) = {y - x, если x<=y; 0, если x > y} Команды для полученной машины Тьюринга записать в виде таблицы Правила форума, пункт 4.7. Как...

Найти регулярное выражение для дополнения языка
Приветствую, есть некая задача: Найти регулярное выражение для дополнения языка (a + b)*(aab + abaa + abb)(a + b)* над алфавитом {a, b}. Помогите, её, пожалуйста решить, не могу никак понять,...

Нормальный алгоритм Маркова. Считая непустое слово Р записью троичного числа, увеличить это число на 1
A=(0,1,2) Считая непустое слово Р записью троичного числа, увеличить это число на 1 Добавлено через 28 секунд Пожалуйста, очень нужно Правила форума, пункт 4.7. Как можно более полно описывайте...

Составить алгоритм вычисления поразрядной дизъюнкции исходных чисел (алгоритм Маркова, дизъюнкция)
Кто-то может помочь с решение алгоритмов Маркова... Вот задание: Входное слово представляет собой два двоичных числа без знака, разделенные знаком "|". Составить алгоритм вычисления поразрядной...

Напишите регулярное выражение для следующего языка
Напишите регулярное выражение для следующего языка : множество всех цепочек из нулей и единиц, в которых число нулей делится на пять, а количество единиц чётно. {(11\cup00000)}^{*}

Побитовое произведение на Машине Тьюрига в 4-ках
Привет всем! Недавно мне дали задание: реализовать алгоритм логического произведения (&& в Си) двух двоичных чисел на Машине Тьюринга в нормированном виде (input output) максимальная разрядность...

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

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

Напишите регулярное выражение для следующего языка - 1
Множество цепочек из нуля и единиц, содержащих не более одной пары последовательных единиц. Вот что получилось: {(01) }^{*}+{(10)}^{*}+11+{(01)}^{*}+{(10)}^{*} нужна реакция Переделал работу:{0...

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

Найти язык конечного автомата (кратко)
товарищи, начал изучать теорию автоматов - возник вопрос такого характера. Я составил для автомата систему уравнений: \begin{align*}x_0 &= ax_1 + bx_2 \\x_1 &= bx_0 + ax_1 \\x_2 &= ax_0 + bx_1 +...

Написать программу для машины Тьюринга, которая реализует следующую функцию
Здравствуйте! Помогите пожалуйста! Алфавит = {0, 1, а0} Напишите программу Машины Тьюринга, которая реализует следующую функцию: f(x)=х+2 (Число записано на ленте в двоичной системе...

Вычитание в троичной системе счисления в нормальных алгоритмах Маркова
Здравствуйте, у меня возникла проблема с вычитанием в нормальных алгоритмах Маркова. Когда числа состоят из 1 разряда, проблем не возникает, но когда идет вычитание например 10-1, у меня выводит 01,...

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

Построить алгоритм Маркова, вычисляющий функцию
Ребят, выручайте, нужно построить алгоритм Маркова, вычисляющий функцию. x, y, z подаются как несколько единиц, а в начале входной строки всегда стоит #, то есть, например, если x=3, y=4, z=2, то...

Машина Тьюринга. Удалить средний символ, если слово с нечетным количеством букв, иначе оставить без изменений
Задан алфавит A = {a, b, c}. Удалить средний символ, если слово с нечетным количества букв, иначе оставить слово без изменений. Например : aaaacaaaa -> aaaaaaaa или abcccab -> abccab (слово не...

Преобразовать автомат Мили в эквивалентный ему автомат Мура
Преобразовать частично заданный автомат Мили, представленный ниже в теоретико-множественной форме, в эквивалентный ему автомат Мура. Я построил совмещённую таблица автомата Мили. Нужно создать...

Решить задачи - тренажер Маркова
Составить абстрактную модель алгоритма в виде нормального алгоритма Маркова над алфавитом А. 1. Уменьшить на 4 положительное целое число в системе счисления А (0,1,2,3,4,5,6,7,8, 9) 2. Задан...

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

Составить программу для машины Тьюринга, оставляющую в непустом слове первые 5 символов
Построить машину Тьюринга с внешним алфавитом A, которая выполняет заданные действия.В начальный момент на ленте записано слово P (конечная последовательность символов внешнего алфавита А, слово P...

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

Построить НАМ. Заменить слово P на пустое слово, т.е. удалить из P все символы
НАМ: A={a,b,c}. Заменить слово P на пустое слово, т.е. удалить из P все символы. Правила форума, пункт 4.7. Как можно более полно описывайте суть проблемы или вопроса, что было сделано для ее...

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

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

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

Задача с Машиной Тьюринга
А {a, b}. Если в слово Р входит больше символов а, чем символов b, то в качестве ответа вывести слово из 1 символа а, если их количество равное, то ответ - пустое слово, иначе выдать 1 символ b

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

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

Нормальный алгоритм Макарова
Входное слово НАМ представляет собой целое троичное число m со знаком, |m|≥4. Получить слово (m-4). Ни входное, ни выходное число не содержит незначащих нулей. Правила форума, пункт 4.3....

Построить регулярное выражение
Множество цепочек, состоящих из нулей и единиц, в которых число нулей кратно пяти. Ответ мой:{((\varepsilon +1)0(\varepsilon +1)0(\varepsilon +1)0(\varepsilon +1)0(\varepsilon +1)0(\varepsilon...

Эквивалентные преобразования контекстно-свободных грамматик
Дана контекстно-свободная грамматика: G=({S, R, T, X, Y}, {a, b, p, g, y}, P, S), где P: 1)S -> R | T; 2) R -> pX | paR | paT| ε; 3) T -> Tg | g; 4) X->aXb; 5) Y -> aYa | y 1. Проверить...

Как грамотно преобразовать выражение с x2, ведь там итерация от x1?
3D Homer, все, дошло, ура! Утро вечера мудренее. Спасибо за пояснение!!! 3D Homer, еще раз здравствуйте! Возник вопрос относительно операции итерации и дальнейшего преобразования выражения. Я...

Построить машину с неограниченными регистрами
Построить машину с неограниченными регистрами для функции х/(у+1) Правила форума, пункт 4.7. Как можно более полно описывайте суть проблемы или вопроса, что было сделано для ее решения и какие...

Обобщенный алгоритм вычисления конгруэнтного замыкания. Кто-нибудь сталкивался с подобными алгоритмами?
Разбираюсь с минимизацией конечных автоматов. Столкнулся с вот таким алгоритмом: Обобщенный алгоритм вычисления конгруэнтного замыкания УАКЗ (A,R) Начало peding := A; / A - множество...

Составить конечный автомат
Добрый вечер, подскажите, правильно ли я составила конечный автомат? Условие: Множество слов, в которых за подстрокой аbb следует подстрока сс Вот мой составленный вариант:...

Как ввести в машину Тьюринга задание?
Есть ПО, эмулятор машины Тьюринга и есть задание, Но задание записано "странно" и не понятно, как минимум для меня. Буду очень благодарен если объясните что это все значит и как вбить в машину A =...

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

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

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

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

Машина Тьюринга. Определить число ячеек на ленте
Определить необходимую память (число ячеек на ленте) для машины Тьюринга, вычисляющую функцию. X + Y

Построить грамматику G, порождающую язык L
Всем здравствуйте, столкнулась с интересным заданием: Построить грамматику G, порождающую язык L={a^nb^m : n, m ∈ N; n ≠ m}. Единственным примерным решением я нашла такую грамматику с правилами: P...

Построить машину Тьюринга для языка, состоящего из одинакового количества символов 0 и 1
Помогите, пожалуйста, построить машину Тьюринга для языка, состоящего из одинакового количества символов 0 и 1.:-| Правила форума, пункт 4.3. Создавайте темы с осмысленными и понятными названиями -...

Сортировка трёхбуквунного алфавита в Машине Тьюринга
Помогите пожалуйста выполнить задачу по сортировке в МТ. Нужно выполнить её в Тренажёре Машины Тьюринга. Дан алфавит A = {h, a, l}. P – непустое слово. Сконструировать МТ, которая упорядочивала...

Построить КС-грамматику языка
Здравствуйте, помогите решить задачу. Как построить дерево я вроде как поняла, но вот КС-грамматика пока не получается Постройте КС-грамматику языка, для заданной программы: int* a = new int;...

Построить конечный автомат распознаватель для автоматного языка LV={weeq, qwe}
Дан словарь V={w, e, q}, постройте конечный автомат распознаватель для автоматного языка LV={weeq, qwe}. Правила форума, пункт 4.3. Создавайте темы с осмысленными и понятными названиями - это...

Регулярная грамматика
1) выполнить проверку заданной грамматики на принадлежность к классу регулярных грамматик; 2) построить по заданной регулярной грамматике конечный автомат, 3) преобразовать недетерминированный...

Дан словарь V. Доказать, что язык над этим словарём L является автоматным языком
Дан словарь V={0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Докажите, что язык над этим словарём L={числа начинающиеся не с девятки} является автоматным языком. Правила форума, пункт 4.3. Создавайте темы с...

Является ли язык L автоматным языком?
Является ли язык L={все числа в которых количество троек в три раза больше чем количество девяток} над словарем V={0, 1, 2, 3, 4, 5, 6, 7, 8, 9} автоматным? Правила форума, пункт 4.3. Создавайте...

Построить Машину Тьюринга, переводящую 1^k 0^m 1^n в 1^2 0^n 1^m
Помогите пожалуйста! A - внешний алфавит. У нас будет A = E = {0, 1}. На ленте влево и вправо в бесконечность уходят нули, заполняющие отдельные ячейки. Дано задание: Построить Машину Тьюринга...

Построить машину Тьюринга для вычисления арифметической функции
Построить машину Тьюринга для вычисления арифметической функции f(x,y)={y, y<x; x+4, y≥x . Внешний алфавит состоит только из 0 и 1, 0 – пустой символ. Пояснения по построению программы для МТ...

Доказать вычислимость функции по Тьюрингу
Как построить граф?

Нормальный алгоритм Маркова. Разработать программу на с++, реализующую разработанный НАМ
Входное слово НАМ представляет собой последовательность символов в алфавите {x,y,z}. Если слово нечетной длины, найти и удалить центральный символ. Если слово четной длины, оставить его без...

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

Создать машину Тьюринга. Классифицировать ее в виде конечного автомата. Вычислить выражение (a+b)/c
Создать машину Тьюринга.Для созданной машины классифицировать ее в виде конечного автомата Вычислить выражение (a+b)/c. Правила форума: 4.2. Если собираетесь создать новую тему, определитесь с...

Построить ДКА допускающий язык L
4)Построить ДКА допускающий язык L={w| w не содержит подцепочки 0000 и 011}Правила форума, пункт 4.7. Как можно более полно описывайте суть проблемы или вопроса, что было сделано для ее решения и...

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

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

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

Требуется совет по реализации МТ - функция вычитания
Здравствуйте, товарищи математики! Только начал изучать теорию алгоритмов. Надо реализовать вычитание в унарной системе, т.е *111* является 3, *11111* является 5. Звезда означает начало и конец слова...

Грамматика. Классификация Хомского
1) составить несколько грамматик (по возможности разных типов), порождающих формальный язык, заданный в соответствии с вариантом; 2) Определить тип формальных грамматик и языка по классификации...

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

Построить диаграмму Мура для конечного автомата
3) Построить диаграмму Мурра для конечного автомата реализующего функцию 2n-4m+3. Правила форума, пункт 4.7. Как можно более полно описывайте суть проблемы или вопроса, что было сделано для ее...

Построить - НКА допускающий язык L
5)Построить - НКА допускающий язык L={w| w содержит без пересечения две различные подцепочки из множества {111, 0011, 1100}} Правила форума, пункт 4.7. Как можно более полно описывайте суть...

Найти канонические уравнения в базисе, реализующий конечный автомат
2)Найти канонические уравнения в базисе B = {^, ^(перевернутая), знак отрицания}, реализующий конечный автомат реализующий функцию n+m-2 Правила форума, пункт 4.7. Как можно более полно описывайте...

Синтезировать автомат c одним входом и одним выходом. В качестве ответа необходима схема готового решения
Синтезировать автомат c одним входом и одним выходом. На вход поступает произвольная последовательность символов и 1. Автомат анализирует входные символы группами по три символа. Выходной сигнал...

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

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

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

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

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

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

Машина Тьюринга. Удалить из массива все элементы 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, а что делать...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Закодировать алфавит методом Шеннона-Фано и Хаффмана
Нужно закодировать алфавит 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,d,e,f,g,h,i,j,k,l,m,n,o,p,r,s,t,u,v,w,x,y,z} удваивал все буквы, стоящие на четных местах в исходном слове.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru