## Exercise ‹5›:

Context-free description for $\{ \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 $\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 context-free description for the set of words obtained by intercaling two words $w_1,w_2$ over $\{a,b\}$ with the same length and with no occurrences of $aa$ in $w_2$, and such that for each two prefixes $x_1,x_2$ of $w_1,w_2$, respectively, of the same length, it holds that $x_1$ has more or equal occurrences of $a$ than $x_2$.

Intercaling $n$ words $w_1,\ldots,w_n$ over $\{a,b\}$ 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 context-free description... } To be able to submit you need to either log in, register, or become a guest.