A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

# Questions tagged [closure-properties]

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

308 questions
Filter by
Sorted by
Tagged with
912 views

### Why can't we say that NP is closed under complement given that we can say it is closed under intersection

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 ...
56 views

### On clarification of intersection of classes definition

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 ...
57 views

### Using closure properties to show that $L_1=\{a^lb^mc^m|l,m\ge 0\} \cup L(b^*c^*)$ is regular or not

i'm trying to figure out whether this Union $\left [ L_1=\{a^lb^mc^m|l,m\ge 0\} \cup L(b^*c^*)\right]=K$ is regular or not, now since regular languages are closed under intersection, so i assume $K$ ...
82 views

### Closure of a CFL under specific operation

Consider the following operation on language $L$: $\mathrm{inv}(L) = \{ xy^Rz \mid x,y,z\in \Sigma^*, xyz\in L \}$ I understand that if $L$ is regular, then $\mathrm{inv}(L)$ is regular too, and ...
265 views

### If $L$ is recursively enumerable (or recursive) then so is $L′$

Given a language $L \subset \{0, 1 \}^*\#\{0, 1 \}^*$ and a language $$L'=\{u \in \{0,1\}^* | \textrm{ There is a word }w \in \{0,1\}^* \text{, so } u\#w \in L\}$$ Prove or disprove: If $L$ is ...
369 views

### Reverse the input and output of a Mealy machine

Given a Mealy machine $M$, is it possible to construct another Mealy machine $M'$ that generates the reverse outputs from the reverse inputs, and if so, how? That is, for each string $s$, $M(s) = t$ ...
455 views

### Constructing a decider for a language

I'm confused about the idea of constructing a decider for a language and i need some help with it. For example, if i have an enumerator M1 for a language L and another enumerator M2 for the ...
211 views

### Are the regular languages closed against injecting single letters?

Let $L$ an arbitrary regular language and $\qquad L_2 = \{uav : uv \in L\}$. Am I correct to say that this language is not regular by saying: $L$ has an even number of $a$'s. So $u$ and $v$ have ...
503 views

### Complement of DPDA

I read that we can find complement of DPDA by just complementing(toggling) the states of DPDA. Why can't we do the same with NPDA ? Also is DCFL closed under complement just because we can toggle ...
358 views

### If L1 ⊆ L2 and L2 is regular, then L2 − L1 is regular [closed]

I'm having trouble being 100% sure about this answer. I feel like it's false but I'm having trouble coming up with a complete answer. Can someone explain this step by step? Thanks.
752 views

### Closure property of recursively enumerable language

I read that recursively enumerable languages are closed under intersection but not under set difference. We know that, $A \cap B = A - ( A - B)$. Now for LHS (left-hand side) to be closed under ...
210 views

389 views

266 views

### How do I prove that a language is regular? [duplicate]

In order to prove that the following language is regular, would I use a pumping lemma? The set $A$ of all strings that are substrings of some string in $L$, where $L \subseteq\Sigma^*$. $L$ Must be ...
3k views

### Show that NP is closed under concatenation

Show that NP is closed under concatenation. This is a homework problem and I would appreciate some guidance. I began by saying the following: Let $A$ and $B$ exist in NP. Let $V_1$ and $V_2$ be ...
96 views

### If $R,F \cap R, F \cap \overline{R}$ are regular, is $F$ regular?

Let $R \in REG$. Is it true that if $F\cap R \in REG$ and $F \cap \overline{R} \in REG$ then $F \in REG$? I took $R = \Sigma^{\ast}$ and because $F\cap R \in REG$, $F$ must be regular. Is this the ...
803 views

### Should two DFAs be complete before making an intersection of them?

In the slides given by my teacher, the third automaton is the product of the first two: I tried to do the product myself by doing the transition table of both automata at the same time. I got stuck ...
121 views

### Proving that REG is reverse-closed against inverse homomorphism

prove/disprove If inverse homomorphism of languages is regular then languages is also regular? Let $h$ be a homomorphism , if $h^{-1}(L)$ is regular then $L$ is also regular?
3k views

### How to show that a language {w|ww^R in A} is regular, A being regular?

Been working on my homework and I've been stuck on a question for over a week now. Not really asking for a solution but if someone could point me towards the right direction that would be great, as I ...
514 views

### Prove a language is regular - Regular language of 0's and 1's [duplicate]

I'm new to regular languages and I've been struggling to solve one for a while. The question is: If there exists a regular language L1 which has an alphabet {0,1}, prove that L2 is also a regular ...