Мне интересно, есть ли какие-либо статьи или исследования, посвященные явно выталкивающим автоматам, но позволяющие помещать слова, а не отдельные буквы, в стек. С другой стороны, конструкция, которая позволяла нажимать символы на ϵϵ\epsilon переходы, могла бы достичь той же цели. Очевидно, что...
Однозначные конечные автоматы (UFA) - это особый тип недетерминированных конечных автоматов (NFA). NFA называется однозначным, если каждое слово имеет не более одного приемлемого пути.w ∈ Σ*вес∈Σ*w\in \Sigma^* Это означает , что .D FA ⊂ UFA ⊂ NFADFA⊂UFA⊂NFADFA\subset UFA\subset NFA Известные...
Для языка L ⊆ Σ ^ * определите синтаксическую конгруэнцию ≡ в L как наименьшую конгруэнцию на Σ ^ *, которая насыщает L , т.е. u ≡ v ⇔ (∀ x, y) [xuy ∈ L ↔ xvy ∈ L]. Теперь определим эквивалентность Nerode как следующее правильное сравнение: u ∼ v ⇔ (∀ x) [ux ∈ L ↔ vx ∈ L]. Пусть [u] - класс...
В формальном описании автоматов детерминированного пушинга они разрешают перемещения, когда машина может вставлять или помещать символы в стек без чтения символа из ввода. Если эти перемещения недопустимы, а стек может быть изменен только один раз после каждого чтения символа, равны ли полученные...
Мы говорим , что НКА является постоянно Неоднозначность , если существует K ∈ N такое , что любое слово W ∈ Е * принимается либо 0 или (точно) К путям.MMMk∈Nk∈Nk\in \mathbb{N}w∈Σ∗w∈Σ∗w\in \Sigma^*000kkk Если автомат постоянно неоднозначен при k = 1 , то M называется однозначным FA...
Существует теоретическое доказательство того, что наивная декартова конструкция продукта для пересечения DFAs - «лучшее, что мы можем сделать». А как насчет объединения двух DFA? Тривиальная конструкция включает в себя преобразование каждого DFA в NFA, добавление эпсилон-перехода и определение...
Фон: Учитывая два детерминированных конечных автомата A и B, мы формируем произведение C, позволяя состояниям в C быть декартовым произведением состояний в A и состояний в B. Затем мы выбираем переходы, начальное состояние и конечные состояния, так что язык, принятый C является пересечением языков...
Пусть LL\mathcal{L} - семейство всех языков над ΣΣ\Sigma удовлетворяющих свойству накачки регулярных языков. А именно: для каждого L∈LL∈LL\in\mathcal{L} существует N∈NN∈NN\in\mathbb{N} st для каждого слова w∈Lw∈Lw\in L , |w|>N|w|>N|w|> N можно записать в виде w=xyzw=xyz w=xyz где: 1....
Лемма: Предполагая, что эта эквивалентность у нас есть (\x -> ⊥) = ⊥ :: A -> B. Доказательство: ⊥ = (\x -> ⊥ x)по eta-эквивалентности и (\x -> ⊥ x) = (\x -> ⊥)по сокращению под лямбду. В отчете Haskell 2010, раздел 6.2, seqфункция определяется двумя уравнениями: seq :: a -> b...
Недетерминированный Xor автомат (NXA) является синтаксически NFA, но говорят, что NXA принимает слово, если оно имеет нечетное число принимающих путей (вместо хотя бы одного принимающего пути в случае NFA). Легко видеть, что для конечного регулярного языка LLL существует минимальный NFA, который не...
Согласно Сложности Zoo , и мы знаем, что R e g не может сосчитать, поэтому T C 0 ⊈ R e g . Однако это не говорит, если R e g ⊆ T C 0 или нет. Поскольку мы не знаем N C 1 ⊈ T C 0, мы также не знаем R e g ⊈ T C 0 .Reg⊆NC1Reg⊆NC1\mathsf{Reg} \subseteq \mathsf{NC^1}RegReграмм\mathsf{Reg}TC0E R...
Я читаю " Объединение регулярных языков и сложность описания " Галины Йирасковой, 2009 г., о сложности состояний, возникающей в результате объединения двух регулярных языков (Галина Жираскова), но я не могу понять, каковы будут практические последствия сложности состояний , Первая тривиальная...
Пусть - некоторый язык, тогда мы определим синтаксическую конгруэнцию как u ∼ v : ⇔ ∀ x , y ∈ X ∗ : x u y ∈ L ↔ x v y ∈ L и фактор-моноид X ∗ / ∼ L равен называется синтаксическим моноид из L .L⊆X∗L⊆X∗L \subseteq X^{\ast}u∼v:⇔∀x,y∈X∗:xuy∈L↔xvy∈Lu∼v:⇔∀x,y∈X∗:xuy∈L↔xvy∈L u \sim v :\Leftrightarrow...
Существует ли какая-либо известная «хорошая» иерархия L0⊆L1⊆L2⊆…L0⊆L1⊆L2⊆…L_0 \subseteq L_1 \subseteq L_2 \subseteq \dots (может быть конечной) внутри класса регулярных языков ? К счастью, классы в каждой иерархии отражают различную выразительность / мощность / сложность. Кроме того, членство...
Учитывая конечный (детерминированный или недетерминированный, я не думаю, что это имеет большое значение) автомат A и порог n , принимает ли A слово, содержащее не более n различных букв? (Под k разными буквами я подразумеваю, что aabaa имеет две разные буквы, a и b .) Я показал, что эта задача...
В системе автоматического обучения Англуина ученик стремится выучить обычный язык L ⊆ Σ*L⊆Σ*L\subseteq \Sigma^* , задавая своему учителю два типа вопросов: Запросы по словам: если w ∈ Σ*вес∈Σ*w\in \Sigma^* , есть ли ?w ∈ Lвес∈Lw\in L Запросы на эквивалентность: если задан язык , является ли ? Если...
Что известно о классе языков, распознаваемых конечными автоматами, имеющими одинаковое начальное и принимающее состояние? Это правильное подмножество обычных языков (поскольку каждый такой язык содержит пустую строку), но насколько он слаб? Есть ли простая алгебраическая характеристика? То же самое...
Обучая, как реализовывать автоматы с использованием синхронных логических схем, я заметил интересное совпадение: как в теоретическом мире CS, так и в мире электротехники «состояние» обычно обозначается как (и пространство состояний Q ). Сначала я спросил об EE.sx , но затем, немного исследуя эту...
Итак, у меня есть около 100-200 очень разреженных квадратных логических матриц с длиной стороны ~ несколько десятков, и мне нужно вычислить их произведение. Я знаю, что, если я умножу их поочередно, продукт, как правило, останется разреженным на каждом этапе. Существуют ли какие-либо алгоритмы...
Остаточные автоматы в конечном состоянии (RFSA, определенные в [DLT02]) - это NFA, которые имеют некоторые общие черты с DFA. В частности, для каждого обычного языка всегда существует канонический RFSA минимального размера, а язык, распознаваемый каждым государством в RFSA, является остаточным, как...