Pumping lemmas for classes of languages generated by folding systems

Sburlan’s (2011) original definition has been modified in order to include the case in which both w and v are empty strings.

Sburlan’s (2011) original version of the lemma states that there exists a positive constant p such that any string \(w\in L\), with \(|w| \ge p\), can be written as \(w =uvxyz\) satisfying \(uv^ixy^iz\in L\) for each \(i\ge 0\), \(|vy| \ge 1\), and \(|vxy|\le p\). In his proof, he set \(p=\max (p_1, p_2)\) where \(p_1\) and \(p_2\) are the pumping lengths for the core and the folding procedure languages. However, it can be shown that such a value of p does not always work. As a simple example, set \(\varPhi =(L_1, L_2)\) with \(L_1=\texttt {aaaab}^*\) and \(L_2=(\texttt {uu})^*\texttt {ddd}\). Then, \(p=5\). However, \(L(\varPhi )= \texttt {aaaab} \cup (\texttt {bb})^*\texttt {aaaabbb}\), and note that string aaaab has length 5 but it can not be pumped as indicated by the lemma. Although the original lemma may still hold for some other value of p (\(p=9\), in case of the example, with \(u=x=y={\epsilon }\), \(v=\texttt {bb}\) and z equal to the rest of the string), a full demonstration was not provided. Other inconsistencies have been detected in the proof. For example, the proof is based on constructing a double stranded structure \(\left[ \frac{r_j}{s_j}\right]\), and the technique is also used here. However, instead of Eqs. (7) and (8), the previous proof sets \(r_j = x_ry_r^{\frac{{{\,\mathrm{lcm}\,}}(|y_r|, |y_s|)}{|y_r|}j}z_r\) and \(s_j = x_sy_s^{\frac{{{\,\mathrm{lcm}\,}}(|y_r|, |y_s|)}{|y_s|}j}z_s\), where \({{\,\mathrm{lcm}\,}}\) denotes the least common multiple. Since the stranded construction requires \(|r_j|=|s_j|\), it follows that \(|x_rz_r|=|x_sz_s|\) and hence \(|y_r|=|y_s|\). However, those conditions do not hold for arbitrary regular languages \(L_1\) and \(L_2\) (note that, in the above example, \(|y_r|=|\texttt {b}|=1\) whereas \(|y_s|=|\texttt {uu}|=2\)).

Similar problems have been found also in the original version of the lemma for the case of \(L\in \mathcal {F}(\textsf {CF}, \textsf {REG})\).