# Questions tagged [closure-properties]

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

306 questions
Filter by
Sorted by
Tagged with
42 views

795 views

### Is the union of two non-regular context-free languages always non-regular?

I had this question in my HW: Prove of disprove: If $L_1$ and $L_2$ are non-regular context free languages then $L_1 ∪ L_2$ is not regular. My intuition is that it is wrong. I thought about the ...
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$ = ...
140 views

209 views

### How to prove that a transformed language is regular using an NFA

I am trying to prove that if a language $L$ of binary strings (i.e. a subset of *) is regular then so is the transformed language $plus (L)$ consisting of ...
234 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}∗...
98 views

### Does this proof work for infinite regular languages

My proof was deemed false because it does not work for infinite regular languages, but I don't understand why. Prove: "If we remove one string from any nonempty regular set, the resulting set is ...
36 views

### Why is it not obvious $coNP = NP$? [duplicate]

I can't find a mistake in reasoning : Let $M_1$ NTM (Non Deterministic Turing Machine) that solves $L$ in polynomial-time. So then $x \in L \Leftrightarrow M_1(x) = 1$. Finally our new NTM $M_2$ that ...
578 views

### Closure of Turing-recognizable languages under homomorphism

I've proven that the Turing-recognizable languages are closed under concatenation and I need to show that they are closed under homomorphism. But what's really the difference? Doesn't closure under ...
10 views

### Choose a specific regular language to prove a language is not regular [duplicate]

I've tried a few tricky languages such as D = { w | w has an equal number of occurences of 01 and 10 as substrings} but I don't have the means to prove this one as being not regular (and I cannot ...
26 views

### Give an example of a language where both L and ¬L is not semidecidable? [duplicate]

I know ¬H is not semidecidable so I was thinking of creating a language that combines both H and ¬H. Therefore L would be undecidable for ¬H and ¬L would be undecidable for H. Is this a proper ...
172 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 ...
453 views

### What happens during the DFA reversal construction if the initial state is final?

The steps in reversal of DFA are :- Make final state as initial state. If there are more than 1 final state, then make a new start state with epsilon transitions to these states. Change all initial ...
I found online solutions which prove the closure of NP under intersection in the following way: given machines $M_1,M_2$ for accepts nondeterministically languages $L_1,L_2$, we construct the ...
How do you define $\oplus P\cap PP$? $L\in\oplus P$ iff $\exists\mbox{ NTM }M:\forall x,\#acc_M(x)\mod2\equiv0$. $L\in PP$ iff $\exists\mbox{ NTM }M:\forall x,\#acc_M(x)>\#rej_M(x)$. Consider ...