Все недетерминированные конечные автоматы можно превратить в эквивалентные детерминированные конечные автоматы. Однако детерминированные конечные автоматы допускают только одну стрелку на символ, указывающую из состояния. Следовательно, его штаты должны входить в состав множества штатов НФА....
В моем курсе теории вычислений многие наши проблемы связаны с использованием индукции по длине входной строки для доказательства утверждений о конечных автоматах. Я понимаю математическую индукцию, однако, когда вступают в игру струны, меня сильно сбивают с толку. Я был бы очень признателен, если...
Позволять L={an∣∃p≥n p, p+2 are prime}.L={an∣∃p≥n p, p+2 are prime}.\qquad L = \{a^n \mid \exists_{p \geq n}\ p\,,\ p+2 \text{ are prime}\}. Является регулярным?LLL На первый взгляд этот вопрос выглядел подозрительно, и я понял, что он связан с гипотезой о двойном простом числе . Моя проблема в...
Я прочитал страницу Википедии для правила 110 в клеточных автоматах, и я более или менее знаю, как они работают (набор правил решает, где рисовать следующие 1 или 0). Я только что прочитал, что они завершены по Тьюрингу, но я даже не могу понять, как бы вы «запрограммировали» «правило 110»?...
Я застрял в следующем вопросе: «Регулярные языки - это как раз те, которые принимаются конечными автоматами. Учитывая этот факт, покажите, что если язык принят некоторым конечным автоматом, то также будет принят некоторым конечным; состоит из всех слов». из необратима «.L R L R...
Может ли контекстно-свободная грамматика включать «мертвые состояния» из автомата, такие как G = ( { a , b , c } , { A , B , C} , { A → a B , B → b , B → C, C→с C} , A )?граммзнак равно({a,б,с},{A,В,С},{A→aВ,В→б,В→С,С→сС},A)?G = \big(\{a, b, c\}, \{A, B, C\}, \{A\to aB, B\to b, B\to C, C\to cC\},...
Основное определение машины Тьюринга (ТМ), по крайней мере, в моем собственном справочнике (Hopcroft + Ullman 1979), является детерминированным. Следовательно, мое собственное понимание проблемы остановки главным образом относится к детерминированной ТМ, хотя я знаю, что это может быть рассмотрено...
Является ли машина Тьюринга без возможности записи на пустые ячейки менее мощной, чем стандартная Тьюринг? Я думаю, что ответ - да, но я не могу найти вычисление, которое может сделать стандартная машина Тьюринга, но эта машина не может. Есть...
Например, когда мы рассматриваем DFA, который позволяет строкам, не имеющим подстрок, 00или 11I, я могу создать следующие два DFA:
Говорят, что пересечение языка L, не зависящего от контекста, с обычным языком M всегда является контекстно-свободным. Я понял доказательство создания перекрестного продукта, но до сих пор не понимаю, почему он не контекстный, а не регулярный. Язык, генерируемый таким пересечением, имеет строки,...
Это дополнительный вопрос этого . В предыдущем вопросе об экзотических конечных автоматах Алекс тен Бринк и Рафаэль обратились к вычислительным возможностям особого вида конечного автомата: автоматов с минимальной кучей. Они смогли показать, что набор языков, принимаемых такими машинами ( HALHALHAL...
Мне интересно, возможно ли это вообще, так как . Поэтому КПК, который может отличить слово от остальной части вполне может принять его , что звучит противоречиво для меня. w ∈ { a n b n c n ∣ n ≥ 0 } { a ∗ b ∗ c ∗ }{anbncn∣n≥0}∉CFL{anbncn∣n≥0}∉CFL\{a^n b^n c^n \mid n \geq 0\} \not\in...
Детерминированный конечный автомат (DFA) - это модель конечного автомата, способная принимать все и только обычные языки. DFA могут быть (и обычно) определены таким образом, что каждое состояние должно обеспечивать некоторый переход для всех элементов входного алфавита; другими словами, функция...
Алгоритм минимизации DFA Бжозовского создает минимальный DFA для DFA путем:граммGG обращая все ребра в , делая начальное состояние принимающим, а принимающее - начальным, чтобы получить NFA для обратного языка,N ′граммGGN'N′N' используя конструкцию powerset, чтобы получить для обратного...
Проблема, распознают ли два нажимных автомата один и тот же язык, неразрешима. Проблема того, распознает ли автомат с нажатием кнопки пустой язык, разрешима, следовательно, также решаемо, распознает ли он данный конечный язык. Неразрешимо, является ли язык, принятый автоматом нажатия, регулярным....
Я использовал FSM в схемах цифровых последовательных цепей. Но я незнаком с конечными автоматами. Может ли кто-нибудь помочь мне понять «основную» разницу между ними?...
Это дополнительный вопрос этого . В предыдущем вопросе об экзотических конечных автоматах Алекс тен Бринк и Рафаэль обратились к вычислительным возможностям особого вида конечного автомата: автоматов с минимальной кучей. Они смогли показать, что множество языков, принятых на таких машинах ( ), не...
Существуют ли неразрешимые свойства линейных ограниченных автоматов (избегая трюка с пустым языком множеств)? Как насчет детерминированного конечного автомата? (отложить в сторону неразрешимость). Я хотел бы получить пример (если возможно) неразрешимой проблемы, которая определена без явного...
Для языка LLL определите множество длин как множество длин слов в : L L S ( L ) = { | ты | | U ∈ L }LLLLLLL S (L)={ | ты | |U∈L}LS(L)={|u|∣u∈L}\mathrm{LS}(L) = \{|u| \mid u \in L \} Какие наборы целых чисел могут быть набором длины обычного...
Счетные машины с двумя или более счетчиками обычно показаны эквивалентными машинам Тьюринга в курсах по теории вычислений. Однако я не видел формального анализа того, какие языки можно распознать с помощью машины с одним счетчиком. Являются ли эти языки эквивалентными языкам, не зависящим от...