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
4
votes
3answers
3k views

Show that P is closed against the Kleene star

I have that question that looks kinda easy at first but it is quite hard. Let $L\in P$. Prove that $L^*\in P$ my approach: I tried to generate a Turing machine but I got stuck with the thing of ...
3
votes
2answers
1k views

Why DCFL is not closed under kleene star?

I have read somewhere that DCFL is not closed under kleene star. but I haven't found any example
3
votes
3answers
4k views

Closure of CFL against right-quotient with regular languages

Let $A/B$ = $\{ w \mid wx \in A$ for some $x \in B \}$. Show that if A is context free and B is regular, then $A/B$ is context free. My interpretation of this is is that we need to show that if a ...
0
votes
1answer
31 views

Are models of computation closed under composition?

It's common to ask whether a particular class of languages $\mathcal{C} \subseteq \mathcal{P}(\Sigma^*)$, for some alphabet $\Sigma$, is closed under complement, or union, or intersection, or ...
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 ...
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 ...
3
votes
2answers
6k views

Is every subset of a decidable set, also decidable?

Is it true that if A is a subset of B, and B is decidable, than A is guaranteed to be decidable? I believe it would be true because all the subsets of B should also be decidable making A decidable. I'...
12
votes
7answers
1k views

Is $A$ regular if $A^{2}$ is regular?

If $A^2$ is regular, does it follow that $A$ is regular? My attempt on a proof: Yes, for contradiction assume that $A$ is not regular. Then $A^2 = A \cdot A$. Since concatenation of two non-...
7
votes
2answers
1k views

Myhill-Nerode and closure properties

It is well known that regular languages are characterized by the Myhill-Nerode equivalence. For language $L$ over $\Sigma^*$ define the equivalence $x\sim_L y$ over $\Sigma^*$ iff for all $z\in\Sigma^*...
1
vote
4answers
363 views

What happens with trios, full trio, (full) semi-AFL, (full) AFL if we require closure under intersection?

Wikipedia says: A trio is a family of languages closed under e-free homomorphism, inverse homomorphism, and intersection with regular language. A full trio, also called a cone, is a trio ...
5
votes
1answer
2k views

Difference between substitution, morphism, and homomorphism

In closure properties, I got confused between substitution and morphism. 1) According to Wikipedia, string substitution means to map letters in a set of alphabets to languages (possibly in a ...
2
votes
1answer
48 views

How can the union of two 'context-free but not regular' languages be regular?

I cannot understand how the union of two languages which are context-free but not regular, can result in a regular language: If $L_1$ and $L_2$ are 'context-free but not regular' languages, defined ...
0
votes
1answer
604 views

Complexity classes that are closed under subtraction

Are NP or P closed under subtraction? Im having a hard time deciding whether they are or aren't. Question was edited Original question: Im having some hard time figuring out what languages are closed ...
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?
1
vote
1answer
32 views

Is the difference of two context-free languages still context-free?

i am asking myself the following question: Assuming: A and B are context-free languages, then A - B (difference) must also be context-free language, right? but I do not know how to prove it.
6
votes
2answers
86 views

Can the regular image of a context-free language be undecidable?

I just need to know the truth or falsity of a simple statement. Let $L_1$ be a context-free language over an alphabet which contains some number of characters $\Sigma$, as well as a single, special ...
0
votes
1answer
22 views

Getting from one language to the other using closure properties(automata) [duplicate]

I am trying to deduct how i can, using closure properties, deduct that since the following language is not context free $$L=\left\{abc^{i_1}bc^{i_2}...bc^{i_{2m}}def^{j_1}ef^{j_2}..ef^{j_{2n}}ghq^{k_1}...
1
vote
2answers
74 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)$...
12
votes
4answers
12k views

Union of regular languages that is not regular

I've come across that question : "Give examples of two regular languages which their union doesn't output a regular language. " This is pretty shocking to me because I believe that regular languages ...
6
votes
3answers
143 views

First half of context-free palindromes

If $L\subseteq\Sigma^*$ is a regular language, then $\text{mir}(L) = \{ww^R \mid w\in L\}$ is context-free. This is a nice exercise. Question: does the reverse hold? Thus, if $\text{mir}(L)$ is ...
0
votes
2answers
131 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 ...
10
votes
3answers
13k views

What is complement of Context-free languages?

I need to know what class of CFL is closed under i.e. what set is complement of CFL. I know CFL is not closed under complement, and I know that P is closed under complement. Since CFL $\subsetneq$ P I ...
2
votes
2answers
46 views

Calculate the number of distinct permutations of length n in the closure of a language

I am studying a distance CS course, but there is no tutor available, so I would appreciate your help... Consider the language $S = \{a, aa, ab\}$ How many distinct words of length $n$ will appear in $...
2
votes
1answer
45 views

How to use homomophism in closure proofs?

I am having a hard time understanding homomorphism. All I seem to understand is that it is a substitution. When I look at examples of proving closure of a particular operation over a regular language, ...
0
votes
1answer
40 views

operate infinite times over a regular language

Let $T:Σ^*\to Σ^*$ be an operation such that $T(L)$ is regular for all regular languages $L \in Σ^*$. Is it possible to prove $T^∞(L)$ is regular? $T^∞(L)=\bigcup_{i=1}^{\infty}{T^{i}\left(L\right)}$...
1
vote
1answer
58 views

Why proving that two languages used to merge into a regular language are not necessarily regular isn't possible with closure properties?

Let $L$ be a regular language over alphabet $\Sigma$. $L$ is the result of merging $2$ languages letter by letter that is for $a_1a_2...a_n\in L_1, b_1b_2...b_n\in L_2, L=a_1b_1a_2b_2...a_nb_n$. $\...
3
votes
3answers
187 views

If $L$ is a regular language, then $s(L)$ is also regular

...where $s$ is a substitution that replaces each symbol of each string in $L$ with a regular expression. For example, if $L=a^*b$ and $s(a) =ab, s(b) = b^*$, we have $s(L) = (ab)^*b^*$. My ...
3
votes
3answers
3k views

If L is regular, show that even(L) is also regular

I am stuck on the following question. If $L$ is regular show that $\mathrm{even}(L)$ is also regular, where $\mathrm{even}(L) = \{ even(w) : w \in L \}$, $w$ is a string in $L$ and $\mathrm{even}(w)...
2
votes
2answers
69 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, \...
2
votes
2answers
763 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
2answers
52 views

if $L_1$ and $L_2$ are languages over the same alphabet and $L_1 \cap L_2$ is context free, at least one of them must be context free

I am having a hard time understanding if this would be true or false, can someone point me in the right direction?
3
votes
1answer
58 views

unambiguous context-free languages and complementation

I was considering the following two natural questions about the relationship between unambiguity and complementation for the class of context-free languages: Is the complement of an unambiguous ...
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 ...
7
votes
4answers
10k views

Is the class NP closed under complement?

Is the class $\sf NP$ closed under complement or is it unknown? I have looked online, but I couldn't find anything.
5
votes
2answers
12k views

Why isn't the class of Turing-Recognizable languages closed under Complement?

I'm studying Turing Machines and I've already showed how Turing-Decidable is closed for the operations of Union, Intersection, Concatenation, Complement and Kleene Star. Next I did some demonstrations ...
2
votes
2answers
16k views

Union and intersection of a regular and a non-regular language

Lets say we have $L_1$, which is a regular language and $L_2$ which is not. Are $L_1 \cap L_2$, $L_1 \cup L_2$ , $L_1$ \ $L_2$ and $L_1 \cdot L_2$ are always non-regular languages? We know that two ...
2
votes
1answer
131 views

Closure of regular languages under deleting a 1 from each even run of 1s

Let $R$ be a regular set over the alphabet $\{0, 1\}$. Give a machine construction to prove that the set obtained by deleting one 1 from each even length block of 1’s is also regular, and using ...
2
votes
2answers
102 views

Finding if the given language is regular or not

I have the language $$L = \{a^mb^nc^o| \, m + n + o > 5\}$$ where $m,n,o$ are non-negative integers. I have to find whether the language is regular or not. My attempt: I feel it should be non ...
0
votes
1answer
220 views

Finite state automaton for the reverse of the language, and multiple starting states

I am studying about Finite State Automaton, and I found that the when reversing a language (i.e., transforming $L$ to $L^R$), I have to add new start state. Why is that? Also, can a Finite State ...
2
votes
1answer
117 views

Show that RP is closed under concatenation

I'm trying to prove the following problem: Show that $RP$ is closed under concatenation Now, let's say that the two languages are $L_{1}$ and $L_{2}$ (both in $RP$). Then I accept a word iff the ...
0
votes
1answer
457 views

Why is the intersection of these two Languages Recursively Enumerable, not Recursive?

I am only several days exposed to computational theory, so my understanding is quite slim: in a question, it says that for a regular language L1 and a recursively enumerable but not recursive language ...
2
votes
2answers
99 views

Proving $L'=\{uv : u \in L \; \land v \in L^R \; \land |u|=|v|\}$ is a CFL with closure properties [duplicate]

Given a language $L$ over $\Sigma=\{a,b\}$ let us define $L'=\{uv : u \in L \; \land v \in L^R \; \land |u|=|v|\}$ Prove: if $L$ is regular, then $L'$ is a context free language. I know how to ...
3
votes
1answer
206 views

Is the union of NP Complete language and a finite language (in P) NP Complete?

Let there be a language $A$ which is NP complete and language $B$ which is a finite language, is the union of $A \cup B$ NP complete language?
1
vote
1answer
38 views

Proving that Pre(L) is regular using automatas: Should I prove that Pre(L) is the semantic of the new automata?

Let $L$ be a regular language, and $Pre(L)$ be the set of all words that are prefix of some word in $L$. Prove that $Pre(L)$ is regular. My proof: Let $M = (\Sigma, Q, \delta, q_0, F)$ be an ...
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 ...
4
votes
1answer
676 views

Proving that if L is regular. Then L′ = {ww : w ∈ L} is regular

I believe this statement to be true. And here's my reasoning: Based on regular languages properties, the concatenation of two regular languages is regular. And since L′ = L · L, it follows that L′ ...
8
votes
3answers
12k views

Context-free Languages closed under Reversal

In class this week we've been learning about the CFLs and their closure properties. I've seen proofs for union, intersection and compliment but for reversal my lecturer just said its closed. I wanted ...
2
votes
2answers
2k views

Proving that non-regular languages are closed under concatenation

How can I prove that non-regular languages are closed under concatenation using only the non-regularity of $L=\{a^nb^n|n\ge1\}$ ?
1
vote
4answers
826 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
604 views

Class P is closed under concatenation

Proving that Class P is closed under concatenation. The answer is given below: But I do not know why stage 2 is repeated at most O(n), could anyone explain this for me please?