The shuffle product of two words u and v, denoted u‖v, is the set of all words of the form x1y1x2y2…xnyn for some n and for some (possible empty) words x1, …xn, y1, …yn, such that u = x1x2…xn, and v = y1y2…yn. In other words, u‖v is the set of all possible words that can be obtained by merging u and v so that the letters of u and v separately maintain their original orders but are allowed to alternate arbitrarily. The shuffle product of languages L and M, denoted L‖M, is the union of all u‖v for u ∈ L and v ∈ M.