Exercise 11:

Context-free description for {w1aw2aw3w1,w2,w3{0,1}    w1=w3    value2(w1w3)12˙    w2{0n1nn0}}\{ w_1aw_2aw_3 \mid w_1,w_2,w_3\in\{0,1\}^*\;\wedge\;|w_1|=|w_3|\;\wedge\;\mathtt{value}_2(w_1w_3)\in\dot{12}\;\wedge\;w_2\in\{0^n1^n\mid n\geq 0\} \}
Give a context-free description for the set of words of the form w1aw2aw3w_1aw_2aw_3 such that w1,w2,w3w_1,w_2,w_3 are constructed over the alphabet {0,1}\{0,1\}, the sizes of w1w_1 and w3w_3 coincide, w1w3w_1w_3 represent a multiple of 1212 in binary (in particular, the empty word represents 00, which is multiple of 1212), and w2w_2 is a sequence of 00’s followed by a sequence of 11’s where the number 00’s and 11’s coincide.
Authors: Guillem Godoy / Documentation:
To be able to submit you need to either log in, register, or become a guest.