Я ищу эффективный алгоритм для следующей задачи или доказательства NP-твердости. Пусть Σ - множество, а A ⊆ P ( Σ ) - множество подмножеств Σ . Найдите последовательность w ∈ Σ ∗ наименьшей длины, такую, что для каждого L ∈ A найдется такое k ∈ N , что { w k + i ∣ 0 ≤ i < | L | } = Л...
Есть ли какой-нибудь естественный или заметный способ связать или связать математические группы и формальные языки CS или какую-то другую основную концепцию CS, например машины Тьюринга? Я ищу ссылки / приложения. Однако обратите внимание, что я знаю о связи между полугруппами и языками CS (а...
Проблема Нет простого способа получить перестановку с помощью регулярного выражения. Перестановка: Получение слово ( «ААБК») в другом порядке, без изменения числа или рода писем.w=x1…xnw=x1…xnw=x_1…x_n Regex: Регулярное выражение. Для подтверждения: «Перестановки регулярных выражений без...
Мне бы очень понравилась ваша помощь в следующем: Для любого фиксированного мне нужно решить, есть ли замыкание под следующими операторами:L2L2L_2 Ar(L)={x∣∃y∈L2:xy∈L}Ar(L)={x∣∃y∈L2:xy∈L}A_r(L)=\{x \mid \exists y \in L_2 : xy \in L\} .Al(L)={x∣∃y∈L:xy∈L2}Al(L)={x∣∃y∈L:xy∈L2}A_l(L)=\{x \mid \exists...
LLL - обычный язык над алфавитом . Левый фактор относительно - это язык Σ={a,b}Σ={a,b}\Sigma = \{a,b\}LLLw∈Σ∗w∈Σ∗w \in \Sigma^*w−1L:={v∣wv∈L}w−1L:={v∣wv∈L}w^{-1} L := \{v \mid wv \in L\} Как я могу доказать, что...
Я изучаю формальные языки и системы баз производства (системы баз правил), и меня немного смущает вопрос, почему эти два слова «производство» и «правило» означают одно и то же во многих контекстах компьютерных наук. В английском языке они не означают одно и то же. Я не являюсь носителем английского...
Похоже, что «Основные регулярные выражения», как определено в POSIX.1-2008 , не поддерживают чередование a|b(хотя некоторые реализации grep распознают экранированную версию \|). Поскольку регулярные языки по определению замкнуты относительно объединения, означает ли это, что POSIX BRE обладает...
Тем не менее, многие «знаменитые» неразрешимые проблемы, по крайней мере, полуразрешимы, а их дополнение неразрешимо. Одним из примеров, прежде всего, может быть проблема остановки и ее дополнение. Тем не менее, кто-нибудь может привести пример, в котором проблема и ее дополнение неразрешимы и не...
Я думал о грамматиках для чувствительных к индендангу языков, и похоже, что грамматики CF сработают, если их объединить с параметрами. В качестве примера рассмотрим этот фрагмент для упрощенной грамматики Python в ANTLR-подобном формате: // on top-level the statements have empty indent program :...
Выполняя текущее задание по курсу формальных языков и автоматов, я как бы застрял на упражнениях с унарными языками (надеюсь, это правильный термин), то есть на языках, которые основаны на одной букве. Я не хочу спрашивать о конкретных упражнениях, а о гораздо более общей гипотезе, с которой я...
Я сталкивался с таким вопросом: «Приведите примеры двух обычных языков, которые их объединение не выводит на обычном языке». Это довольно шокирует меня, потому что я считаю, что обычные языки закрыты для объединения. Что означает для меня, что, если я возьму два обычных языка и объединю их, я...
Пусть регулярный, регулярный, не регулярный. Покажите, что не является регулярным, или приведите контрпример.L1L1L_1L1∩L2L1∩L2L_1 \cap L_2L2L2L_2L1∪L2L1∪L2L_1 \cup L_2 Я попробовал это: Посмотрите на . Это регулярно. Для этого я могу построить конечный автомат: регулярный, регулярный, поэтому...
Я понимаю, что контекстно-свободные грамматики могут использоваться для представления контекстно-свободных языков. Это может иметь неоднозначность. У нас также есть нормальные формы, такие как нормальная форма Хомского и Грейбаха . Я не мог понять необходимость этого. Почему они важны в теории...
Скажем, L⊆{0}∗L⊆{0}∗L \subseteq \{0\}^* . Тогда как мы можем доказать, что L∗L∗L^* регулярно? Если LLL регулярно, то, конечно, L∗L∗L^* также регулярно. Если LLL конечно, то оно регулярно и снова L∗L∗L^* регулярно. Также я заметил, что для L={0p∣p is a prime}L={0p∣p is a prime}L = \{0^p \mid p...
Мне интересно, какова сложность определения пустоты для двусторонних DFA? То есть конечные автоматы, которые могут двигаться назад на своей ленте ввода только для чтения. Согласно Википедии, они эквивалентны DFA, хотя эквивалентный DFA может быть экспоненциально больше. Я обнаружил сложность...
Я наткнулся на этот рисунок, который показывает, что контекстно-свободные и регулярные языки являются (правильными) подмножествами эффективных задач (предположительно ). Я прекрасно понимаю, что эффективные проблемы являются подмножеством всех разрешимых проблем, потому что мы можем их решить, но...
Если регулярно, следует ли из этого, что A регулярно?A2A2A^2AAA Моя попытка доказательства: Да, для противоречия предположим, что не является регулярным. Тогда 2 = ⋅ .AAAA2= A ⋅ AA2=A⋅AA^2 = A \cdot A Поскольку конкатенация двух нерегулярных языков не является регулярной, не может быть регулярной....
Я хочу доказать, что дополнение не является регулярным, используя свойства замыкания.{ 0N1N∣ n ≥0 }{0N1N|N≥0}\{0^n1^n \mid n \geq{} 0\} Я понимаю, что лемму прокачки можно использовать, чтобы доказать, что не является регулярным языком. Я также понимаю, что обычные языки закрыты в рамках операции...
Вот проблема: Докажите, что одноленточные машины Тьюринга, которые не могут писать на той части ленты, которая содержит входную строку, распознают только обычные языки. Моя идея состоит в том, чтобы доказать, что этот конкретный TM эквивалентен DFA. Использовать эту ТМ для симуляции DFA очень...
Я хочу преобразовать введенное пользователем регулярное выражение в NFA, чтобы потом можно было запускать NFA для строки для сопоставления. Какой минимальный компьютер можно использовать для разбора регулярных выражений? Я предполагаю, что это должен быть автомат с принудительной передачей, потому...