Пусть будет константой. Как мы можем с уверенностью построить псевдослучайный генератор, который обманывает конечные автоматы d- состояния?dddddd Здесь, -state имеет конечные автоматы d узлов, начальный узел, набор узлов , представляющие принимают состояния, и две направленных ребер помечены 0, 1 ,...
Скажем, у кого-то есть язык , но вы не знаете, какие строки на самом деле являются частью языка. Все, что есть, - это конечное представление языка: конечный набор строк о которых известно, что они есть в языке, и конечный набор строк , которые известны не быть на языке.L⊆Σ∗L⊆Σ∗L \subseteq...
MPA (многопробельный автомат) - это 2DFA (двусторонний детерминированный конечный автомат), который может использовать произвольное количество камешков (на самом деле самое большее камешков на заданном входе - вход записывается на ленту между двумя концами -маркер как ). Во время вычисления MPA...
Может ли кто-нибудь привести пример двух эквивалентных (распознающих один и тот же язык) минимальных недетерминированных автоматов (NFA), которые не являются...
Вдохновленный этим вопросом , мне интересно следующее: Какова сложность наихудшего случая проверки, принимает ли данный DFA тот же язык, что и данное регулярное выражение? Это известно? Надежда будет заключаться в том, что эта проблема в P - что есть алгоритм полинома в размере...
Я ищу обзорную статью о важных концепциях в области квантовых автоматов. Я нашел квантовую теорию автоматов - обзор Хирвенсало, но она звучит слишком кратко, чтобы понять тему. Существует ли достаточно всеобъемлющий опрос на тему квантовых автоматов? Кроме того, не могли бы вы указать мне...
Остаточные автоматы в конечном состоянии (RFSA, определенные в [DLT02]) - это NFA, которые имеют некоторые общие черты с DFA. В частности, для каждого обычного языка всегда существует канонический RFSA минимального размера, а язык, распознаваемый каждым государством в RFSA, является остаточным, как...
Предположим, вам даны два детерминированных автомата нажатия, которые распознают языки и B , и хотите определить, существует ли регулярный язык R такой, что A ⊆ R и R ∩ B = ∅ . По сути, задача состоит в том, чтобы определить, существует ли DFA, способный распознавать, из какого из двух языков...
В настоящее время я занимаюсь исследованиями Формального языка, в которых участвуют классы языков выше обычного, но ниже контекста. Я смотрю на такие вещи, как машины с множеством счетчиков с ограниченным обращением, счетчики с одним стеком, детерминированные КЛЛ и т. Д. Мне интересно, знает ли...
Можно ли построить алгоритм, который принимает в качестве входных данных автомат сокращения вместе с обещанием, что язык, принятый этим автоматом является детерминированным контекстно-свободным языком и выводит детерминированный автомат нажатия который принимает именно принятый язык на ?MMMЛ (...
Я ищу общий метод, который может помочь мне доказать не только то, что автоматы Бучи являются более выразительной моделью, чем LTL, но и то, что конкретная формула может / не может быть выражена в LTL. Например, « встречается хотя бы на четных позициях» может быть описано следующими автоматами...
Этот вопрос связан с недавним вопросом по Janoma . Фон В программировании ограничений, A регулярное глобальное ограничение ccc над областью DDD представляет собой пару (s,M)(s,M)(s, M) с sss кортежем переменных (о масштабе) и MMM ДКА над областью DDD . Назначение θθ\theta для sss удовлетворяет ccc...
После прочтения соответствующего вопроса о неконструктивных доказательствах существования алгоритмов мне стало интересно, есть ли способы показать существование «маленьких» (скажем, состояний) вычислительных машин без фактического их построения. Формально: предположим, нам дан некоторый язык и...
Все мои учебники используют один и тот же алгоритм для создания DFA с заданным регулярным выражением: во-первых, создайте NFA, который распознает язык регулярных выражений, затем, используя конструкцию подмножества (он же «powerset»), преобразуйте NFA в эквивалентный DFA ( при желании...
Существует ли 2DFA с состояниями (где n нетривиально, скажем, по крайней мере 4), для которых требуется по крайней мере 2 n состояния для моделирования с использованием любого DFA?NnnNnn2N2n2^n Двусторонний DFA (2DFA) является детерминированным конечным числом состояний автомата , который может...
Односторонние чередующиеся нажимные автоматы (1APDA) могут распознавать любой язык в (Чередование, Чандра, Козен и Стокмейер, 1981) . Заменив хранилище 1APDA со счетчиком, можно получить односторонний чередующийся автомат с одним счетчиком (1ACA). Мой вопрос о 1ACA на унарных языках.Д ТяMЕ( 2O ( n...
Обновление: кажется, что эта проблема была недавно изучена и решена, см. Эту статью вики: http://en.wikipedia.org/wiki/Tree_walking_automaton А также этот опрос: http://www.mimuw.edu.pl/~bojan /papers/twasurvey.pdf Предположим, что вместо обычного набора слов {0,1} * наши слова не линейны, а заданы...
DFA или NFA читает входную строку с одной головой, двигаясь слева направо. Кажется естественным задаться вопросом о конечных автоматах, которые имеют несколько головок , каждая из которых движется через вход слева направо, но не обязательно в том же месте на входе, что и другие. Определим конечный...
Детерминированный автомат называется k- локальным при k > 0, если для каждого w ∈ X k множество { δ ( q , w ) : q ∈ Q } содержит не более один элемент. Интуитивно это означает, что если слово w длины k приводит к состоянию, то это состояние уникально или сказано иначе, чем произвольное слово...
Я заинтересован в небольшом обобщении DFA. Как обычно, мы имеем набор состояний , конечный алфавит , действие определенное на помощью , и начальное состояние ; но вместо обычного терминального множества, мы берем семейство подмножеств . Многоязычный DFA - это...