Конкатенація

Розглянемо два рядки $\alpha$ і $\beta$. Їх конкатенацією називається рядок, отриманий в результаті приєднання до рядка $\alpha$ рядка $\beta$. Цей рядок позначається як $\alpha \beta$. Наприклад, конкатенацією рядків '$ab$' і '$ac$' буде рядок '$abac$'. Очевидно, що це визначення природним чином поширюється на конкатенацію довільної кількості рядків. Таким чином, конкатенацією нуля рядків буде порожній рядок, а конкатенацією одного рядка буде він сам.

Розглянемо певну множину $W$, що складається з рядків. Замиканням цієї множини називається множина W^{*}, яка складається лише з тих рядків, які можна отримати внаслідок конкатенації нуля або більше рядків з множини $W$. Таким чином, множина W^{*} містить порожній рядок, і якщо рядок $\alpha$ належить W^{*}, а рядок $\beta$ належить $W$, то рядок $\alpha \beta$ належить W^{*}. Більше того, всі елементи множини W^{*} можна подати у такому вигляді, тобто W^{*} є перетином всіх множин із зазначеними вище властивостями. Наприклад, якщо W=\{a, ab\}, то W^{*} складається з усіх рядків, у яких перед кожною літерою '$b$' стоїть хоча б одна літера '$a$'.

Задано певну множину рядків $W$. Потрібно знайти множину $X$, таку, що W^{*}=X^{*}, і множина $X$ має мінімально можливу кількість елементів. Якщо таких множин декілька, підходить будь-яка з них. Наприклад, якщо W=\{a, aabb, ab, ac, b, bac\}, то єдиною множиною, що задовольняє умови задачі, буде множина \{a, ac, b\}.