Give a regular description for the set of words obtained by intercaling three words
w1,w2,w4
over
{0,1} with the same length and such that there exists another word
w3∈{0,1}∗, also
with the same length as
w1,w2,w4, and satisfying the following property:
the sum of the natural values obtained
from
w1,w2 by interpreting them
as a binary numbers is equal to
w3, that is
value2(w1)+value2(w2)=value2(w3),
and it is bigger than
value2(w4).
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.