# Questions tagged [finite-sets]

The tag has no usage guidance.

31 questions
Filter by
Sorted by
Tagged with
38 views

### Is this the correct answer for the cardinality of this set?

This is a question from a practice quiz at my university. Is the question asking for the cardinality of Σ1 = {a,b} to the power of four? if that's the case, then the set would still have a ...
38 views

### How to implement conditional probability distribution on set-valued Random Variables

I'm trying to implement conditional probability distribution when the events of two RVs are sets. If I try to extrapolate concepts from real or categorical variables to sets things become confusing ...
51 views

### Complexity of a decision problem: system of linear equations over finite field with restricted solutions

I have a system of linear equations over a finite field $\mathbb F_p \cong \mathbb Z_p$, and I'm interested in the decision problem of whether there exists a solution where all of the variables $x_i$ ...
74 views

### Union of every language within group of decidable languages is also decidable?

So I was trying to solve following exercise: Let $(L_{i})_{i \in \mathbb{N}}$ be a family of decidable languages - this means that every $L_{i}$ is decidable. Then $\cup_{i \in \mathbb{N}}L_{i}$ is ...
164 views

6k views

### Understanding facts about regular languages, finite sets and subsets of regular languages

I am aware of following two facts related to two concepts: regular languages and finite sets: Regular languages are not closed under subset and proper subset operations. It is decidable ...
105 views

### Get indexes of unique elements in two different arrays in linear time

I have two array of the same set of elements, say for exemple: $a_1 = [x_1, x_2, …, x_n]$ and $a_2 = [y_1, y_2, …, y_n]$ so that $i \neq j \Rightarrow x_i \neq x_j$ Is it possible, in linear time, to ...
110 views

### Is this problem NP-complete?

Let there be a set of cardinality $n\in \mathbb{N}$. Let there also be $n$ subsets of that set. What is the smallest k such that union of some $n-k$ of those subsets is of cardinality at most $k$? The ...
130 views

### Compact mapping from an involuted set

Let $S$ be a set (say positive integers $\leq$ N) and $f$ an involution ($f$ is bijective, $f\cdot f=id$, e.g. xor with a constant). $g$ is a idempotent mapping choosing an arbitrary representative ...
469 views

### What is the space in big-O notation of the minimal DFA accepting the intersection of two finite languages where their minimal DFAs are given

Given two minimal deterministic finite automatons called A and B where A accepts the finite language L(A) and B accepts the finite language L(B) and the alphabet of both languages and automatons are &...
633 views

336 views

### If $L^*$ or $L^+$ is empty, can L be an infinite language?

I have to prove or disprove the implications in these two situations $L^* = \emptyset$ $\rightarrow$ $L$ is infinite $L^+ = \emptyset$ $\rightarrow$ $L$ is infinite Here are my thoughts. I would ...
60 views

### Approximate target subset by intersecting other subsets

Let $S$ be a finite set of integers (this set contains about 200000 elements). Let $T \subset S$ be a particular subset of $S$ called target. $S$ keeps growing. So does $T$. Each new element of $S$ ...
Inputs. I am given a finite set $S$ of symbols. I know there should exist some total order $<$ on $S$, but I'm not given this ordering and it could be anything. I am also given a collection of ...
Wikipedia has the following definition of the pumping lemma for regular langauges... Let $L$ be a regular language. Then there exists an integer $p$ ≥ 1 depending only on $L$ such that every ...