Skip to main content

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
2 votes
1 answer
29 views

Rule-Based Link Prediction for Social Network

Relevance to Site I believe this question is suitable for the Computer Science Stack Exchange as it pertains to the implementation of a graph algorithm. According to this widely accepted answer, such ...
Jay Gupta's user avatar
0 votes
1 answer
35 views

Matroid Closure follows the Closure Operator Properties

I want to show that for a matroid $M=(E,\mathcal{I})$ the closure of $S\subseteq E$ i.e. $$cl(S)=\{x\in E\mid rank(S\cup\{x\})=rank(S)\}$$ actually follows the closure operator properties: $\forall$ $...
Soham Chatterjee's user avatar
0 votes
1 answer
59 views

Are NL-Complete languages closed under any regular operations?

I have tried looking online, but I couldn't find any definitive statements. It would make sense to me that Union and Intersection of two NL-C languages would produce a language not necessarily in NL-C....
Lior klunover's user avatar
1 vote
2 answers
396 views

Does there exist an context free language L such that L∩L^R is not context free?

By the closure property of context-free languages, if $L$ is context-free, then $L^R$ (the reverse of $L$) is also context-free, but $L\cap L^R$ might be non-context-free. I tried to come up with an ...
Miki's user avatar
  • 11
0 votes
2 answers
138 views

How to find prefixes and suffixes for infinite languages? (Automata)

L= {abc} prefix = {epsilon,a,ab,abc} suffix = {epsilon,c,bc,abc} It's easy to find suffixes and prefixes for finite Regular languages. But what will be the ...
Vedant Khandelwal's user avatar
0 votes
2 answers
419 views

What can i say about L1 given that L2, L1L2 and L2L1 are regular?

I found this question in one of our past exams, and I'm not to sure about the correct answer. I have a language L1 (which i don't know anything about) and another language L2, which is regular, the ...
pezbecoding's user avatar
1 vote
1 answer
58 views

P NP R RE closures

I wrote the following table for all the closures in those classes. is anything there incorrect? also, would appreciate help with coNP and coRE closures. couldn't find much information about it online.
Skynet's user avatar
  • 53
1 vote
1 answer
266 views

is the class NP closed under set difference?

I know P is closed under all Boolean operations, but what about NP? is NP closed under set difference and symmetric difference? is this table accurate? Edit: updated table:
Skynet's user avatar
  • 53
0 votes
0 answers
24 views

Theory of computation

I am trying to look answer for this question of toc please help me find the answer. The question is : Construct epsilon NFA(Non deterministic finite automata) for regular expression (0+1)*1(0+1)
Amy's user avatar
  • 1
3 votes
1 answer
214 views

context-free shuffle for two-letter alphabets

The operation of shuffle takes two words and merges their symbols, keeping the symbols of each of the strings in the right order. It can be recursively defined by $x \parallel \varepsilon = \...
Hendrik Jan's user avatar
  • 30.7k
0 votes
1 answer
66 views

Why these languages are closed under union or concatenation?

This is a question in my text book that I cannot understand the solution provided for that: In each case below, give a simple descreption of the smallest set of languages that contains all the "...
user157089's user avatar
0 votes
0 answers
25 views

Why is the collection of decision problems closed under set operations?

Most of the proofs of such properties that I see involve informally using algorithms or invoking Turing machines as needed. But it's not clear to me how are we using set operations on instances of ...
user avatar
0 votes
2 answers
490 views

If L = L1 U L2 is regular, L2 is the complement of L1 (which means L1 ∩ L2 = Ø), and we're given that L and L2 are regular, is L1 regular?

L1, L2, and L are not finite. We're given that L and L2 are regular. However, L1 ∩ L2 is empty, since L2 is the complement of L1. Is L1 regular under the property that regular languages are closed ...
st00dent's user avatar
0 votes
2 answers
93 views

Intersection of different languages

Consider L1 = Any language generated by a machine M1 L2 = Any language generated by a machine M2 Machine can be – FA, PDA, LBA, or TM Assuming Machine M2 is more powerful than M1 Let L3 = L1 $\cap$ ...
Chaitanya Kale's user avatar
2 votes
1 answer
179 views

Does this DFA prove closure under Perfect Shuffle?

I'm self studying Introduction to Theory of computation and I'm a bit confused about a problem definition. I'm trying to understand and verify whether my proof is correct or not. Question: Prove that ...
user5954246's user avatar
1 vote
2 answers
87 views

Show for every $CFL$ $L$ that's not $REG$ exists $L_1,L_2$ with $L_1$ is $REG$ and $L_1 \subseteq L_2$ and $L_2$ is not $REG$ and $L \subseteq L_2$

i want to show that for all $CFL$ and not $REG$ languages $L \subseteq \{0,1\}^*$ exists $L_1,L_2\subseteq\{0,1\}^*$ with: $L_1$ is $REG$ $L_2$ is $CFL$ and not $REG$ $L_1 \subseteq L_2 $ $L \...
tomato's user avatar
  • 17
1 vote
1 answer
69 views

Is LR(1) closed under union?

Suppose I have two LR(1) languages $L_1$, $L_2$. Is $L_1 \cup L_2$ also LR(1)? References to proofs would be very helpful.
Jonathon's user avatar
2 votes
0 answers
51 views

Is LR(1) closed under concatenation?

Suppose I have two LR(1) languages $L_1$, $L_2$. Is $L_1 L_2$ (their concatenation) guaranteed to also be LR(1)? References to proofs would be very helpful.
Jonathon's user avatar
3 votes
1 answer
110 views

Exotic closure of regular languages

Let $L_1 \subseteq \{0,1\}^{*}$ be a regular language, and let $L_2 \subseteq \{0,1\}^{*}$ be some (not necessarily regular) language. Show that $$L=\left\{ \sigma_{1}\#\sigma_{2}\dots\#\sigma_{n}\mid\...
Xiobiq's user avatar
  • 161
0 votes
0 answers
46 views

Regular, CFL, non-CFL infinite closures [duplicate]

I was wondering about infinite closure properties. Are the Regular languages closed under infinite union? Infinite intersection? Probably not, by taking $\forall n>0~~L_n=\{a^nb^n\}\in RL$, then $\...
Math4me's user avatar
  • 249
5 votes
1 answer
277 views

Is the set of languages satisfying the pumping lemma closed under concatenation?

Let $L$ be the set of all languages that satisfy the pumping lemma, including non-regular languages that satisfy it. Is the set $L$ closed under concatenation? I couldn’t prove it or find a ...
Clifford Royals's user avatar
2 votes
2 answers
103 views

Prove irregularity of a language using closure properties

Given the language $L=\{a^{j+1}b^kc^{j-k}|j\ge k\ge 0 \}$ I need to prove that it is not a regular language using closure properties. I was having a trouble handling $a^{j+1}$ so I tried to prove this ...
CforLinux 's user avatar
0 votes
1 answer
53 views

If $L$ is finite and $R$ is not regular, then $R\cup L$ is not regular

Prove/Disprove: If $L$ is finite and $R$ is not regular, then $R\cup L$ is not regular. I think that this one is true, but I am stuck: Since $R$ is not regular, it is infinite, so $R \cup L$ is also ...
Mish's user avatar
  • 5
3 votes
1 answer
344 views

Is NL closed under complemenrt?

I am trying to understand if NL is closed under complement or not. By NL i mean the non-deterministic-logspace complexity. I suppose that the answer is linked to the fact that we don't even know if L =...
James Anderson's user avatar
0 votes
1 answer
187 views

Prove that $\{xyz \mid zyx \in A \}$ is regular if $A$ is regular

Does the following work and is there anything possibly simpler? Let $X = (Q, \Sigma, \delta, s, F)$ be a DFA for $A$. Intuitively, we want to "remember" (or guess) two states $p$ and $q$ ...
SyntasticMonoid's user avatar
-2 votes
2 answers
1k views

Prove that the class of regular languages is closed under three operation

We define an operation three on strings as three(c1c2c3c4c5c6...) = c3c6... then the above-described definition is extended to languages. Prove that the class of regular languages is closed under this ...
kangkang's user avatar
0 votes
1 answer
450 views

Prove the class of regular languages is closed or not closed under the operations below

Suppose $A$ and $B$ are both languages over $\Sigma=\{0,1\}$. We use $n_0(x)$ and $n_1(x)$ to represent the number of $0$s and $1$s in the string $x$ respectively. Consider the following two ...
scone's user avatar
  • 3
2 votes
1 answer
2k 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 ...
darkexodus's user avatar
1 vote
1 answer
82 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$?
Turbo's user avatar
  • 2,901
3 votes
1 answer
161 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) ...
SeekingAMathGeekGirlfriend's user avatar
2 votes
1 answer
269 views

Proof that class of languages accepted by DPDA by empty stack is not closed under union

My first intuition was to take two languages $L_1$ and $L_2$ (symbol $d$ at the end is to fulfill prefix property): $$L_1 = \{ a^i b^i c^j d : i,j \ge 0 \} \mathrm{\ \ and\ \ } L_2 = \{ a^i b^j c^j d :...
user avatar
1 vote
1 answer
478 views

Closure of context-free languages under left-half [duplicate]

The regular languages are known to be closed under the operation "left half": $$ \operatorname{left}(L) = \{ x \in \Sigma^* : xy \in L \text{ for some } y \in \Sigma^* \text{ s.t. } |x|=|y| \...
Yuval Filmus's user avatar
-1 votes
2 answers
503 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: ...
user14342519's user avatar
1 vote
1 answer
90 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 ...
Gabriel F. Silva's user avatar
2 votes
1 answer
135 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 ...
Gabriel F. Silva's user avatar
3 votes
2 answers
2k 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 ...
bigbang's user avatar
  • 281
3 votes
2 answers
72 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 ...
Abigale Moore's user avatar
1 vote
1 answer
125 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 ...
Dhruv Joshi's user avatar
1 vote
1 answer
1k 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 \} $$ ...
Demokles's user avatar
1 vote
1 answer
63 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 ...
Lightsong's user avatar
  • 239
1 vote
1 answer
316 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. ...
NimaJan's user avatar
  • 353
-1 votes
1 answer
112 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^{+}$ ...
Mutating Algorithm's user avatar
0 votes
1 answer
37 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?
Jmk's user avatar
  • 13
0 votes
1 answer
130 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)$?
Matt B's user avatar
  • 11
1 vote
1 answer
55 views

Regularity of a language constructed from a know regular language

I'm working through so textbook questions on regular languages, and came across a problem that amounts to showing the following language is regular, given that $A$ is a regular language: $$ \{x|\...
MoC2020's user avatar
  • 63
0 votes
1 answer
350 views

PDA kleene star construction

I know how to prove that CFL are closed under kleene star operation using CFG. I can't find online or in class notes a proof using PDA. I would appreciate description of the basic idea (not formal).
Ella 's user avatar
  • 109
0 votes
0 answers
121 views

How to show that language L is NOT context-free?

True or false: To show that a language L is not context-free, one can alternatively show that the union between L and a known context-free language is not context-free. I know that you can prove ...
UnhappyFurball's user avatar
1 vote
1 answer
221 views

closure of Context free grammer to homomorphism using PDA

I was looking online, on sipser book, and on lecture notes and I can't find a proof to closure of context free languages to homomorphism that using PDA instead of CFG. I'm not looking for a full and ...
Ella 's user avatar
  • 109
0 votes
1 answer
188 views

Complement of $0^n1^n | n \in \mathbb{N}$

I know why A is irregular by Closure properties of irregular language. I also know the complement of $ \{ 0^n 1^n | n \in \mathbb{N}\}$ is $A = \{ 0^i 1^j| i \neq j\} \cup (0 \cup1)^*(1)(0 \cup1)^*0(0 ...
user6599080's user avatar
2 votes
1 answer
34 views

Decidability of a language and inclusion between two other languages

I have this assignement that asks to say if the following statement is true or false, and possibly justifying the answer: "Let L₁, L₂ be decidable languages. For every language L s.t. L₁ ⊆ L ⊆ L₂, L ...
abart's user avatar
  • 21

1
2 3 4 5
8