Недетерминированный Xor автомат (NXA) является синтаксически NFA, но говорят, что NXA принимает слово, если оно имеет нечетное число принимающих путей (вместо хотя бы одного принимающего пути в случае NFA). Легко видеть, что для конечного регулярного языка LLL существует минимальный NFA, который не...
Можно стандартно два счетчика ( ) машина со следующими инструкциями:c1,c2c1,c2c_1,c_2 1) ADD 1 to c_i, GOTO label_j 2) IF c_i = 0 GOTO label_j, OTHERWISE SUB 1 to c_i and GOTO label_k 3) GOTO label_j 4) HALT and ACCEPT|REJECT выбрать следующий язык: L={n2∣n≥1}L={n2∣n≥1}L = \{ n^2 \mid n \geq 1 \}...
Я читаю " Объединение регулярных языков и сложность описания " Галины Йирасковой, 2009 г., о сложности состояний, возникающей в результате объединения двух регулярных языков (Галина Жираскова), но я не могу понять, каковы будут практические последствия сложности состояний , Первая тривиальная...
Допустим, у меня есть большой блок кода, который я уже проанализировал и проанализировал. Предположим, что меняется только один символ; Я хотел бы обновить мой синтаксический анализ, но поскольку модификация очень мала по сравнению со всем этим, я хотел бы знать, возможно ли не анализировать все...
Лемма: Предполагая, что эта эквивалентность у нас есть (\x -> ⊥) = ⊥ :: A -> B. Доказательство: ⊥ = (\x -> ⊥ x)по eta-эквивалентности и (\x -> ⊥ x) = (\x -> ⊥)по сокращению под лямбду. В отчете Haskell 2010, раздел 6.2, seqфункция определяется двумя уравнениями: seq :: a -> b...
Рассмотрим следующий естественный вопрос: для какого конечного языка наименьшая не зависящая от контекста грамматика порождает L ?LLLLLL Мы можем сделать вопрос более интересным, указав последовательность языков , например, L n - это множество всех перестановок { 1 , … , n } : интуитивно, CFG для L...
Пусть - некоторый язык, тогда мы определим синтаксическую конгруэнцию как 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...
После прочтения недавнего вопроса «Является дополнение {www∣...}{www∣...}\{ www \mid ...\} Контекстно-свободным?» ; Я вспомнил похожую проблему, которую не смог опровергнуть: Является ли L={ww′∣w,w′∈{0,1}∗∧|w|=|w′|∧HamDist(w,w′)>1}L={ww′∣w,w′∈{0,1}∗∧|w|=|w′|∧HamDist(w,w′)>1}L = \{ ww' \mid...
Что известно о классе языков, распознаваемых конечными автоматами, имеющими одинаковое начальное и принимающее состояние? Это правильное подмножество обычных языков (поскольку каждый такой язык содержит пустую строку), но насколько он слаб? Есть ли простая алгебраическая характеристика? То же самое...
В настоящее время я занимаюсь исследованиями Формального языка, в которых участвуют классы языков выше обычного, но ниже контекста. Я смотрю на такие вещи, как машины с множеством счетчиков с ограниченным обращением, счетчики с одним стеком, детерминированные КЛЛ и т. Д. Мне интересно, знает ли...
Это, вероятно, довольно просто, но рассмотрим стандартную проблему почтовой корреспонденции: Учитывая и , найдите последовательность индексов такую, что . Это, конечно, неразрешимо.β 1 , … , β N i 1 , … , i K α i 1 ⋯ α i K = β i 1 ⋯ β i Kα1,…,αNα1,…,αN\alpha_1, \ldots,...
Хорошо известно, что дополнение к зависит от контекста. Но как насчет дополнения ?{ww∣w∈Σ∗}{ww∣w∈Σ∗}\{ ww \mid w\in \Sigma^*\}{www∣w∈Σ∗}{www∣w∈Σ∗}\{ www \mid w\in
Greibach лихо определил язык , так называемую недетерминированную версию о , таких , что любая КЛЛ является обратной морфической изображение . Существует ли подобное утверждение с DCFL, возможно, с некоторыми ограничениями на допустимые морфизмы?D 2 HЧАСHHD2D2D_2ЧАСHH (См., Например, М. Аутеберт,...
Может ли кто-нибудь привести пример двух эквивалентных (распознающих один и тот же язык) минимальных недетерминированных автоматов (NFA), которые не являются...
Я ищу язык L со следующими свойствами: L не должен быть контекстно-свободным. Дополнение L не должно быть контекстно-свободным. (Все, что вы видите в учебниках как главные примеры неконтекстно-свободных языков, похоже, не соответствует этому второму требованию.) L не должен быть слишком сложным....
Скажем, у кого-то есть язык , но вы не знаете, какие строки на самом деле являются частью языка. Все, что есть, - это конечное представление языка: конечный набор строк о которых известно, что они есть в языке, и конечный набор строк , которые известны не быть на языке.L⊆Σ∗L⊆Σ∗L \subseteq...
Я переместил этот вопрос из stackoverflow, где id не получил ответов. У нас был похожий вопрос , является ли JSON регулярным : JSON и XML часто называют языками без контекста - они оба определяются в основном формальной грамматикой в EBNF. Однако это верно только для JSON, как определено в RFC...
Языки Dyck определяются следующей грамматикой S → S SDyck(k)Dyck(k)\mathsf{Dyck}(k) над множеством символов { ( 1 , … , ( k , ) 1 , … , ) k } . Интуитивно понятно, что языки Dyck - это языки сбалансированных скобок k различного типа. Например, (S→SS|(1S)1|…|(kS)k|ϵS→SS|(1S)1|…|(kS)k|ϵ S \rightarrow...
Рассмотрим следующую проблему: Для двух строк x, y решите, существует ли строковый гомоморфизм f такой, что f (x) = y. Легко показать , что эта проблема находится в . Есть ли что-то еще, что мы можем сказать об этой проблеме? Например, это в c o N P или даже в P ?NPNPNPcoNPcoNPcoNPPPP Эта проблема...
РЕДАКТИРОВАТЬ (Тара B): Я все еще был бы заинтересован в ссылке на доказательство этого, так как я должен был доказать это сам для моей собственной статьи. Я ищу доказательство теоремы 4, которое появляется в этой статье: Бесконечная иерархия пересечений контекстно-свободных языков Лю и Вейнера....