Вопросы с тегом «nondeterminism»

Я проходил дискуссию по вопросу, как определить квантовые машины Тьюринга? и я чувствую, что квантовая ТМ и недетерминированная ТМ - это одно и то же. Ответы на другой вопрос не касаются этого. Являются ли эти две модели одинаковыми? Если нет, Каковы различия между квантовой ТМ и НДТМ? Существуют...

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

Мы знаем, что DFAs эквивалентны NFAs в силе выразительности; Существует также известный алгоритм для преобразования NFA в DFA (к сожалению, я теперь знаю изобретателя этого алгоритма), который в худшем случае дает нам состояния, если у нашего NFA было S состояний.2S2S2^SSSS Мой вопрос: что...

Автомат - это абстрактная модель цифрового компьютера. Цифровые компьютеры полностью детерминированы; их состояние в любое время однозначно предсказуемо из входных данных и исходного состояния. Когда мы пытаемся моделировать реальные системы, зачем включать недетерминизм в теорию автоматов?...

Все недетерминированные конечные автоматы можно превратить в эквивалентные детерминированные конечные автоматы. Однако детерминированные конечные автоматы допускают только одну стрелку на символ, указывающую из состояния. Следовательно, его штаты должны входить в состав множества штатов НФА....

Основное определение машины Тьюринга (ТМ), по крайней мере, в моем собственном справочнике (Hopcroft + Ullman 1979), является детерминированным. Следовательно, мое собственное понимание проблемы остановки главным образом относится к детерминированной ТМ, хотя я знаю, что это может быть рассмотрено...

Это дополнительный вопрос этого . В предыдущем вопросе об экзотических конечных автоматах Алекс тен Бринк и Рафаэль обратились к вычислительным возможностям особого вида конечного автомата: автоматов с минимальной кучей. Они смогли показать, что множество языков, принятых на таких машинах ( ), не...

Я понимаю, что недетерминированные автоматы нажатия могут быть улучшением по сравнению с детерминированными, поскольку они могут «выбирать» из нескольких состояний, и есть некоторые контекстно-свободные языки, которые не могут быть приняты детерминированным выпуском. Все-таки я не понимаю, как...

Я имею в виду этот [забавный] вопрос. Почему недетерминированный конечный автомат называется недетерминированным, в то время как мы определяем переходы для входных данных. Что ж, несмотря на то, что существуют множественные и эпсилон- переходы, они определены, что означает, что машина является...

Я знаю, что мы можем минимизировать DFA, находя и объединяя эквивалентные состояния, но почему мы не можем сделать то же самое с NFA? Я не ищу доказательств или чего-то в этом роде - если только доказательство не проще для понимания. Я просто хочу интуитивно понять, почему минимизация NFA так...

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

Я только начал читать о теории вычислений. Если мы сравним, что является более мощным (в принятии строк), оба одинаковы. Но как насчет эффективности? DFA будет быстрым по сравнению с NFA, поскольку у него есть только один исходящий фронт, и не будет никакой двусмысленности. Но в случае NFA мы...

Завтра моя презентация, и я хочу прояснить свои концепции ... Я прочитал это в DFA: «Для каждого состояния должен быть определен переход на все возможные символы (алфавит)». Является ли для каждого состояния определение перехода по всем возможным символам обязательным в DFA? Если нет, то приведите,...

На картинке ниже я пытаюсь понять, что именно принимает этот NFA. Что меня смущает, так это прыжок на .q 0εϵ\epsilonQ0q0q_0 Если введен , система переместится в и (состояние принятия)?q 0 q 1000Q0q0q_0 Q1q1q_1 Если введено , система переместится на и ?q 1 q 2111Q1q1q_1q2q2q_2 Переходит ли система...

На работе мне было поручено вывести некоторую информацию о типах динамического языка. Я переписываю последовательности операторов во вложенные letвыражения, например так: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x then {...

Мой учебник гласит: «Мы определяем функцию следующим образом: f ( 1 ) = 2 и f ( i + 1 ) = 2 f ( i ) 1.2 . Обратите внимание, что при заданном n мы легко можем найти в O ( n 1.5 ) умножить число i так , чтобы n зажалось между f ( i ) и f ( i + 1)f:N→Nf:N→Nf\colon...

Я учусь конвертировать NFA в DFA и хочу убедиться, что все делаю правильно. Очевидно, что возвращение в другом направлении - это не вещь. Кто-нибудь знает алгоритм проверки, что DFA эквивалентен...

Пусть входная строка будет задана как . Затем, если NFA в настоящее время находится в состоянии (и прочитал входной алфавит ), то перед чтением следующего входного символа NFA разделяется на два NFA, один из которых находится в состоянии а другой - в , если происходит переход тип . Если существует...

Я начал изучать недетерминированные автоматы, используя книгу Хопкрофта и Уллмана . Я застрял в проблеме, которая показалась мне очень интересной: Дать недетерминированный конечный автомат, принимающий все строки, имеющие одинаковое значение, при оценке слева направо как справа налево путем...

Я работаю через Sipser Book (2-е издание) и наткнулся на этот пример, который я не понимаю. В книге говорится, что этот NFA принимает пустую строку εε\epsilon . Может ли кто-нибудь объяснить мне, почему это так? Насколько я понимаю, εε\epsilon перейдет к Q3Q3q_3 который не является состоянием...