Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [closure-properties]

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

5
votes
1answer
105 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 ...
0
votes
2answers
50 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 ...
9
votes
3answers
12k 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
39 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 $...
3
votes
2answers
62 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 ...
2
votes
1answer
41 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
47 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
133 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 ...
2
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
61 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, \...
3
votes
2answers
648 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
50 views
3
votes
1answer
50 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
9k 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
11k 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
14k 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
112 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
93 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
154 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
98 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
297 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
76 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
137 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
35 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
560 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
10k 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
699 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
430 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?
1
vote
1answer
200 views

Proving that $\{0^i10^i : i \ge 1\}$ is non-regular, using only closure results

I have been stumped on the following question for a few hours now, I feel like I am missing some "aha" moment. $\text{Suppose that } \{ a^nb^n : n \ge 1 \} \text{ is non-regular.}$ $\text{Prove ...
1
vote
1answer
586 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 ...
1
vote
0answers
104 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 $ = ...
3
votes
2answers
106 views

Constructive Proof on Regular Languages

As an assignment, I've to come up with constructive proofs for the following languages to be regular supposing A and B are two distinct regular languages. $$L_1=\{w│w^R∈A\}$$ $$L_2=\{w│w=a_1 b_1,…,...
0
votes
1answer
4k views

Kleene positive closure - help in proofing this claim

I just started a course called 'Automata and Formal Languages'. I'm having difficulty in proofing\disproofing this equality. $ (L_{1} \circ L_{2})^{+} = L_{1}^{+} \circ L_{2}^{+} $ Where: $ L_{1}...
0
votes
1answer
1k views

Show that the collection of Turing-recognizable languages is closed under homomorphism [duplicate]

I have seen this question here, Closure of Turing-recognizable languages under homomorphism But actually this question answers the question of "What is the relation between homomorphism and ...
1
vote
2answers
135 views

XOR of two NP-Complete languages

Given two NP-Complete languages A and B, show that the language: $L = A\bigoplus B =\{a\bigoplus b \mid a \in A, b \in B, |a|=|b|\}$ is not necessarily NP-Complete. Remember $a\bigoplus b$ when $|...
1
vote
1answer
519 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 ...
5
votes
2answers
69 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 ...
4
votes
1answer
116 views

Complement of Mealy machine

How could one reasonably define and construct the complement of a deterministic Mealy machine? My intuition is that the complement should give exactly the opposite of output strings after a specific ...
4
votes
1answer
160 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 [01]*) is regular then so is the transformed language $ plus (L) $ consisting of ...
2
votes
1answer
103 views

context free grammar not closed under relative complement using product construction of pda and dfa

Hello friends need a bit of help, I Know that given: $$L_1 \in L_{cfg}, L_2 \in L_{reg}$$ $$L_2/L_1\notin L_{cfg}$$ because if it was contex free it would imply that $L_{cfg} $ is closed under ...
7
votes
1answer
1k views

Closure properties of linear context-free languages

Under what operations are linear context-free languages closed? Suppose $L_1, L_2$ are two linear context free languages. Are there any guarantees about $L_1 \cup L_2$, $L_1 \cap L_2$, $\overline{L_1}...
0
votes
0answers
176 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}∗...
1
vote
2answers
88 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 ...
0
votes
0answers
34 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 ...
0
votes
0answers
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 ...
3
votes
2answers
3k views

Are regular languages closed under inverse homomorphism?

Let $\Sigma$ and $\Delta$ be alphabets. Consider a function $\varphi: \Sigma \rightarrow \Delta^*$. Extend $\varphi$ to a function from $\Sigma^* \rightarrow \Delta^*$ such that: \begin{eqnarray*} \...