Give a regular description for the set of words obtained by intercaling two words
w1,w2
over
{0,1} with the same length and such that the natural value obtained by interpreting
w1 as a binary number, that is
value2(w1), is smaller than
value2(w2).
Intercaling
n words
w1,…,wn over
{0,1} and with the same length gives
as result a word whose sequence of symbols is:
the first symbol of
w1, the first symbol of
w2,
…, the first symbol of
wn, the second symbol of
w1, the second symbol
of
w2, …, the second symbol of
wn, the third symbol of
w1, and so on.