Обновление: кажется, что эта проблема была недавно изучена и решена, см. Эту статью вики: http://en.wikipedia.org/wiki/Tree_walking_automaton А также этот опрос: http://www.mimuw.edu.pl/~bojan /papers/twasurvey.pdf Предположим, что вместо обычного набора слов {0,1} * наши слова не линейны, а заданы...
Я заинтересован в небольшом обобщении DFA. Как обычно, мы имеем набор состояний , конечный алфавит , действие определенное на помощью , и начальное состояние ; но вместо обычного терминального множества, мы берем семейство подмножеств . Многоязычный DFA - это...
Детерминированный автомат называется k- локальным при k > 0, если для каждого w ∈ X k множество { δ ( q , w ) : q ∈ Q } содержит не более один элемент. Интуитивно это означает, что если слово w длины k приводит к состоянию, то это состояние уникально или сказано иначе, чем произвольное слово...
Конкретно, что я имею в виду под сложением, мы определяем как алфавит . Учитывая регулярные языки и под некоторым алфавитом , смотреть на . { 0 , 1 , 2 , . , , , i } A B Σ i A × BΣяΣi\Sigma_i{ 0 , 1 , 2 , . , , , я }{0,1,2,...,i}\{0, 1, 2, ..., i\}AAAВBBΣяΣi\Sigma_iA × BA×BA\times B Для каждой...
Каков стандартный подход к минимизации Büchi-Automata (или также Müller-Automata)? Перенос обычного метода из конечных слов, то есть установка двух состояний равными, если слова «заканчиваются» из принятых состояний одинаковы, не будут работать. Например, рассмотрим Büchi-Automoton, принимающий все...
Существует открытая проблема в формальных языках, известная как проблема разделения; который кратко изложен как заданные две отдельные строки длины , насколько большой DFA требуется, чтобы «разделить» их, то есть принять одну строку, но отклонить другую.nnn Вот некоторые соответствующие документы 1...
Пусть будет дано число . Рассмотрим следующий язык: L n = {Nnn .LN= {ш ш|w ∈ { 0 , 1 }N}Ln={ww|w∈{0,1}n}L_n = \{ \; ww \; \vert \; w \in \{0,1\}^{n} \; \} Словом, - это набор строк копирования длиной 2 n .LNLnL_n2 н2n2n Рассмотрим следующую функцию сложности состояний , в которой s ( n ) - это...
Рассматриваемые здесь преобразователи - это те, которые Википедия называет преобразователями конечного состояния . Поведение преобразователя , то есть вычисляемого им отношения, записывается как [ T ] : слово y является выходом для x тогда и только тогда, когда x [ T ] y...
DFA или NFA читает входную строку с одной головой, двигаясь слева направо. Кажется естественным задаться вопросом о конечных автоматах, которые имеют несколько головок , каждая из которых движется через вход слева направо, но не обязательно в том же месте на входе, что и другие. Определим конечный...
Я имею в виду языковые семейства, которые допускают произвольно длинные строки, а не соединения по n битам или спискам решений или любому другому «простому» языку, содержащемуся в {0,1} ^ n. Я спрашиваю об «теоретико-автоматных» регулярных языках, в отличие от «теоретико-логических»: что-то вроде...
По моему опыту, контекстно-зависимые языки и линейно-ограниченные автоматы часто пропускаются или зацикливаются на курсах теории вычислимости, и даже не учтены в некоторых заметных учебниках, хотя конечным автоматам и автоматам с выталкивающими функциями уделяется много внимания. Конечно, должна...
Хотелось бы знать, почему для распознавания контекстно-свободных языков работают только недетерминированные автоматы push-down (DPA = NPDA). Почему детерминированные автоматы (DPDA) не распознают такие...
Меня интересуют эффективные алгоритмы пересечения DFA для особых случаев. А именно, когда DFA пересекаются, подчиняются определенной структуре и / или работают по ограниченному алфавиту. Есть ли источник, где я могу найти алгоритмы таких случаев? Чтобы не делать вопрос слишком широким, особый...
Для регулярного языка на алфавите его минимальный детерминированный автомат можно рассматривать как ориентированный связный мультиграф с постоянной степенью outи отмеченное начальное состояние (забывая метки переходов, конечные состояния). Мы сохраняем исходное состояние, потому что каждая вершина...
Алгоритм Бжозовского для преобразования DFA в эквивалентный DFA с минимальным состоянием удивительно прост: если R(D)R(D)R(D) обозначает NFA, образованный путем обращения всех ребер в DFA DDDпревращение старого начального состояния в принимающее состояние и превращение старого принимающего...
Недетерминированные линейные ограниченные автоматы ограниченного посещения распознают только регулярные языки? Под недетерминированным линейным ограниченным автоматом (nLBA) я подразумеваю недетерминированную машину Тьюринга с одной лентой, где вход «дополняется» конечными маркерами на обоих...
Позволять ΣΣ\Sigma быть алфавитом размера 222и рассмотрим минимальные DFA, размер которых ограничен не более мmm, Позволятье( м )f(m)f(m) обозначим количество различных таких минимальных ДФА. Можем ли мы найти формулу замкнутой формы для е( м )f(m)f(m)? Учитывая, что для | Σ | =2|Σ|=2|\Sigma|=2...
Позволять ΣΣ\Sigmaбыть конечным алфавитом. код XXX над ΣΣ\Sigma это подмножество Σ∗Σ∗\Sigma^* так, что каждое слово в X∗X∗X^* может быть однозначно представлен в виде объединения слов в XXX, КодXXXявляется конечным , если|X||X||X|конечно. Что известно о (минимальных) автоматах распознаванияX∗X∗X^*...
Учитывая полный DFA A = ( Q , Γ , δ, F)A=(Q,Γ,δ,F)A=(Q, \Gamma, \delta, F)мы можем определить коллекцию функций еafaf_a для каждого a ∈ Γa∈Γa\in \Gammaи с еa: Q → Qfa:Q→Qf_a:Q\rightarrow Q, еa( д) = δ( д, )fa(q)=δ(q,a)f_a(q)=\delta(q, a), Мы можем обобщить это понятие на словоW =a1, ⋯...
Какое-то время мне было любопытно, что машины Тьюринга имеют ровно одну ленту и ровно 3 состояния (а именно, начальное состояние , состояние принятия и состояние отказа ). Обратите внимание, что я допускаю произвольные (конечные) алфавиты ленты (т. Е. Алфавит ленты не ограничен равным входному...