# Questions tagged [closure-properties]

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

366 questions
Filter by
Sorted by
Tagged with
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 ...
35 views

• 30.7k
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 "...
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 ...
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 ...
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$ ...
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 ...
• 123
1 vote
87 views

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 ...
• 21