Concatenation

Let us consider two strings $\alpha$ and $\beta$. Their concatenation is the string obtained by appending string $\beta$ to the end of string $\alpha$. This string is denoted as $\alpha \beta$. For example, the concatenation of '$ab$' and '$ac$' is the string '$abac$'. Clearly, this definition naturally extends to the concatenation of any number of strings. Thus, the concatenation of zero strings is the empty string, and the concatenation of a single string is the string itself.

Let us consider a set $W$ consisting of strings. The closure of this set, denoted as W^{*}, is the set containing precisely those strings that can be obtained by concatenating zero or more strings from $W$. Thus, the set W^{*} contains the empty string, and if a string $\alpha$ belongs to W^{*} and a string $\beta$ belongs to $W$, then the string $\alpha \beta$ belongs to W^{*}. Moreover, every element of W^{*} can be represented in this way, that is, W^{*} is the intersection of all sets with the specified properties. For example, if W=\{a, ab\}, then W^{*} consists of all strings in which before every letter '$b$' there is at least one letter '$a$'.

Given a set of strings $W$, it is required to find a set $X$ such that W^{*}=X^{*} and the set $X$ contains the minimal possible number of elements. If there are several such sets, any of them will do. For example, if W=\{a, aabb, ab, ac, b, bac\}, the only set satisfying the requirements is \{a, ac, b\}.