We’re rewarding the question askers & reputations are being recalculated! Read more.

Questions tagged [closure-properties]

Questions about operations on objects of some kind that result in objects of the same kind.

15 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
8
votes
1answer
277 views

Is there a strictly non-deterministic one-counter language whose complement is one-counter?

Let $A= \{L \mid L \;\text{is one-counter and \(\bar{L}\) is also one-counter} \}$ Clearly, $\text{Deterministic one-counter} \subseteq A$ Is it the case that $ A = \text{Deterministic one-counter}$...
5
votes
1answer
124 views

Have any natural complexity classes been proven not to be closed under complement?

Many important (non-deterministic) complexity classes like NP are believed not to be closed under complement. But have any of them been proven not to be? I'm sure one could construct some contrived ...
2
votes
0answers
10k views

Is the class of non regular languages is closed under complementation?

This is the question I am asked and I am currently proving it using proof by contradiction something like this: Let's take some language L which is non regular. Let's assume compliment of L i.e. $(L^...
1
vote
0answers
109 views

Is star closure of reverse of grammar equivalent to reverse of closure of that grammar

I need to proof if that it's true or not. $ (G^R)^* = (G^*)^R $ If $G$ is a CFG and $ G = \langle V, \Sigma, \delta, S \rangle $ where $ V $ = Set of Variables or Non-Terminal Symbols $ \Sigma $ = ...
1
vote
0answers
168 views

Unrestricted grammar is closed under intersection

I want to show that unrestricted grammar is closed under intersection and I don't want to use Turing machine or etc. So I think that we have two grammar $G_1$ and $G_2$ that are restricted for example ...
1
vote
0answers
432 views

Is PSPACE closed under the following forall-there-exists construction?

Suppose I have a language $L$ (over alphabet $\Sigma$), such that $$ w \in L \iff (\forall x \in \Sigma^*) (\exists y \in \Sigma^*) P(x,y,w). $$ and I can give a turing machine that decides $P(x,y,w)$ ...
1
vote
0answers
542 views

Are DCFLs closed under concatenation with a regular language?

I have found various opinions saying they are (a link to one is given in D.W.'s comment). However, a proof that DCFLs themselves are not closed under concatenation found here on StackExchange seems to ...
0
votes
0answers
70 views

If $L$ is a regular language then so is $L/a =\{w | wa ∈ L\}$, where $L$ is a language over $\Sigma$ and $a \in \Sigma$

I'm trying to work out a proof by construction that $L/a$ would be regular. $a$ is any final symbol at the end of an accepted string, so I figured the only part of the machine that would have to be ...
0
votes
0answers
43 views

Intersection of decision problems?

Say we have two problems $\Pi_1\in NP$ and $\Pi_2\in coNP$. Where does $\Pi_1\cap\Pi_2$ live?
0
votes
0answers
32 views

Dependency of operations of languages

I've struggled in the closure properties of the general class of languages because I couldn't use any automata concept and grammars. In specific, I'm interested in dependency of operations. (The ...
0
votes
0answers
230 views

Closure under swap operator

I am stuck on this problem and unsure how to proceed. I understand how to show that two languages are closed under regular operators, but not one like the 'swap' operator. Let swap : {a, b}∗ → {a, b}∗...
0
votes
0answers
319 views

CFL Intersection with Regular Language prove

how can i prove the following statement : 1- $L_1\subseteq\Sigma^*$ is CFL and $L_2\subseteq\Sigma^*$ is regular Language, then $L_1$\ $L_2$ is CFL . so i want to know what is the method to prove it ...
0
votes
0answers
229 views

Writing a constructive proof for closure of a regular language under homomorphism

I've spend the last few days searching online for an example of a constructive proof of regular languages being closed under homomorphism, but I have not seen one. I am mostly unsure of how to show ...
0
votes
0answers
169 views

Union, Intersection, Difference, etc. of different types of languages

I am preparing for a competitive exam (GATE) in which questions are asked in Automata about operations among different types of languages. For example, If $L_1$ is recursive & $L_2$ is ...
-1
votes
1answer
119 views

How to show that certain summations are primitive recursive?

If we have a function $g\colon \mathbb{N}^{k+1} \to \mathbb{N}$ which is primitive-recursive. How to show that the function $f\colon \mathbb{N}^{k+1} \to \mathbb{N}$ with $$f(x_1, \dots, x_k , x_{k+...