## Exercise ‹26:

Regular description for $\{ \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 $\mathtt{intercal}(a_1w_1,\ldots,a_nw_n)=a_1\ldots a_n\mathtt{intercal}(w_1,\ldots,w_n)$ and $\mathtt{intercal}(\lambda,\ldots,\lambda)=\lambda$
Give a regular description for the set of words obtained by intercaling four words $w_1,w_2,w_4,w_5$ over $\{0,1\}$ with the same length and such that there exists another word $w_3\in\{0,1\}^*$, also with the same length as $w_1,w_2,w_4,w_5$, and satisfying the following property: the sum of the natural values obtained from $w_1,w_2$ by interpreting them as a binary numbers is equal to $w_3$, that is $\mathtt{value}_2(w_1)+\mathtt{value}_2(w_2)=\mathtt{value}_2(w_3)$, and it is bigger than $\mathtt{value}_2(w_4)+\mathtt{value}_2(w_5)$.

Intercaling $n$ words $w_1,\ldots,w_n$ over $\{0,1\}$ and with the same length gives as result a word whose sequence of symbols is: the first symbol of $w_1$, the first symbol of $w_2$, …, the first symbol of $w_n$, the second symbol of $w_1$, the second symbol of $w_2$, …, the second symbol of $w_n$, the third symbol of $w_1$, and so on.
Authors: Guillem Godoy / Documentation:
 main { // Write here your regular description... } To be able to submit you need to either log in, register, or become a guest.