MathDB
Good is regular

Source: STEMS 2021 CS Cat B Q3

January 23, 2021
Thoery of compuatation

Problem Statement

Let Σ\Sigma be a finite set. For x,y∈Σ∗x,y \in \Sigma^{\ast}, define x⪯yx\preceq y if xx is a sub-string (not necessarily contiguous) of yy. For example, ac⪯abcac \preceq abc. We call a set S⊆Σ∗S\subseteq \Sigma^{\ast} good if ∀x,y∈Σ∗\forall x,y \in \Sigma^{\ast}, x⪯y,  y∈S      ⇒  x∈S. x\preceq y, \; y \in S \; \; \; \Rightarrow \; x\in S . Prove or disprove: Every good set is regular.
Back to ProblemsView on AoPS