Вопросы с тегом «regular-language»

14
Иерархии на обычных языках

Существует ли какая-либо известная «хорошая» иерархия L0⊆L1⊆L2⊆…L0⊆L1⊆L2⊆…L_0 \subseteq L_1 \subseteq L_2 \subseteq \dots (может быть конечной) внутри класса регулярных языков ? К счастью, классы в каждой иерархии отражают различную выразительность / мощность / сложность. Кроме того, членство...

14
Обычный против TC0

Согласно Сложности 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...

14
О реализации моноидов как синтаксических моноидов языков

Пусть - некоторый язык, тогда мы определим синтаксическую конгруэнцию как 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...

13
(N) DFA с таким же начальным / принимающим состоянием (ями)

Что известно о классе языков, распознаваемых конечными автоматами, имеющими одинаковое начальное и принимающее состояние? Это правильное подмножество обычных языков (поскольку каждый такой язык содержит пустую строку), но насколько он слаб? Есть ли простая алгебраическая характеристика? То же самое...

13
Автоматическое обучение без контрпримеров

В системе автоматического обучения Англуина ученик стремится выучить обычный язык L ⊆ Σ*L⊆Σ*L\subseteq \Sigma^* , задавая своему учителю два типа вопросов: Запросы по словам: если w ∈ Σ*вес∈Σ*w\in \Sigma^* , есть ли ?w ∈ Lвес∈Lw\in L Запросы на эквивалентность: если задан язык , является ли ? Если...

11
Параметризованная сложность включения обычных языков

Меня интересует классическая проблема РЕГУЛЯРНОГО ВКЛЮЧЕНИЯ ЯЗЫКА. Для регулярного выражения обозначим через L ( E ) связанный с ним регулярный язык. (Регулярные выражения на фиксированном алфавите Σ с объединением операций, звездой Клини и конкатенацией.)ЕЕEL ( E)L(Е)L(E)ΣΣ\Sigma Входные данные:...

11
Количество классов эквивалентности в обычных языках как функция размера DFA

Этот вопрос связан с недавним вопросом по Janoma . Фон В программировании ограничений, A регулярное глобальное ограничение ccc над областью DDD представляет собой пару (s,M)(s,M)(s, M) с sss кортежем переменных (о масштабе) и MMM ДКА над областью DDD . Назначение θθ\theta для sss удовлетворяет ccc...

11
Неоднозначность в обычных и контекстно-свободных языках

Я понимаю следующие утверждения, чтобы быть правдой: Два разных вывода строки в данном CFG могут иногда приписывать строку одному и тому же дереву разбора. Когда есть производные некоторой строки в данном CFG, которые приписывают различные деревья разбора, CFG является неоднозначным. Некоторые...

10
Можно ли решить, ограничена ли выходная длина преобразователя входной длиной?

Рассматриваемые здесь преобразователи - это те, которые Википедия называет преобразователями конечного состояния . Поведение преобразователя , то есть вычисляемого им отношения, записывается как [ T ] : слово y является выходом для x тогда и только тогда, когда x [ T ] y...

10
Какой класс языков распознается конечными автоматами с головами?

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

9
Недетерминированные линейные ограниченные автоматы ограниченного посещения распознают только регулярные языки?

Недетерминированные линейные ограниченные автоматы ограниченного посещения распознают только регулярные языки? Под недетерминированным линейным ограниченным автоматом (nLBA) я подразумеваю недетерминированную машину Тьюринга с одной лентой, где вход «дополняется» конечными маркерами на обоих...

9
Обычные языки и постоянная сложность общения

Пусть будет языком, и определим как тогда и только тогда, когда , Я ищу ссылку для:L⊆A∗L⊆A∗L \subseteq A^*fL:A∗×A∗→{0,1}fL:A∗×A∗→{0,1}f_L\colon A^* \times A^* \to \{0, 1\}fL(x,y)=1fL(x,y)=1f_L(x, y) = 1x⋅y∈Lx⋅y∈Lx\cdot y \in L Предложение. является регулярным, если детерминированная...

9
Сложность проверки, если два слова имеют чередование в языке

Для фиксированного языка LLL на каком-то алфавите AAA, давайте рассмотрим следующую проблему, которую я называю LLL-Интерлевинг : Вход: два слова u,v∈A∗u,v∈A∗u, v \in A^* Вывод: существует ли там перемежения изuuu а также vvv который в LLL, Здесь чередование двух словuuu а также vvv это слово www...

9
Переход моноидного членства для DFA

Учитывая полный 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, ⋯...

9
Обобщение утверждения, что моноид распознает язык, если синтаксический моноид делит моноид

Позволять AAAбыть конечным алфавитом. Для данного языкаL ⊆A*L⊆A∗L \subseteq A^{\ast}синтаксический Моноид M( Л )M(L)M(L)является известным понятием в теории формального языка. Кроме того, моноидMMM признает язык LLL если существует морфизм φ :A*→ Мφ:A∗→M\varphi : A^{\ast} \to M такой, что L =φ- 1(...