Exercise 26:

Regular description for {intercal(w1,w2,w4,w5)w3:(w1,w2,w3,w4,w5{0,1}    w1=w2=w3=w4=w5    value2(w1)+value2(w2)=value2(w3)>value2(w4)+value2(w5))}\{ \mathtt{intercal}(w_1,w_2,w_4,w_5) \mid \exists w_3: (w_1,w_2,w_3,w_4,w_5\in\{0,1\}^*\;\wedge\;|w_1|=|w_2|=|w_3|=|w_4|=|w_5|\;\wedge\;\mathtt{value}_2(w_1)+\mathtt{value}_2(w_2)=\mathtt{value}_2(w_3)>\mathtt{value}_2(w_4)+\mathtt{value}_2(w_5)) \},
where intercal(a1w1,,anwn)=a1anintercal(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 four words w1,w2,w4,w5w_1,w_2,w_4,w_5 over {0,1}\{0,1\} with the same length and such that there exists another word w3{0,1}w_3\in\{0,1\}^*, also with the same length as w1,w2,w4,w5w_1,w_2,w_4,w_5, and satisfying the following property: the sum of the natural values obtained from w1,w2w_1,w_2 by interpreting them as a binary numbers is equal to w3w_3, that is value2(w1)+value2(w2)=value2(w3)\mathtt{value}_2(w_1)+\mathtt{value}_2(w_2)=\mathtt{value}_2(w_3), and it is bigger than value2(w4)+value2(w5)\mathtt{value}_2(w_4)+\mathtt{value}_2(w_5).

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 either log in, register, or become a guest.