Given an alphabet Σ , recall that a regular language R is a certain subset of the free monoid M generated by Σ , which can be obtained by taking singleton subsets of Σ , and perform, in a finite number of steps, any of the three basic operations : taking union, string concatenation, and the Kleene star . The construction of a set like R is still possible without M being finitely generated free. Let M be a monoid, and 𝒮 M the set of all singleton subsets of M . Consider the closure ℛ M of S under the operations of union, product , and the formation of a submonoid of M . In other words, ℛ M is the smallest subset of M such that • ∅ ∈ ℛ M , • A , B ∈ ℛ M imply A ∪ B ∈ ℛ M , • A , B ∈ ℛ M imply A ⁢ B ∈ ℛ M , where A ⁢ B = { a ⁢ b ∣ a ∈ A , b ∈ B } , • A ∈ ℛ M implies A * ∈ ℛ M , where A * is the submonoid generated by A . Definition . A rational set ...