Вопросы с тегом «context-free»

31
Рациональная иерархия Эйленберга нерациональных автоматов и языков - где она сейчас?

В предисловии к своим очень влиятельным книгам «Автоматы, языки и машины» (тома A, B) Самуэль Эйленберг обещал соблазнительно изложить тома C и D, посвященные «иерархии (называемой рациональной иерархией) нерациональных явлений ... используя рациональные отношения как инструмент для сравнения....

25
Существует ли расширение регулярных выражений, которое фиксирует языки без контекста?

Во многих работах с использованием контекстно-свободных грамматик (CFG) примеры таких грамматик, представленные там, часто допускают простую характеристику языка, который они генерируют. Например: S→aaSbS→aaSbS \to a a S b S→S→S \to генерирует {a2ibi|i≥0}{a2ibi|i≥0}\{ a^{2i} b^i | i \geq 0\} ,...

23
Для того чтобы язык был программируемым, обязательно ли он основывался на контекстно-свободной грамматике

Практически, для языка, который в конечном итоге может быть скомпилирован / преобразован в инструкции системного уровня, необходимо ли, чтобы это была контекстно-свободная грамматика? пример: все ли языки программирования / написания сценариев являются контекстно-свободными грамматиками? Java...

22
Можно ли анализировать все однозначные грамматики за линейное время?

Когда я возился с неканоническим анализом LR, я придумал метод синтаксического анализа (с таблицами бесконечного размера, что делает его несколько непрактичным ), способный анализировать ровно однозначные грамматики за времени, и мне было интересно, возможно ли это сделать лучше:O(n2)O(n2)O(n^2)...

21
Языки, которые мы не можем (не) доказать, что не зависят от контекста

Я ищу языки, которые "вероятно, не являются контекстно-свободными", но мы не можем (не) доказать это, используя известные стандартные методы. Есть недавний опрос на предмет или открытый проблемный раздел от недавней конференции? Вероятно, не так много языков, которые не известны как CF, поэтому,...

20
Сложность пересечения регулярных языков как контекстно-свободных грамматик

При заданных регулярных выражениях , существуют ли нетривиальные ограничения на размер наименьшей контекстно-свободной грамматики для R 1 ∩ ⋯ ∩ R n ?р1, … , RNR1,…,RnR_1, \dots, R_nр1∩ ⋯ ∩ RNR1∩⋯∩RnR_1 \cap \cdots \cap...

19
Как доказать, что контекстно-свободный язык является неоднозначным неразрешимым?

Я где-то читал, что машина Тьюринга не может вычислить это, и поэтому она неразрешима, но почему? Почему для компьютера невозможно вычислить дерево разбора и принять решение? Возможно я ошибаюсь и это можно...

19
Разрешима ли эквивалентность однозначных контекстно-свободных языков?

Хорошо известно, что проблема эквивалентности неразрешима для общих контекстно-свободных языков. Тем не менее, все доказательства этого факта, о которых я знаю, похоже, включают в себя некоторые неоднозначные контекстно-свободные грамматики. По этой причине я хотел бы спросить, известно ли,...

18
Синтаксический анализ CFG с использованием пространства

Существует множество алгоритмов, которые могут анализировать грамматику без контекста за . Используя матричное умножение, можно даже пойти асимптотически быстрее, чем это.O(n3)O(n3)O(n^3) Тем не менее, все алгоритмы для разбора произвольных CFG, которые я знаю, имеют использование пространства в...

17
Ссылка для «более алгебраического» подхода к автоматам и КЛЛ?

В книге Сакаровича по теории автоматов во введении к разделу о рациональных числах в свободной группе написано, что представленный в нем материал закладывает «основу действительно математической теории языков без контекста». Тем не менее, это не указывается явно, так как языки без контекста и...

16
Существуют ли варианты визуально выпадающих автоматов, которые позволяют помещать слова в стек?

Мне интересно, есть ли какие-либо статьи или исследования, посвященные явно выталкивающим автоматам, но позволяющие помещать слова, а не отдельные буквы, в стек. С другой стороны, конструкция, которая позволяла нажимать символы на ϵϵ\epsilon переходы, могла бы достичь той же цели. Очевидно, что...

16
Характеристика

В курсах автоматов стандартным доказательством является то, что для L=Σ⋆L=Σ⋆L = \Sigma^\star и |Σ|≥2|Σ|≥2|\Sigma| \ge 2 что не является контекстно-свободным языком.S(L)={ww:w∈L}S(L)={ww:w∈L}S(L) = \{ww : w \in L\} Это также верно , что для любого конечного , S ( L ) конечна (и , следовательно,...

16
Являются ли DPDA без

В формальном описании автоматов детерминированного пушинга они разрешают перемещения, когда машина может вставлять или помещать символы в стек без чтения символа из ввода. Если эти перемещения недопустимы, а стек может быть изменен только один раз после каждого чтения символа, равны ли полученные...

14
Достаточные условия регулярности языка без контекста

Было бы неплохо собрать список условий, которые подразумевают, что язык L без контекста является регулярным, то есть условия вида: «если данный CFG / PDA имеет свойство P, то его языки являются регулярными» Свойство P не должно характеризовать CFG, генерирующие регулярные языки. Кроме того, P не...

14
Нижние границы размера CFG для определенных конечных языков

Рассмотрим следующий естественный вопрос: для какого конечного языка наименьшая не зависящая от контекста грамматика порождает L ?LLLLLL Мы можем сделать вопрос более интересным, указав последовательность языков , например, L n - это множество всех перестановок { 1 , … , n } : интуитивно, CFG для L...

13
Is {ww '| HamDist (w, w ')> 1} не зависит от контекста?

После прочтения недавнего вопроса «Является дополнение {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...

12
Ссылка на языки Dyck, являющаяся

Языки 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...

12
Является ли SAT контекстно-свободным языком?

Я рассматриваю язык всех выполнимых логических формул высказываний, SAT (чтобы гарантировать, что у этого есть конечный алфавит, мы бы закодировали пропозициональные буквы некоторым подходящим способом [править: ответы указали, что ответ на вопрос, возможно, не является устойчивым при различные...

12
Существует ли самый сложный DCFL?

Greibach лихо определил язык , так называемую недетерминированную версию о , таких , что любая КЛЛ является обратной морфической изображение . Существует ли подобное утверждение с DCFL, возможно, с некоторыми ограничениями на допустимые морфизмы?D 2 HЧАСHHD2D2D_2ЧАСHH (См., Например, М. Аутеберт,...