Вопросы по теме 'computation-theory'
Почему это недействительная машина Тьюринга?
Во время проверки экзамена у меня возникли проблемы с ответом на следующий вопрос из книги «Введение в теорию вычислений» Сипсера. К сожалению, в книге нет ответа на этот вопрос.
Объясните, почему следующее не является законной машиной Тьюринга....
6024 просмотров
schedule
20.05.2024
Докажите, что множество регулярных языков является правильным подмножеством множества контекстно-свободных языков.
Я освежал (не домашнее задание) некоторую теорию вычислений и столкнулся с этой проблемой:
Как вы можете доказать, что множество обычных языков является правильным подмножеством множества контекстно-свободных языков.
Теперь я знаю, что язык...
2914 просмотров
schedule
13.10.2022
Можно ли построить машину Тьюринга, используя только два ленточных символа?
Машина Тьюринга M, содержащая любое количество ленточных символов, может быть смоделирована одним M', содержащим всего три ленточных символа: {0, 1, B} (B = Пусто).
Можно ли смоделировать М с помощью М", который имеет только два символа ленты,...
2827 просмотров
schedule
15.01.2023
Необходимо минимальное количество состояний?
Определение языка L с алфавитом { a } дается следующим образом
L = { a nk | к > 0; и n — положительная целочисленная константа }
Какое количество состояний необходимо в DFA для распознавания L ?
На мой взгляд, должно быть k+1, но я...
3792 просмотров
schedule
03.08.2023
Минимизация конечного автомата
Я пытаюсь минимизировать этот DFA: http://img145.imageshack.us/img145/3006/dfac.png
Вот мой свернутый DFA: http://img195.imageshack.us/img195/4131/mdfa.png
Я прав? Спасибо
P.S. Это домашнее задание. Нам разрешено обсуждать домашнее...
391 просмотров
schedule
12.06.2023
Понимание распознавателей и решающих устройств в теории вычислений
У меня возникли некоторые проблемы с пониманием того, что значит для машины распознавать и определять язык. Думаю, я близок к определениям, но не прав.
Когда говорят, что машина Тьюринга T распознает язык L , где
L = { <A> | A is a...
9429 просмотров
schedule
13.07.2022
Союз в контекстно-свободных языках
Всегда ли объединение набора контекстно-свободных языков является контекстно-свободным? Обосновать ответ .....
Я знаю, что ответ положительный, но как я могу это доказать?
1592 просмотров
schedule
14.05.2023
Можно ли узнать, какие входные символы соответствуют какой части регулярного выражения?
Я пытаюсь создать инструмент, который использует что-то вроде регулярных выражений для поиска шаблонов в строке (не в текстовой строке, но сейчас это не важно). Я знаком с теорией автоматов, т.е. знаю, как реализовать базовое сопоставление регулярных...
535 просмотров
schedule
12.05.2023
Игра для 2 игроков в PSPACE
Итак, я дал логическую формулу Q с 2n переменными. Обозначается Q(x1...xn,y1...yn) и упоминается, что существует a1....an, принадлежащий {0,1} такой, что для каждого b1...bn, принадлежащего {0,1}, Q(a1...an,b1,....bn} оценивается как true, теперь...
166 просмотров
schedule
07.08.2023
Преобразование кода в рекуррентное отношение
Я готовлюсь к экзамену, и я столкнулся с некоторыми проблемами, которые мне нужно решить - работая с базовыми случаями:
Я перехожу от кода к рекуррентному отношению, а не наоборот
Пример 1:
if(n==1) return 0;
Теперь рекуррентное...
3061 просмотров
schedule
29.05.2023
Push Down Automanton-Computation
Я пытаюсь понять, как работает КПК. На следующей диаграмме я понимаю, как работают функции перехода и как должен обновляться стек. Но единственный вопрос, который у меня есть, это почему состояние Start также является состоянием принятия? в то...
55 просмотров
schedule
10.05.2022
DFA :- все строки, в которых каждый блок из пяти последовательных символов содержит не менее двух нулей
Я хочу построить DFA для языка: набор всех строк, таких что каждый блок из пяти последовательных символов содержит не менее двух нулей. Как вести учет последних 5 записей. Короче как решить такую проблему. Я получил диаграмму DFA в Интернете, но...
12581 просмотров
schedule
09.08.2022
Преобразование регулярного выражения в DFA
Я пытался преобразовать регулярное выражение
к недетерминированному конечному автомату (NFA), сначала используя конструкцию Томпсона, что дает:
, что выглядит правильно.
Затем я использую построение подмножества для создания DFA из...
1922 просмотров
schedule
10.06.2024
Подсчет частоты букв в КПК
Я пытаюсь создать КПК или CFG, который принимает все слова, где E — самая распространенная буква. Например, сыр и тройник будут на языке. Я почти уверен, что этот язык не зависит от контекста, но я не могу создать для него КПК. Это возможно?
198 просмотров
schedule
21.04.2022
Какие типы строк генерируются (a*+b*)
Помимо строк с любым количеством букв a и b, таких как aa.. или bb.., будет ли регулярное выражение (a*+b*) содержать строку, например
ab
или любая строка, оканчивающаяся на b?
Является ли (a*+b*) таким же, как (a* b*)?
Я немного...
3956 просмотров
schedule
24.04.2024
Не могу понять решение (машина Тьюринга и редукция)
Нажмите здесь, чтобы увидеть мою проблему
Hi.
Что касается этого вопроса, я просто не могу понять его решение.
Мы знаем дополнение Atm = { <M,W> : M является TM и M не принимает W} и Rtm, как описано на фото = { <M,W> : M...
211 просмотров
schedule
13.04.2023
Существуют ли какие-либо рекурсивно перечисляемые проблемы, которые не являются RE-сложными?
Класс вычислимости, который я беру, объясняет несколько языков, которые находятся в RE - REC (рекурсивно перечисляемые, но не рекурсивные, т.е. решаемые безостановочной машиной Тьюринга). Сначала показано, как один из них (L_d, язык машин Тьюринга,...
484 просмотров
schedule
25.02.2022
Можно ли вычислить функцию подсчета простых чисел и произведение последовательных простых чисел за полиномиальное время?
В двух алгоритмах, с которыми я работал, я использую две функции:
pi(n):=количество простых чисел ‹= n и
R(n):=r , где prod(p_i,i=1,r)‹=n , но n ‹ prod(p_i,i=1, r+1) , где p_i — i-е простое число.
По сути, pi(n) — это известная...
244 просмотров
schedule
03.09.2022
Количество элементов, удовлетворяющих отношению
Даны два массива:
2 5 6 4 3 7 1
5 1 6 2 3 7 4
подсчитайте количество элементов x, y , которые удовлетворяют условию, что x предшествует y в обоих массивах.
Прогресс на данный момент:
Отсортируйте массивы по их индексам....
81 просмотров
schedule
29.05.2024
что означают регулярные, распознаваемые по Тьюрингу и распознаваемые по Тьюрингу?
Я знаю, что этот вопрос задавался ранее, но, честно говоря, я не совсем понимаю его.
В настоящее время я изучаю теорию вычислений и подхожу к термину «Докажите, что язык разрешимый, узнаваемый или регулярный».
Проще говоря, что они на самом деле...
2228 просмотров
schedule
02.12.2022
