Является ли язык { } не зависит от контекста или нет?aibjck | i≠j,i≠k,j≠kaibjck | i≠j,i≠k,j≠ka^{i}b^{j}c^{k} ~|~ i \neq j, i \neq k, j \neq k Я понял, что столкнулся почти со всеми вариантами этого вопроса с различными условиями относительно отношений между i, j и k, но не с этим. Я думаю, что это...
В качестве стороннего проекта я пишу язык с использованием Python. Я начал с использования клона flex / bison под названием Ply, но столкнулся с трудностями, которые я могу выразить с помощью этого стиля грамматики, и мне не интересно взламывать свой язык из-за несоответствия импеданса с...
Насосная лемму для регулярных языков можно доказать, рассматривая конечный автомат, распознающий язык изучал, выбирая строку с длиной больше , чем его число состояний, и применением принципа Дирихля. Однако прокачивающая лемма для языков без контекста (а также лемма Огдена, которая является...
Хорошо известно, что проблема эквивалентности неразрешима для общих контекстно-свободных языков. Тем не менее, все доказательства этого факта, о которых я знаю, похоже, включают в себя некоторые неоднозначные контекстно-свободные грамматики. По этой причине я хотел бы спросить, известно ли,...
Это переформулировка программ грамматики? предыдущий вопрос от Vag и множество предложений от комментаторов. Каким образом грамматика может рассматриваться как спецификация модели вычислений? Если, например, мы берем простую контекстно-свободную грамматику, такую как G ::= '1' -> '0' '+' '1'...
Рассмотрим следующий естественный вопрос: для какого конечного языка наименьшая не зависящая от контекста грамматика порождает L ?LLLLLL Мы можем сделать вопрос более интересным, указав последовательность языков , например, L n - это множество всех перестановок { 1 , … , n } : интуитивно, CFG для L...
Пусть будет контекстно-свободным языком. Определить , чтобы быть пре- и постфиксное замыканием , другими словами, содержит все «с префиксами и postfixes, и , следовательно сам по себе. Мой вопрос: если зависит от контекста и имеет не однозначную грамматику, то же самое верно для ?p p c ( L ) L p p...
Пусть будет дано число . Рассмотрим следующий язык: 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 ) - это...
Есть ли перестановки π1,π2π1,π2\pi_1,\pi_2 и полиномиальный размер (в |w|=n|w|=n|w|=n) контекстно-бесплатная грамматика, описывающая конечный язык {wπ1(w)π2(w)}{wπ1(w)π2(w)}\{w \pi_1(w) \pi_2(w)\} по алфавиту {0,1}{0,1}\{0,1\}? ОБНОВЛЕНИЕ: для одной перестановки ππ\pi это возможно. ππ\pi является...
Каково соотношение неоднозначных CFG к всем CFG ? Поскольку оба множества счетно бесконечны, соотношение не является четко определенным. Но как насчет асимптотической плотности : limn↦∞# ambiguous CFG of size<n# CFG of size<nlimn↦∞# ambiguous CFG of size<n# CFG of size<n\lim_{n \mapsto...
Мне интересна компьютерная музыка, где есть подходы к обработке музыкальных произведений как предложений в порождающих грамматиках или L-системах. Вместо сочинения можно было бы указать грамматику и позволить компьютеру генерировать музыку. Например, Йельская группа вокруг покойного Пола Худака...