Exercise ‹18›:

Regular description for {intercal(w1,w2)∣w1,w2∈{0,1}∗  ∧  ∣w1∣=∣w2∣  ∧  value2(w1)>value2(w2)}\{ \mathtt{intercal}(w_1,w_2) \mid w_1,w_2\in\{0,1\}^*\;\wedge\;|w_1|=|w_2|\;\wedge\;\mathtt{value}_2(w_1)>\mathtt{value}_2(w_2) \},
where intercal(a1w1,…,anwn)=a1…anintercal(w1,…,wn)\mathtt{intercal}(a_1w_1,\ldots,a_nw_n)=a_1\ldots a_n\mathtt{intercal}(w_1,\ldots,w_n) and intercal(λ,…,λ)=λ\mathtt{intercal}(\lambda,\ldots,\lambda)=\lambda
Give a regular description for the set of words obtained by intercaling two words w1,w2w_1,w_2 over {0,1}\{0,1\} with the same length and such that the natural value obtained by interpreting w1w_1 as a binary number, that is value2(w1)\mathtt{value}_2(w_1), is bigger than value2(w2)\mathtt{value}_2(w_2).

Intercaling nn words w1,…,wnw_1,\ldots,w_n over {0,1}\{0,1\} and with the same length gives as result a word whose sequence of symbols is: the first symbol of w1w_1, the first symbol of w2w_2, …, the first symbol of wnw_n, the second symbol of w1w_1, the second symbol of w2w_2, …, the second symbol of wnw_n, the third symbol of w1w_1, and so on.
Authors: Guillem Godoy / Documentation:
To be able to submit you need to log in, register, or become a guest.