Вопросы по теме 'computation-theory'
Контекстно-свободные грамматики
Существует ли алгоритм, который генерирует все строки из заданной контекстно-свободной грамматики?
1308 просмотров
schedule
14.08.2022
Докажите, что задача факторизации α находится в NP
Пытаюсь освежить теорию вычислений, но не уверен в решении этой проблемы:
Prove that the problem of factoring α is in NP.
У меня есть ощущение, что это может быть связано с поиском проблемы NP и поиском сведения к проблеме факторизации α.
395 просмотров
schedule
08.06.2023
Спроектировать язык L так, чтобы ни L, ни его дополнение не имели бесконечного регулярного подмножества?
У меня занятия по теории автоматов, и прямо сейчас мы изучаем лемму о прокачке. Существует вопрос для упражнения, в котором нас просят: «Спроектировать язык L так, чтобы ни L, ни его дополнение не имели бесконечного регулярного подмножества?» Но я...
1481 просмотров
schedule
11.08.2022
Как я могу доказать, является ли этот язык правильным или нет?
Как я могу доказать, является ли этот язык правильным или нет?
L = {a n b n : n1} union {a n b n+2 : n1}
2954 просмотров
schedule
27.08.2022
Является ли {ш | w ‹› w^R } над алфавитом {0,1} контекстно-свободный язык?
Мне бы очень хотелось, чтобы вы помогли решить, является ли язык всех слов в алфавите {0,1} , который не может быть прочитан с обеих сторон одинаково, { w | w <> w R } , контекстно-свободным языком (то есть его можно преобразовать в...
3805 просмотров
schedule
26.07.2022
Алгоритм разделения списка на две равные части
Связанные вопросы:
Алгоритм разделения списка чисел на 2 списка с равной суммой
разделите список на две части, чтобы их сумма самые близкие друг к другу
Предположим, у меня есть список, который содержит ровно 2k элементов....
1546 просмотров
schedule
28.05.2024
Разрешимость FA с тремя состояниями
Я пытаюсь выяснить, как описать пятьдесят шесть строк, чтобы проверить, имеет ли FA с тремя состояниями над алфавитом {a b} конечный язык.
Число пятьдесят шесть исходит из теоремы, которая гласит, что если машина имеет N состояний, а алфавит...
124 просмотров
schedule
25.05.2022
Является ли a*b* нормальным?
Я знаю, что a n b n для n > 0 не является регулярным по лемме о накачке, но я бы предположил, что a*b* является регулярным, поскольку оба a, b не обязательно должны быть такой же длины. Есть доказательства того, что это регулярно или нет?
10339 просмотров
schedule
20.07.2023
Языки для контекстно-свободных грамматик
Предоставьте контекстно-свободные грамматики для следующих языков.
(a) {a^mb^nc^n | m ≥ 0 and n ≥ 0 }
(b) {a^nb^nc^m | m ≥ 0 and n ≥ 0 }
Если бы были задействованы какие-либо другие правила, такие как m = n или что-то в этом роде, я мог бы...
982 просмотров
schedule
14.01.2023
Как доказать, что данный язык не распознается
Учитывая следующий язык:
Lf = { р (м) | Язык M конечен }
Лф узнаваем? если нет, докажите с помощью приведения. В противном случае создайте NDTM, который его распознает.
Я почти уверен, что Lf нельзя распознать, но я не уверен, как это...
651 просмотров
schedule
05.10.2022
Является ли понимание списка или последовательный фильтр более оптимизированным?
Допустим, вам нужно вернуть сумму всех чисел, кратных 2 и 3, в наборе целых чисел от 1 до 100. В Haskell код, который я бы написал, будет выглядеть примерно так:
sum ([x*2 | x<-[1..100], x*2 < 100] `union` [x*3 | x<-[1..100], x*3 <...
110 просмотров
schedule
11.06.2023
Алгоритм Хопкрофта — минимизация DFA
Я хочу реализовать алгоритм Хопкрофта для минимизации DFA WIKIPEDIA . До сих пор я могу удалить недоступные состояния. Проблема в том, что я не понимаю этот алгоритм. Я не знаю, как это реализовать. Кто-нибудь может это объяснить? Или, может...
6872 просмотров
schedule
28.09.2022
Полный взвешенный график G, нахождение весов и одна машина
Я много читал о темах Complete Weighted Graph и Hamiltonian Tour на этом сайте, которые спросил один из пользователей, я спросил много сотрудников в моем университете, но не смог получить хороший ответ, я изменил важную часть этого вопроса...
267 просмотров
schedule
10.07.2023
Пересечение линии и выпуклого множества
Пусть X будет набором n точек в некотором пространстве умеренной размерности — пока, скажем, R ^ 5. Пусть S — выпуклая оболочка X, пусть p — точка в S, а v — любое направление. Наконец, пусть L = {p + lambda v : lambda действительное число} будет...
760 просмотров
schedule
09.05.2023
Использование условия 3 леммы о накачке для доказательства неправильности
Итак, я просматривал книгу Сипсера по теории вычислений, и одно из упражнений:
Пусть B — язык {0^n1^n | n≥0}.
Докажите, что B не является регулярным.
Книга продолжает давать доказательство с использованием леммы о накачке, допуская s = 0 ^...
114 просмотров
schedule
10.05.2022
Если детерминированная машина Тьюринга определяет язык L, означает ли это, что она также определяет дополнение языка L?
Предположим, что существует детерминированная машина Тьюринга, например. тот, который выполняется за полиномиальное время и определяет язык L.
Означает ли это автоматически, что он также определяет дополнительный язык L?
Говоря о дополнительном...
168 просмотров
schedule
19.10.2022
Контекстно-свободная грамматика для языка L = a^(2^k)
В рамках упражнения по теории вычислений меня попросили найти контекстно-свободный язык для языка L = a^(2^k).
Как я пытался решить эту проблему: я хочу работать с предложением X , которое рекурсивно удваивает все буквы "а", которые были...
437 просмотров
schedule
28.03.2023
В чем разница между рекурсивными и рекурсивно перечислимыми языками
Мне было интересно, в чем разница между рекурсивными и рекурсивно перечислимыми языками с точки зрения остановки и машин Тьюринга. Я знаю, что рекурсивно перечисляемые языки являются подмножеством рекурсивных языков, но я не уверен в отличии от этого.
23650 просмотров
schedule
29.04.2023
Получить пересечение двух NFA
Итак, у меня есть проблема, когда мне нужно найти пересечение двух NFA, и я не нахожу решения. Итак, у вас есть два автомата m1 и m2 с m1=(Q1, Σ1, ∆1, q1, F1) и m2=(Q2, Σ2, ∆2, q2, F2).
Я думаю, что Q формируется комбинацией состояний Q1 и Q2, так...
1135 просмотров
schedule
07.07.2022
Язык, который может быть распознан ТМ, но не может быть определен ТМ?
Может ли язык, который может быть распознан ТМ, но не может быть определен ТМ?
пример языка, который может быть распознан ТМ, но не может быть определен ТМ
Будет ли ответ:
TM={<M,w> M is a TM that accepts input string w}...
535 просмотров
schedule
25.03.2023
