Give a context-free description for the set of words obtained by intercaling two words
w1,w2
over
{a,b} with the same length, where
w1 is palindromic and with no occurrences of
aa in
w2.
Intercaling
n words
w1,…,wn over
{a,b} and with the same length gives
as result a word whose sequence of symbols is:
the first symbol of
w1, the first symbol of
w2,
…, the first symbol of
wn, the second symbol of
w1, the second symbol
of
w2, …, the second symbol of
wn, the third symbol of
w1, and so on.