Exercise 5:

Context-free description for {intercal(w1,w2)w1,w2{a,b}    w1=w2    w2aa=0    x1,y1,x2,y2:(w1=x1y1    w2=x2y2    x1=x2    x1ax2a)}\{ \mathtt{intercal}(w_1,w_2) \mid w_1,w_2\in\{a,b\}^*\;\wedge\;|w_1|=|w_2|\;\wedge\;|w_2|_{aa}=0\;\wedge\;\forall x_1,y_1,x_2,y_2:(w_1=x_1y_1\;\wedge\;w_2=x_2y_2\;\wedge\;|x_1|=|x_2|\;\Rightarrow\;|x_1|_a\geq|x_2|_a) \},
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 context-free description for the set of words obtained by intercaling two words w1,w2w_1,w_2 over {a,b}\{a,b\} with the same length and with no occurrences of aaaa in w2w_2, and such that for each two prefixes x1,x2x_1,x_2 of w1,w2w_1,w_2, respectively, of the same length, it holds that x1x_1 has more or equal occurrences of aa than x2x_2.

Intercaling nn words w1,,wnw_1,\ldots,w_n over {a,b}\{a,b\} 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.