Следующая проблема разрешима: Имеет ли контекстная грамматика , ?GGGL(G)=∅L(G)=∅L(G) = \varnothing Следующая проблема неразрешима: Имеет ли контекстно-свободная грамматика GGG , L(G)=A∗L(G)=A∗L(G) = A^{\ast} ? Существует ли характеристика контекстно-свободных языков MMM с разрешимым равенством...
Этот вопрос связан с недавним вопросом по Janoma . Фон В программировании ограничений, A регулярное глобальное ограничение ccc над областью DDD представляет собой пару (s,M)(s,M)(s, M) с sss кортежем переменных (о масштабе) и MMM ДКА над областью DDD . Назначение θθ\theta для sss удовлетворяет ccc...
РЕДАКТИРОВАТЬ (Тара B): Я все еще был бы заинтересован в ссылке на доказательство этого, так как я должен был доказать это сам для моей собственной статьи. Я ищу доказательство теоремы 4, которое появляется в этой статье: Бесконечная иерархия пересечений контекстно-свободных языков Лю и Вейнера....
Я понимаю следующие утверждения, чтобы быть правдой: Два разных вывода строки в данном CFG могут иногда приписывать строку одному и тому же дереву разбора. Когда есть производные некоторой строки в данном CFG, которые приписывают различные деревья разбора, CFG является неоднозначным. Некоторые...
Пусть язык и f : Σ ⋆ × Σ ⋆ → Σ ⋆ функция по двум параметрам со свойством, которое для всех x и y , f возвращает элемент из L тогда и только тогда, когда x и y являются элементами из L :LLLе: Σ⋆× Σ⋆→ Σ⋆f:Σ⋆×Σ⋆→Σ⋆f\colon {\Sigma^\star}\times\Sigma^\star\to\Sigma^\starxxxyyyfffLLLxxxyyyLLL...
Рассмотрим следующую проблему: Для двух строк x, y решите, существует ли строковый гомоморфизм f такой, что f (x) = y. Легко показать , что эта проблема находится в . Есть ли что-то еще, что мы можем сказать об этой проблеме? Например, это в c o N P или даже в P ?NPNPNPcoNPcoNPcoNPPPP Эта проблема...
Система векторного сложения (VAS) - это конечный набор действий . - это набор разметок . В рабочем цикле является непустое слово маркировки й . Если такое слово существует , мы говорим , что является достижимым из .A ⊂ Z d A⊂ZdA \subset \mathbb{Z}^dN dNd\mathbb{N}^dm 0 m 1 … m nm0m1…mnm_0 m_1\dots...
Детерминированные контекстно-свободные языки (DCFL) и языки визуального нажатия (VPL) являются наборами формальных языков между контекстно-свободными языками (CFL) и обычными языками (REG). Есть ли удобочитаемая нотация, которая может быть выражена в простом ASCII-формате, например Backus-Naur-Form...
Привет всем, в настоящее время я пытаюсь найти твердую тему магистерской диссертации, относящуюся к некоторой отрасли теории автоматов или связанной с формальными языками. Я пытаюсь выработать несколько хороших идей для приемлемой темы, чего-то амбициозного, но в то же время выполнимого. Любые...
Я пытаюсь составить таксономию алгоритмов для преобразования регулярных выражений в автоматы, чтобы выполнить некоторые эмпирические тесты их свойств сложности в определенных областях. Я знаю несколько «больших» имен, например: Томпсон «Алгоритм поиска регулярных выражений», Томпсон, 1968 Глушков...
Постановка задачи : Позволять MMM быть (потенциально недетерминированным) автоматом и AA\cal Aбыть его входным алфавитом. Есть ли словоw∈A∗w∈A∗w \in \cal A^* улица |w|≤k|w|≤k|w| \leq k что принято MMM ? Эта проблема NP-полная? Было ли это изучено? Есть ли алгоритм, позволяющий найти такое...
Пусть будет контекстно-свободным языком. Определить , чтобы быть пре- и постфиксное замыканием , другими словами, содержит все «с префиксами и postfixes, и , следовательно сам по себе. Мой вопрос: если зависит от контекста и имеет не однозначную грамматику, то же самое верно для ?p p c ( L ) L p p...
Неизвестно, является ли или , гдеP⊆CSLP⊆CSLP\subseteq CSLP⊈CSLP⊈CSLP\not\subseteq CSL PPP - это множество всех языков, разрешимых за полиномиальное время на детерминированной машине Тьюринга, и CSLCSLCSL - это класс контекстно-зависимых языков, который, как известно, эквивалентен...
Рассмотрим непустой язык двоичных строк длины . Я могу описать булевой схемой с входами и одним выходом, так что истинно тогда и только тогда, когда : это хорошо известно.LLLnnnLLLCCCnnnC(w)C(w)C(w)w∈Lw∈Lw \in L Тем не менее, я хочу представлять с булевой схемой с выходами и определенным...
Детерминированный автомат называется k- локальным при k > 0, если для каждого w ∈ X k множество { δ ( q , w ) : q ∈ Q } содержит не более один элемент. Интуитивно это означает, что если слово w длины k приводит к состоянию, то это состояние уникально или сказано иначе, чем произвольное слово...
DFA или NFA читает входную строку с одной головой, двигаясь слева направо. Кажется естественным задаться вопросом о конечных автоматах, которые имеют несколько головок , каждая из которых движется через вход слева направо, но не обязательно в том же месте на входе, что и другие. Определим конечный...
Этот вопрос касается того, существуют ли какие-либо известные обратимые тарпиты Тьюринга, где «обратимый» означает в смысле Аксельсена и Глюка , а «тарпит» является гораздо более неформальным понятием (и, возможно, не очень удачным выбором слова), но я сделаю все возможное, чтобы объяснить, что я...
Каков стандартный подход к минимизации Büchi-Automata (или также Müller-Automata)? Перенос обычного метода из конечных слов, то есть установка двух состояний равными, если слова «заканчиваются» из принятых состояний одинаковы, не будут работать. Например, рассмотрим Büchi-Automoton, принимающий все...
Существует открытая проблема в формальных языках, известная как проблема разделения; который кратко изложен как заданные две отдельные строки длины , насколько большой DFA требуется, чтобы «разделить» их, то есть принять одну строку, но отклонить другую.nnn Вот некоторые соответствующие документы 1...
Пусть будет дано число . Рассмотрим следующий язык: 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 ) - это...