# 単語のすべての順列の集合のような言語演算子の帰納的定義は、シャッフル演算子から来た

Let \$X\$ be a finite alphabet. Given two words \$u, v in
X^{ast}\$ the shuffle operator is defined to be \$\$ u || v := { u_1
v_1 u_2 v_2 ldots u_n v_n : 1 le i le n, u_i, v_i in X^{ast},
u = u_1 ldots u_n, v = v_1 ldots v_n } \$\$ i.e. it is the set of
all “interlaced” strings (notice its signature \$X^{ast}times
X^{ast}to 2^{X^{ast}}\$). For example \$\$ ab || c = { cab, acb,
abc }. \$\$ There is also an inductive definition begin{align*}
varepsilon || u & = u || varepsilon = {u} \ au || bv & = a(u
|| bv) cup b(au || v). end{align*} This operator could be
extended to languages. Now, for a language \$L subseteq X^{ast}\$
denote by \$mbox{perm}(L)\$ the set of all permutations of words
from \$L\$, for example \$mbox{perm}({ abc }) = { abc, bac, acb,
cba, cab, bca }\$. Now we have the inductive definition for \$x in
X\$ and \$u in X^{ast}\$ begin{align*} mbox{perm}(varepsilon) & =
{varepsilon} \ mbox{perm}(xu) & = x || mbox{perm}(u).
end{align*} which defines it for words, and then extended to
languages. Now instead of all permutations, just consider the
rotations, or the cyclic permutations, i.e. for \$u in X^{ast}\$ \$\$
mbox{cycle}(L) := { vu : uv in L}. \$\$ For example
\$mbox{cycle}({abc}) = {abc, bca, cab}\$. And similar the
rotations and reflections, where if we define \$mbox{reverse}(u) =
u_n ldots u_1\$ for \$u = u_1 ldots u_n\$ with \$u_i in X\$, then for
\$L subset X^{ast}\$ the smallest set, called \$mbox{di}(L)\$ such
that \$\$ u in mbox{di}(L) Rightarrow mbox{cycle}({u})subseteq