# Questions tagged [finite-sets]

The tag has no usage guidance.

37 questions
Filter by
Sorted by
Tagged with
22 views

### Truth table of the next state function of a Moore machine

I'm studying finite state machines and trying to make this table but i don't know where to start. Isn't it necessary to know what happens when for example both inputs A and B from state s1 are active? ...
721 views

### Can we prove that any set of finite strings without substrings is finite?

I want to prove (or disprove) the following conjecture: Let $\Sigma$ be a finite alphabet, and let $L \subseteq \Sigma^*$ satisfy that there are no $v, w \in L$ such that $v$ is a proper substring of ...
• 23
59 views

### Finding all sets which are not subsets of other sets

I have a set of sets, for example { {1, 2, 3}, {1, 2}, {2}, {2, 4} } I want to find all sets which are not subsets of another set. For example, ...
• 141
69 views

### How to find the intersection of two FAs and then check if two FAs are equal?

I am still quite confused on how to properly handle in answering the intersection and equality of two FAs in terms of table form and manipulating its transformation....
1 vote
31 views

### matching vector families that form a group

Is there any research/information on matching vector family sets (the U list or the V list or both) that form a group (under addition)? You can find the definition of MV families here: https://homes....
58 views

### Deciding whether a set of relations can be composed to the empty relation

Is there an efficient algorithm to solve the following decision problem? Given a finite set $S$ and a set of relations $\mathcal R$ from $S$ to $S$, determine whether there is any sequence of ...
46 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 ...
• 185
53 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 ...
119 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$ ...
• 143
1 vote
236 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 ...
• 35
180 views

1 vote
7k 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 ...
• 1,637
1 vote
128 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 ...
• 12.3k
132 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 ...
• 101
166 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 ...
• 133
1 vote
708 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 &...
769 views

• 63
721 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 ...
65 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$ ...
• 121
357 views

### Given many partial orders, check them for consistency and report any that are not consistent

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 ...
• 154k
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 ...