Хорошо известно, что дополнение к зависит от контекста. Но как насчет дополнения ?{ww∣w∈Σ∗}{ww∣w∈Σ∗}\{ ww \mid w\in \Sigma^*\}{www∣w∈Σ∗}{www∣w∈Σ∗}\{ www \mid w\in
Я понимаю следующие утверждения, чтобы быть правдой: Два разных вывода строки в данном CFG могут иногда приписывать строку одному и тому же дереву разбора. Когда есть производные некоторой строки в данном CFG, которые приписывают различные деревья разбора, CFG является неоднозначным. Некоторые...
Пусть будет дано число . Рассмотрим следующий язык: 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 ) - это...
Рассмотрим произвольную контекстно-свободную грамматику гGG по алфавиту { 0 , 1 ,0¯¯¯,1¯¯¯}{0,1,0¯,1¯}\lbrace 0,1,\overline{0} ,\overline{1} \rbrace, К произведениям этой грамматики добавьте два фиксированных неконтекстно-свободных произведения.пPP: 0¯¯¯0 → ϵ0¯0→ϵ\overline{0} 0 \rightarrow \epsilon...
Каково соотношение неоднозначных CFG к всем CFG ? Поскольку оба множества счетно бесконечны, соотношение не является четко определенным. Но как насчет асимптотической плотности : limn↦∞# ambiguous CFG of size<n# CFG of size<nlimn↦∞# ambiguous CFG of size<n# CFG of size<n\lim_{n \mapsto...
Хотелось бы знать, почему для распознавания контекстно-свободных языков работают только недетерминированные автоматы push-down (DPA = NPDA). Почему детерминированные автоматы (DPDA) не распознают такие...
Есть ли какие-то результаты по решению задач формальных языков с использованием математического анализа, непрерывной математики. Например, решение проблемы непустоты пересечения для языка без контекста и обычного...
Есть ли перестановки π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 является...