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
0
votes
1answer
687 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
249 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
795 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
109 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
141 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
2k 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
150 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
578 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 ...
4
votes
1answer
152 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
209 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
142 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 ...
6
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
234 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
99 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
36 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
4k 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*} \...
1
vote
0answers
172 views

Unrestricted grammar is closed under intersection

I want to show that unrestricted grammar is closed under intersection and I don't want to use Turing machine or etc. So I think that we have two grammar $G_1$ and $G_2$ that are restricted for example ...
0
votes
0answers
26 views

Give an example of a language where both L and ¬L is not semidecidable? [duplicate]

I know ¬H is not semidecidable so I was thinking of creating a language that combines both H and ¬H. Therefore L would be undecidable for ¬H and ¬L would be undecidable for H. Is this a proper ...
0
votes
1answer
457 views

What happens during the DFA reversal construction if the initial state is final?

The steps in reversal of DFA are :- Make final state as initial state. If there are more than 1 final state, then make a new start state with epsilon transitions to these states. Change all initial ...
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
56 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
79 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
248 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
0answers
436 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)$ ...
0
votes
1answer
359 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
447 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
208 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 ...
0
votes
1answer
340 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.
1
vote
1answer
488 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 ...
2
votes
1answer
684 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
192 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
84 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 ...
12
votes
4answers
3k views

Operations under which the class of undecidable languages isn't closed

Do there exist undecidable languages such that their union/intersection/concatenated language is decidable? What is the physical interpretation of such example because in general, undecidable ...
0
votes
2answers
198 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
2answers
309 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
35 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-...
6
votes
2answers
258 views

Prove that context free languages aren't closed under DropMiddle

The question is simple: $\qquad \operatorname{DropMiddle}(L)=\{xy\in\Sigma^* \mid |x|=|y| \land \exists a\in\Sigma\colon xay\in L\}$. Prove that CFL's aren't closed under $\operatorname{...
3
votes
1answer
62 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?
20
votes
2answers
1k views

Are context-free languages in $a^*b^*$ closed under complement?

The context-free languages are not closed under complement, we know that. As far as I understand, context-free languages that are a subset of $a^*b^*$ for some letters $a,b$ are closed under ...
1
vote
1answer
440 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
1answer
388 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 \} \...
1
vote
2answers
122 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
2answers
192 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
323 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
315 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 ...
2
votes
1answer
99 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? ...