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.

Filter by
Sorted by
Tagged with
1
vote
4answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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$ ...
0
votes
1answer
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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$ ...
1
vote
1answer
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 ...
0
votes
2answers
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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.
2
votes
1answer
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 ...
0
votes
1answer
210 views

Infinite Union of Recursive language

Question Is Infinite Union of Recursive language is Recursive? I know it is already posted here, but the i am not getting answer also i want to know if my approach is correct. My Approach/Doubt $...
3
votes
2answers
85 views

Proving OP(L) is regular [closed]

I did some searching before I decided to ask this question and there was nothing similar to my question that helped me. So I came to CS stack-exchange for hints. So, I am currently working on a proof ...
2
votes
2answers
2k views

Why are DCFL not closed under concatenation or Union whereas CFL is?

I understand that DCFL they are not closed under concatenation or Union. As without non determinism, PDA cannot decide when to jump to the next one in case of concatenation and without epsilon moves ...
0
votes
2answers
310 views

Is it possible to prove closure of decidable languages under union and intersection, using enumerators?

We can use multi-tape enumerators. (Of course it is not valid to use turing machines albeit the fact that any enumerator has an equivalent TM) What we need is to prove that if $A$ and $B$ are ...
4
votes
1answer
36 views

Closure operator and set of fixpoint

In chapter 2.2 of Giacobazzi, Roberto; Ranzato, Francesco, Uniform closures: Order-theoretically reconstructing logic program semantics and abstract domain refinements, Inf. Comput. 145, No.2, 153-...
3
votes
1answer
64 views

Is $\{ w \in L : wx \in L, \textrm{for some } x \neq \epsilon\}$ a CFG language if $L$ is CFG?

Let $L$ be CFG. Is $\{ w \in L : wx \in L, \textrm{for some } x \neq \epsilon\}$ also CFG?
1
vote
1answer
2k views

Are the undecidable languages closed under complement?

Are the undecidable languages closed under complement? How can the answer be proved?
1
vote
1answer
450 views

If A is NL-complete then complement of A is also NL-complete?

We know that coNL = NL. But, is this also true? If A is NL-complete then complement of A is also NL-complete? I don't see a reason for that it could be true.
2
votes
2answers
194 views

Closure of regular languages under non-contiguous subsequence

Suppose there is a language $L$ on alphabet $Σ$. Now consider the language $$ S(L) = \{x : wxy ∈ L, w, y ∈ Σ^*\} ∪ \{x : w ∈ L,\text{ and $x$ is a subsequence of $w$}\}. $$ How to prove that if $L$ ...
0
votes
0answers
326 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 ...
1
vote
2answers
325 views

CFL Closure Properties prove or disprove for the following languages

I have following statements which I must prove or disprove : 1) Let $L$ be a CFL and $k \in N$ then $L^k$ is also a CFL. 2) $L_1 \subseteq L_2 \subseteq L_3$ are Languages, if $L_1$ and $L_3$ are ...
1
vote
2answers
124 views

Given a regular language, show another language is regular

I was hoping someone could help me with this question, since I'm having trouble determining what approach to take. Let $L \subseteq \{0,1\}^*$ be a regular language. Show the language $\{w \in \{0,1\}...
2
votes
1answer
389 views

Are recursively enumerable languages closed under shuffle?

For languages $L_1, L_2$ over some alphabet $\Sigma$, we define $$ \textit{Shuffle}(L_1, L_2) = \{a_1b_1a_2b_2 \cdots a_nb_n : n \geq 1 \wedge a_1, \ldots , a_n \in L_1 \setminus \{ \varepsilon \} \...
2
votes
1answer
100 views

Operation on a regular language and context free language

Given $L_1$ and $L_2$ over some alphabet: $L_1@L_2 = \{uv \mid u \in L_1 \land v \in L_2 \land |u|=|v|\}$ The question is: if $L_1$ is regular and $L_2$ is context-free, is $L_1@L_2$ context free? ...
0
votes
2answers
210 views

Show that RE is closed against right-quotient

I have a problem that I have no idea how to approach. I've been looking at using mapping reductions, but I can't find a way to apply it. Assume some alphabet $\Sigma$ and two languages $A, B \...
0
votes
1answer
258 views

Proof Check: The class L is closed under concatenation

I want to prove that the class of all Turing machines that use a logarithmic amount of space is closed under concatenation. The basic idea of my proof is this: given a word, to check if it's in $...
3
votes
1answer
468 views

For a regular language $L$, is $\{xy^Rz:xyz\in L\}$ regular?

For a regular language $L$, is $\{xy^Rz:xyz\in L\}$ regular? [Where $w^R$ is the reverse of $w$] My intuition says it is, as for a regular $L$, the languages $L^*$, $\{y: xyz\in L\}$ and $L^R$ are ...
1
vote
0answers
438 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
1answer
855 views

Show that PTIME and PSPACE is closed under Klenee star

How to show that PSPACE and PTIME are closed under Kleene star ? I can only show that NP is closed, but it is easy because we can use non-determinism to guess partition of word. In these two cases I ...
3
votes
2answers
1k views

Closure under the Star Operation

I'm doing my homework, but there's one task that I didn't get the idea. Task: Recall the alternative definition for the star of a language A that we gave just before Theorem 2.3.1. In Theorems 2.3.1 ...
0
votes
1answer
485 views

Finite substitution and regular closure properties

I'm not sure if I get the following definition right: 1.Def: A map $\varphi: \Sigma^{*} \rightarrow 2^{\Delta^{*}}$ is called Substitution iff: $\forall u,v \in \Sigma^{*}: \varphi(uv)=\varphi(u) \...
1
vote
1answer
425 views

Under which operations is the class of non-recursive languages a closure?

I am currently studying turing computability and related problems such as the halting problem with a background in formal languages. I know that the class of recursive (decidable) languages is a ...
0
votes
0answers
232 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 ...
1
vote
1answer
176 views

Question of DFA closure properties?

I have some question about DFA Language properties. Does closure under intersection and complementation imply closure under union? Does closure under intersection and union imply closure under ...
0
votes
2answers
224 views

Is the union between a regular language and a random language also a regular language?

If not can we draw any conclusion about the newly fromed language, the language that represents the union between a regular language and a non regular language (not context free but a truly random ...
3
votes
1answer
383 views

Closure of regular languages to shuffle using closure operations

Given a language: $L = \{\; a_1b_1a_2b_2a_3b_3\dots a_nb_n \mid \forall i: a_i,b_i \in \Sigma, a_1\dots a_n \in L_1\ , b_1\dots b_n \in L_2 \;\}$ Also $L_1, L_2$ are regular languages. Using ...
0
votes
1answer
94 views

Prove the following language is regular using closures

How can I prove this language is regular using just closures and homomorphism? $$ L = \{a_1b_1a_2b_2\dotsm a_nb_n \mid a_i \in L_1 , b_i \in L_2\} $$ and we know $L_1$ and $L_2$ are regular.
0
votes
1answer
289 views

Reflexive transitive closure = (zero or more) Kleene star?

In Alloy Tutorial they denote some reflexive transitive closure with Kleene star saying that they admit zero or more elements at that position. ...
4
votes
1answer
152 views

Inverse Homomorphisms and Kleene star

The exercise is to prove or give a counterexample to the following proposition with $L \subseteq \Gamma^*$ regular and $h: \Gamma \to \Sigma^*$ a homomorphism. Is there any regular language $L'$ such ...
2
votes
2answers
821 views

Proof that the language $ww^R$ is not regular without using the pumping lemma

I am breaking my head over this. Let the alphabet $A$ be given by $A = \{a,b,c\}$ and let $$L = \{ww^R \mid w \in A^* \}.$$ Prove that the language $L$ is not regular without using the pumping ...
0
votes
1answer
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 ...
3
votes
2answers
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 ...
1
vote
1answer
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 ...
6
votes
2answers
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 ...
-2
votes
1answer
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?
2
votes
1answer
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 ...
-1
votes
1answer
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 ...
4
votes
1answer
470 views

Prove that PP is closed under complement

I found this proof in Wikipedia, but one of the most important steps in it doesn't make any sense to me. I'll explain: By the definition of PP there is a polynomial-time probabilistic algorithm ...
3
votes
2answers
808 views

Showing Regular Languages are closed under removal of rightmost character

"Show that if L is a regular language without the empty string, then the language in which the rightmost symbol of every string in is removed is also regular." I tried going by closure properties of ...