Неизвестно, является ли или , гдеP⊆CSLP⊆CSLP\subseteq CSLP⊈CSLP⊈CSLP\not\subseteq CSL PPP - это множество всех языков, разрешимых за полиномиальное время на детерминированной машине Тьюринга, и CSLCSLCSL - это класс контекстно-зависимых языков, который, как известно, эквивалентен...
DFA или NFA читает входную строку с одной головой, двигаясь слева направо. Кажется естественным задаться вопросом о конечных автоматах, которые имеют несколько головок , каждая из которых движется через вход слева направо, но не обязательно в том же месте на входе, что и другие. Определим конечный...
По моему опыту, контекстно-зависимые языки и линейно-ограниченные автоматы часто пропускаются или зацикливаются на курсах теории вычислимости, и даже не учтены в некоторых заметных учебниках, хотя конечным автоматам и автоматам с выталкивающими функциями уделяется много внимания. Конечно, должна...
Есть ли перестановки π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 является...
Парсеры диаграмм могут быть реализованы на основе нормальной формы Хомского или непосредственно на основе правил производства. Предположим на данный момент, что у нас есть анализатор диаграмм CYK, который использует нормальную форму Хомского. Бинаризация не определяется однозначно. Влияет ли это на...
Мне было интересно, какие наборы языков генерируются ограничениями регулярных выражений. Предположим, что все ограничения имеют постоянный символ для каждого элемента и конкатенации. Тогда восемь классов могут быть сформированы наличием или отсутствием дополнения / отрицания, изменения /...
Я изучаю алгебраическую теорию разбора. Моя первая проблема - это определение примеров полукольца, специфичных для теории формального языка. Вот попытка построить два примера. 1 При заданной грамматике CNF элементами полукольца являются наборы терминальных и нетерминальных символов с операциями: i)...
Хотелось бы знать, почему для распознавания контекстно-свободных языков работают только недетерминированные автоматы push-down (DPA = NPDA). Почему детерминированные автоматы (DPDA) не распознают такие...
Каково соотношение неоднозначных CFG к всем CFG ? Поскольку оба множества счетно бесконечны, соотношение не является четко определенным. Но как насчет асимптотической плотности : limn↦∞# ambiguous CFG of size<n# CFG of size<nlimn↦∞# ambiguous CFG of size<n# CFG of size<n\lim_{n \mapsto...
Позволять 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(...
Существует множество различных моделей для определения преобразований между языками. Конечные преобразователи состояния и определяемые MSO преобразования графов над строковыми графами - это те два, с которыми я лучше всего знаком. Мы знаем, что двухсторонние конечные преобразователи состояния...
Есть ли какие-то результаты по решению задач формальных языков с использованием математического анализа, непрерывной математики. Например, решение проблемы непустоты пересечения для языка без контекста и обычного...