# Questions tagged [closure-properties]

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

339 questions
Filter by
Sorted by
Tagged with
67 views

### Why are Recursive Enumerable Languages closed under union?

Union of two REL is closed under union. I don't understand how is it closed. I followed this link. The have stated: Here the trick is to simulate both M1 and M2 “simultaneously”. In other words, we ...
58 views

### Is there distinction between $(C/poly)\cap(coC/poly)$ and $(C\cap coC)/poly$?

Let $C$ be an uniform complexity class for example $NL$ or $NP$. Is there distinction between $(C/poly)\cap(coC/poly)$ and $(C\cap coC)/poly$?
64 views

### Closure of context-sensitive languages under inverse language substitution

We define language substitution for a Context-Sensitive Language (CSL) $S$ over an alphabet $\Sigma$ is a map from $\Sigma$ into CSL's, for example: $f(abc) = L_1(a) L_2(b) L_3(c)$ such that (I guess) ...
49 views

41 views

### Prove by contradiction that the language with unequal number of a's and b's is not regular

Consider the language $$L = \{w \mid w \text{ has an unequal number of a’s and b’s}\}$$ where Σ = {a, b}. Prove that L is not regular. Hint: Try proof by contradiction. Would this be the right Answer: ...
33 views

### Classes of Functions Closed Under Polynomial Composition - Papadimitriou Exercise 7.4.4

I am studying Computation complexity using Papadimitrious's book: "Computational Complexity". I am trying to do Problem 7.4.4: "Let $C$ be a class of functions from nonnegative ...
45 views

### Definition of Closed Under Left Polynomial Composition

I am studying Computation complexity using Papadimitrious's book: "Computational Complexity". While doing Problem 7.4.4, I came across the definition of what it means for a class of ...
771 views

### Given L is a regular language, prove that Perm(L) is Context-Free

Given a regular language $L$ defined over $\Sigma = \{0, 1\}$. We define a new language $$Perm(L) = \{w \mid \exists x \in L, w \in perm(x)\},$$ where $perm(x)$ is the set of all permutations of the ...
44 views

### Language equivalency for modified CFG closed over intersection

Suppose "CFG+" was created, where it is identical to standard context-free grammars in every way, but rather than rules being limited to unions, was also closed over intersections, both ...
42 views

### Show that the Language is irregular

I was solving some problem from past test, there was this question: Use the closure property of regular language to show the language $L$ is not regular $$L =\{ a^3 b^n c^{n-3} \mid n>3\}$$ I ...
143 views

### Regular languages closed under prefix operation

Suppose that $D$ is a regular language over an alphabet $A$. How can I prove that the following language is also regular? $$\mathrm{LANGUAGE}_2(D) := \{ d \mid d,t \in A^* \text{ and } dt \in D \}$$ ...
40 views

### Using closure properties, prove that $L=\{a^kb^ra^m|k,r,m\ge0 \text{ and } m=k+r\}$ is not regular

I'm trying to prove that $L=\{a^kb^ra^m|k,r,m\ge0 \text{ and } m=k+r\}$ is not regular and, although it's trivial to prove it via pumping lemma, I'm having troubles trying to find a way to prove it ...
85 views

### Which closure properties are always valid between regular, context-free and non context-free languages?

I am making a scheme that respresents some closure properties (union, intersection, complement and concatenation) for regular languages, context-free languages, decidable languages and RE languages. ...
36 views

### Prove that the class of regular languages is closed under the Kleene + operation. That is, show that if L is regular, then so is $L^{+}$

This is my attempt at a proof: Let $E$ be a $REGEX$ accepting $L$. We claim the $REGEX$ $E^{'} = E^{+}$ accepts L. i.e. $L(E^{+}) = (L(E))^{+}$ $L^{+}$ is regular since there is a $REGEX$ $E^{+}$ ...
28 views

### How do i prove this language is regular? [duplicate]

I have this language {0+1+0+} and i need to prove it is regular,i had the idea to use the closure properties but i can find any regular languages to unify perhaps.Any ideas?
35 views

### Relationship between Kleene Star of a subset of regular language and the regular language

If $L(R_1) \subseteq L(R_2) \subseteq L(R_3)$ then $L(R_1)^* \subseteq L(R_2)^* \subseteq L(R_3)^*$. Does this also imply that $L(R_1)^* \subseteq L(R_3)$?
37 views

338 views

### Strings of infinite length?

Suddenly a thought came to my mind and I thought of resolving it as follows. We know that: String is a finite sequence of symbols from an alphabet $\Sigma$ i.e. we cannot have an infinite sequence ...
94 views

121 views

### DSPACE(f(n)) closed under complement

I think you can create the complementary language that is an element of DSPACE($f(n)$), where $f(n) \geq \log(n)$ by adding a step to the algorithm that reverses the answer. By that the function $f(n)$...
728 views

### Proving that L is not regular using closure properties

I need to show that the following language is not regular. $$L = \{\ ab^jc^j\ |\ j \geq 0\ \}\ \cup\ \{\ a^ib^jc^k\ |\ i, j, k \geq 0 \ and\ i \neq 1\ \}$$ There is also a hint that it cannot be ...
58 views

102 views

### How to prove certain parts of one regular language restricted by another regular language is also regular?

I’ve encountered the following difficult question that I don’t know how to solve. $L_1$ and $L_2$ are regular languages over the same $\Sigma$. \begin{align}L^\wedge=&\{σ_1σ_2...σ_n\mid n\ge1, \...