Вопросы с тегом «closure-properties»

Вопросы об операциях с объектами какого-либо типа, в результате которых создаются объекты одного типа.

20
Являются ли контекстно-свободные языки в

Языки без контекста не закрыты в дополнении, мы это знаем. Насколько я понимаю, контекстно-свободные языки, которые являются подмножеством a*б*a∗b∗a^*b^* для некоторых букв а , бa,ba,b , закрыты в дополнении (!?) Вот мой аргумент. Каждый CF язык LLL имеет полулинейный образ Париха π( L ) = { ( m ,...

16
Доказательство замыкания при обращении языков, принятых автоматами min-heap

Это дополнительный вопрос этого . В предыдущем вопросе об экзотических конечных автоматах Алекс тен Бринк и Рафаэль обратились к вычислительным возможностям особого вида конечного автомата: автоматов с минимальной кучей. Они смогли показать, что набор языков, принимаемых такими машинами ( HALHALHAL...

14
Всегда ли наборы до и после для контекстно-свободных грамматик всегда контекстно-свободны?

Пусть GGG - не зависящая от контекста грамматика. Строка терминалов и нетерминалов из GGG называется быть сентенциальная формой из GGG , если вы можете получить его путем применения постановки GGG нуля или более раз для начального символа SSS . Пусть SF(G)SF⁡(G)\operatorname{SF}(G) множество...

13
Закрытие против правильного отношения с фиксированным языком

Мне бы очень понравилась ваша помощь в следующем: Для любого фиксированного мне нужно решить, есть ли замыкание под следующими операторами: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...

12
Операции, при которых класс неразрешимых языков не закрыт

Существуют ли неразрешимые языки, так что их язык объединения / пересечения / сцепления является разрешимым? Какова физическая интерпретация такого примера, потому что в целом неразрешимые языки не закрыты под этими операциями? Что мы можем сказать о закрытии клини? У нас тоже есть примеры для...

12
Докажите, что дополнение к

Я хочу доказать, что дополнение не является регулярным, используя свойства замыкания.{ 0N1N∣ n ≥0 }{0N1N|N≥0}\{0^n1^n \mid n \geq{} 0\} Я понимаю, что лемму прокачки можно использовать, чтобы доказать, что не является регулярным языком. Я также понимаю, что обычные языки закрыты в рамках операции...

12
Является ли регулярным , если

Если регулярно, следует ли из этого, что A регулярно?A2A2A^2AAA Моя попытка доказательства: Да, для противоречия предположим, что не является регулярным. Тогда 2 = ⋅ .AAAA2= A ⋅ AA2=A⋅AA^2 = A \cdot A Поскольку конкатенация двух нерегулярных языков не является регулярной, не может быть регулярной....

12
Союз регулярных языков, который не является регулярным

Я сталкивался с таким вопросом: «Приведите примеры двух обычных языков, которые их объединение не выводит на обычном языке». Это довольно шокирует меня, потому что я считаю, что обычные языки закрыты для объединения. Что означает для меня, что, если я возьму два обычных языка и объединю их, я...

11
Что является дополнением к контекстно-свободным языкам?

Можно понять ваш вопрос двумя способами, согласно определению «дополнение КЛЛ». Случай A: Дополнение к CFL - это класс всех языков, которых нет в CFL. Формально, В этом случае намного больше, чем , у него даже есть языки, которых нет в и т. Д. Но, возможно, это не то, что вы имели в...

11
Легкое доказательство того, что контекстно-зависимые языки закрываются при циклическом сдвиге

Циклический сдвиг (также называемый поворот или конъюгации ) из языка определяется как { у х | х у ∈ L } . Согласно википедии (и здесь ), контекстно-свободные языки закрыты для этой операции со ссылками на статьи из Oshiba и Maslov. Есть ли простое доказательство этого факта?LLL{yx∣xy∈L}{yx∣xy∈L}\{...

10
Создание всех контекстно-свободных языков из набора базовых языков и свойств замыкания?

Один из способов рассмотрения регулярных выражений - это конструктивное доказательство следующего факта: можно создавать регулярные языки, начиная с небольшого набора языков и комбинируя их с помощью небольшого фиксированного набора свойств замыкания. В частности, если мы начнем с пустого языка,...

9
Если

Я застрял, решая следующее упражнение: Докажите, что если зависит от контекста, а R регулярно, то L / R = { w ∣ ∃ x ∈ RLLLRRR (т.е.правый фактор) не зависит от контекста.L/R={w∣∃x∈Rs.twx∈L}L/R={w∣∃x∈Rs.twx∈L}L / R = \{ w \mid \exists x \in R \;\text{s.t}\; wx \in L\} Я знаю , что должен...