Pumping lemmas for classes of languages generated by folding systems

Abstract

Geometric folding processes are ubiquitous in natural systems ranging from protein biochemistry to patterns of insect wings and leaves. In a previous study, a folding operation between strings of formal languages was introduced as a model of such processes. The operation was then used to define a folding system (F-system) as a construct consisting of a core language, containing the strings to be folded, and a folding procedure language, which defines how the folding is done. This paper reviews main definitions associated with F-systems and next it determines necessary conditions for a language to belong to classes generated by such systems. The conditions are stated in the form of pumping lemmas and four classes are considered, in which the core and folding procedure languages are both regular, one of them is regular and the other context-free, or both are context-free. Full demonstrations of the lemmas are provided, and the analysis is illustrated with examples.

1 Introduction

In a recent paper, Sburlan (2011) introduced a folding operation for strings of symbols of a given formal language. The operation was inspired in actual geometric folding processes that occur in, e.g., protein biochemistry (Dobson 2003), in-vitro DNA shaping (Rothemund 2006), and even origami (the Japanese art of paper folding; Demaine and O’Rourke 2007), and it was proposed as a restricted computational model of such processes.

The folding operation was applied to define folding systems (F-systems) of the form $\varPhi =(L_1, L_2)$, where $L_1$ is the language that contains the strings to be folded (the core language), and $L_2$ is the language that contains strings defining how the folding must be performed (the folding procedure language). Then, the computing power of F-systems was investigated by comparison with standard language classes from the Chomsky hierarchy; i.e., regular, context-free, context-sensitive, recursive and recursively enumerable languages.

The paper fitted well within a growing body of applications of geometric folding to science and technology which have surged in recent years; in, e.g., aerospace and automotive technology (Cipra 2001), civil engineering (Filipov et al. 2015), biology (Mahadevan and Rica 2005), and robotics (Felton et al. 2014). Also, a number of theoretical studies have considered algebraic models, algorithmic complexity, and other mathematical and computational aspects of folding(e.g. Akitaya et al. 2017; Alperin 2000; Ida et al. 2016).

F-systems might find relevant applications to DNA computing and related areas of natural computing (Kari and Rozenberg 2008). As defined, the folding operation resembles the shuffle operation on trajectories (Mateescu et al. 1998). It is also related to parallel computing using transparencies, which can solve SAT and other NP-complete problems in linear time (Head 2011). Thus, the general purpose of the present paper is to further explore capabilities and limitations of F-systems, and it will consider the classes of languages generated when the core and the folding procedure languages are regular or context-free. Necessary conditions for a language to belong to some of those classes were presented by Sburlan (2011) in the form of pumping lemmas, similar to the well known pumping lemmas for regular and context-free languages (Hopcroft et al. 2001). His analysis considered the cases in which both the core and the folding procedure language are regular, and in which the core language is context-free and the folding procedure language is regular. Here, the two cases will be revised, in order to solve detected inconsistencies (see footnote 2 to Lemma 1). The lemmas will be restated in a weaker form (as consequence of the revision) and full proofs will be provided. Also, it will be shown that the same lemma for the case in which the core language is context-free and the folding procedures language is regular also applies to the case in which the class attribution is reversed. Finally, a lemma for the remaining case in which both the core and the folding procedure languages are context-free will be presented and proved.

2 Folding systems

For clarity of the analysis, let us review main definitions associated to folding operations and systems.

Let $\varSigma$ be an alphabet, $\varGamma =\{\texttt {u}, \texttt {d}\}$, and $f:\varSigma ^*\times \varSigma \times \varGamma \rightarrow \varSigma ^*$ a function such that

$$\begin{aligned} f(w, a, b)= \left\{ \begin{array}{ll} aw, &{} \text { if } b=\texttt {u},\\ wa, &{} \text { if } b=\texttt {d}. \end{array} \right. \end{aligned}$$

(1)

Then, the folding function $h:\varSigma ^*\times \varGamma ^*\rightarrow \varSigma ^*$ is a partial function defined by

$$\begin{aligned} h(w, v)=\left\{ \begin{array}{ll} f(f(\ldots f({\epsilon }, a_1, b_1)\ldots , a_{k-1}, b_{k-1}), a_k, b_k), &{}\text { if } |w|=|v|>0,\\ {\epsilon }, &{} \text { if } |w|=|v|=0,\\ \text {undefined,} &{} \text { if } |w|\ne |v|. \end{array} \right. \end{aligned}$$

(2)

where $w=a_1a_2\ldots a_k$, $v=b_1b_2\ldots b_k$, $a_i\in \varSigma$ and $b_i\in \varGamma$ for $i=1, 2, \ldots , k$, and ${\epsilon }$ is the empty string.¹

Example 1

Let $w=\texttt {abcde}$ and $v=\texttt {dduud}$. Then,

$$\begin{aligned} h(w, v)&=f(f(f(f(f({\epsilon }, \texttt {a}, \texttt {d}), \texttt {b}, \texttt {d}), \texttt {c}, \texttt {u}), \texttt {d}, \texttt {u}), \texttt {e}, \texttt {d}),\\&=f(f(f(f(\texttt {a}, \texttt {b}, \texttt {d}), \texttt {c}, \texttt {u}), \texttt {d}, \texttt {u}), \texttt {e}, \texttt {d}),\\&=f(f(f(\texttt {ab}, \texttt {c}, \texttt {u}), \texttt {d}, \texttt {u}), \texttt {e}, \texttt {d}),\\&=f(f(\texttt {cab}, \texttt {d}, \texttt {u}), \texttt {e}, \texttt {d}),\\&=f(\texttt {dcab}, \texttt {e}, \texttt {d}),\\&=\texttt {dcabe}. \end{aligned}$$

The computation of h(w, v) is represented graphically in Fig. 1. As shown there, each application of function f may be regarded as a folding operation that arranges the symbols of w in a stack. Strings over $\varGamma$ describe how each folding must be performed, where symbol u represents a “folding up” action and symbol d represents a “folding down” action. The final result is the created stack, read from top to bottom.

Fig. 1

Computation of $h(\texttt {abcde}, \texttt {dduud})=\texttt {dcabe}$ as a sequence of folding operations

Another way to see the folding operation is illustrated in Fig. 2. The folded string may be written as

$$\begin{aligned} h(w, v) = w_\texttt {u}^\mathcal {R}w_\texttt {d}, \end{aligned}$$

(3)

where $w_\texttt {u}$ is the sequence of symbols in w that are folded up, $\mathcal {R}$ denotes the reverse order operator, and $w_\texttt {d}$ is the sequence of symbols in w that are folded down. Letting $w=xy$, $v=st$, with $|x|=|s|$ and $|y|=|t|$, we obtain the identity

$$\begin{aligned} h(xy, st) = y_\texttt {u}^\mathcal {R}h(x, s)y_\texttt {d}. \end{aligned}$$

(4)

Fig. 2

Computation of $h(\texttt {abcde}, \texttt {dduud})=\texttt {dcabe}$ using Eq. (3)

A folding system (F-system) is defined as a pair $\varPhi =(L_1, L_2)$, where $L_1\subseteq \varSigma ^*$ is the core language, and $L_2\subseteq \varGamma ^*$ is the folding procedure language. The language of $\varPhi$ is

$$\begin{aligned} L(\varPhi )=\{h(w, v)|w\in L_1, v\in L_2, |w|=|v|\}. \end{aligned}$$

(5)

The class of all languages generated by F-systems with core languages of a class $\mathcal {C}$ and folding procedure languages of a class $\mathcal {H}$ is defined as

$$\begin{aligned} \mathcal {F}(\mathcal {C}, \mathcal {H})=\{L(\varPhi )|\varPhi =(L_1, L_2), L_1\in \mathcal {C}, L_2\in \mathcal {H}\}. \end{aligned}$$

(6)

3 Pumping lemmas

The first lemma states necessary conditions for a language to belong to class $\mathcal {F}(\textsf {REG}, \textsf {REG})$, where REG is the class of regular languages.

Lemma 1

Let $L \in \mathcal {F}(\textsf {REG}, \textsf {REG})$ be an infinite language over an alphabet $\varSigma$. Then, there are strings $u, v, x, y, z \in \varSigma ^*$, with $|vy|>0$, such that $uv^ixy^iz\in L$ for all $i\ge 0$.²

Proof

Let $L_1\subseteq \varSigma ^*$, $L_2\subseteq \{\texttt {u}, \texttt {d}\}^*$ and define the F-system $\varPhi =(L_1, L_2)$. If $L=L(\varPhi )$ is infinite, then $L_1$ and $L_2$ are also infinite. Set $p=\max (p_1, p_2)$, where $p_1$ and $p_2$ are pumping lengths for $L_1$ and $L_2$ (from the pumping lemma for regular languages), respectively, and choose any string $w\in L$ such that $|w|\ge p$. Then, there are strings $r\in L_1$ and $s\in L_2$ such that $w=h(r, s)$, with $|r|=|s|=|w|\ge p$.

According to the pumping lemma for regular languages, r may be written as $r=x_ry_rz_r$, with $|y_r|>0$, such that $x_ry_r^jz_r\in L_1$ for any $j\ge 0$. Similarly, s may be written as $s=x_sy_sz_s$, with $|y_s|>0$, such that $x_sy_s^jz_s\in L_2$ for any $j\ge 0$.

Consider the sequences $\{r_j\}$ and $\{s_j\}$ defined by

$$\begin{aligned} r_j&= x_ry_r^{|y_s|j+1}z_r, \end{aligned}$$

(7)

$$\begin{aligned} s_j&= x_sy_s^{|y_r|j+1}z_s, \end{aligned}$$

(8)

for any $j\ge 0$. Clearly, $r_j\in L_1$, $s_j\in L_2$; further, $|r_j|=|s_j|$ and so each of the strings in $\{r_j\}$ may be folded according with the corresponding string in $\{s_j\}$. For clarity, let us arrange $r_j$ and $s_j$ in the form of a double stranded structure $\left[ \frac{r_j}{s_j}\right]$, illustrated with an example in Fig. 3. Note that, for j large enough, repetitions of substring $y_r$ overlap with repetitions of substring $y_s$. Therefore, we may seek expressions of $r_j$ and $s_j$ of the form

$$\begin{aligned} r_j&=\xi _1\xi _2^{j-j_0}\xi _3, \end{aligned}$$

(9)

$$\begin{aligned} s_j&=\mu _1\mu _2^{j-j_0}\mu _3, \end{aligned}$$

(10)

with substrings $\xi _k$ and $\mu _k$ such that $|\xi _k|=|\mu _k|$ for $k=1, 2, 3$, and for $j\ge j_0$, where $j_0$ is a constant to be determined.

Fig. 3

Double stranded structure built with strings $r_j\in L_1$ and $s_j\in L_2$, in the case in which both $L_1$ and $L_2$ are regular languages

In Eqs. (7) and (8), the iterated portions may be decomposed as

$$\begin{aligned} y_r^{|y_s|j+1}&=\alpha _1\xi _2^{j-j_0}\alpha _2, \end{aligned}$$

(11)

$$\begin{aligned} y_s^{|y_r|j+1}&=\beta _1\mu _2^{j-j_0}\beta _2, \end{aligned}$$

(12)

with

$$\begin{aligned} \alpha _1\alpha _2&= y_r^{j_0|y_s|+1}, \end{aligned}$$

(13)

$$\begin{aligned} \beta _1\beta _2&= y_s^{j_0|y_r|+1}. \end{aligned}$$

(14)

Consequently, $\xi _2$ and $\mu _2$ will be formed by repetitions of strings $y_r$ and $y_s$, respectively, with

$$\begin{aligned} |\xi _2^{j-j_0}|&= |y_r^{|y_s|j+1}| - |\alpha _1\alpha _2|,\nonumber \\&= |y_r|(|y_s|j+1) - |y_r|(j_0|y_s|+1), \nonumber \\&= |y_r||y_s|(j-j_0), \end{aligned}$$

(15)

and the same result for $|\mu _2^{j-j0}|$. Consequently, $|\xi _2|=|\mu _2|=|y_r||y_s|$.

Next, we set $\xi _1 =x_r\alpha _1$, $\xi _3 =\alpha _2z_r$, $\mu _1 =x_s\beta _1$, $\mu _3 =\beta _2z_s$. Substrings $\alpha _1$, $\alpha _2$, $\beta _1$, $\beta _2$ are computed so that $|\xi _1|=|\mu _1|$ and $|\xi _3|=|\mu _3|$, with

$$\begin{aligned} \left\{ \begin{array}{l} \beta _1={\epsilon }, |\alpha _1|= |x_s|-|x_r|, \text { if } |x_s|\ge |x_r|,\\ \alpha _1={\epsilon }, |\beta _1|= |x_r|-|x_s|, \text { if } |x_s|<|x_r|. \end{array} \right. \end{aligned}$$

(16)

and using Eqs. (13) and (14). During the calculations, constant $j_0$ is chosen large enough so as to produce $|\alpha _2|\ge 0$ and $|\beta _2|\ge 0$.

Finally, $h(r_j, s_j)$ is computed by using Eqs. (9), (10), and the identity in Eq. (4). Note that $\xi _1$, $\xi _2$, and $\xi _3$ are folded as determined by $\mu _1$, $\mu _2$, and $\mu _3$, respectively. Then, letting $i=j-j_0$,

$$\begin{aligned} h(\xi _1\xi _2^i\xi _3, \mu _1\mu _2^i\mu _3) = (\xi _3)_\texttt {u}^\mathcal {R}[(\xi _2)_\texttt {u}^\mathcal {R}]^i(\xi _1)_\texttt {u}^\mathcal {R}(\xi _1)_\texttt {d}(\xi _2)_\texttt {d}^i(\xi _3)_\texttt {d}. \end{aligned}$$

(17)

The condition stated by the lemma is obtained from Eq. (17) with $u=(\xi _3)_\texttt {u}^\mathcal {R}$, $v=(\xi _2)_\texttt {u}^\mathcal {R}$, $x=(\xi _1)_\texttt {u}^\mathcal {R}(\xi _1)_\texttt {d}$, $y=(\xi _2)_\texttt {d}$, $z=(\xi _3)_\texttt {d}$. Also, $|vy|=|\xi _2|=|y_r||y_s|>0$. $\square$

The next lemma considers the two cases in which the core and the folding procedure languages belong to different classes, regular or context-free. Its demonstration follows similar steps as in Lemma 1.

Lemma 2

Let $L \in \mathcal {F}(\textsf {CF}, \textsf {REG})$ or $L \in \mathcal {F}(\textsf {REG}, \textsf {CF})$ be an infinite language over an alphabet $\varSigma$. Then, there are strings $w_1, w_2, \ldots , w_9\in \varSigma ^*$, with $|w_2w_4w_6w_8| >0$, such that $w_1w_2^iw_3w_4^iw_5w_6^iw_7w_8^iw_9\in L$ for all $i\ge 0$.

Proof

a) Consider first the case $L \in \mathcal {F}(\textsf {CF}, \textsf {REG})$ and proceed similarly as in Lemma 1, except that the pumping lemma for context-free languages is used for string $r\in L_1$. Thus, r is written as $r=u_rv_rx_ry_rz_r$, with $|v_ry_r|>0$ and $u_rv_r^jx_ry_r^jz_r\in L_1$, for any $j\ge 0$. Strings $r_j\in L_1$ and $s_j\in L_2$ are now defined as

$$\begin{aligned} r_j&= u_rv_r^{|y_s|j+1}x_ry_r^{|y_s|j+1}z_r, \end{aligned}$$

(18)

$$\begin{aligned} s_j&= x_sy_s^{|v_ry_r|j+1}z_s, \end{aligned}$$

(19)

for any $j\ge 0$, and their double stranded arrangement is illustrated in Fig. 4.

Fig. 4

Double stranded structure built with strings $r_j\in L_1$ and $s_j\in L_2$, in the case in which $L_1$ is a context-free language and $L_2$ is a regular language

For j large enough, repetitions of $y_s$ overlap with repetitions of $v_r$ (if $|v_r|>0$) and $y_r$ (if $|y_r|>0$). Then, we may seek expressions of $r_j$ and $s_j$ of the form

$$\begin{aligned} r_j&=\xi _1\xi _2^{j-j_0}\xi _3\xi _4^{j-j_0}\xi _5, \end{aligned}$$

(20)

$$\begin{aligned} s_j&=\mu _1\mu _2^{j-j_0}\mu _3\mu _4^{j-j_0}\mu _5, \end{aligned}$$

(21)

with substrings $\xi _k$ and $\mu _k$ such that $|\xi _k|=|\mu _k|$ for $k=1, 2, \ldots , 5$, and for $j\ge j_0$, where $j_0$ is a constant to be determined.

In Eqs. (18) and (19), the iterated portions are decomposed as

$$\begin{aligned} v_r^{|y_s|j+1}&=\alpha _1\xi _2^{j-j_0}\alpha _2, \end{aligned}$$

(22)

$$\begin{aligned} y_r^{|y_s|j+1}&=\beta _1\xi _4^{j-j_0}\beta _2, \end{aligned}$$

(23)

$$\begin{aligned} y_s^{|v_ry_r|j+1}&=\gamma _1\mu _2^{j-j_0}\gamma _2\mu _4^{j-j_0}\gamma _3, \end{aligned}$$

(24)

with

$$\begin{aligned} \alpha _1\alpha _2&= v_r^{j_0|y_s| + 1}, \end{aligned}$$

(25)

$$\begin{aligned} \beta _1\beta _2&= y_r^{j_0|y_s| + 1}, \end{aligned}$$

(26)

$$\begin{aligned} \gamma _1\gamma _2\gamma _3&= y_s^{j_0|v_ry_r| + 1}. \end{aligned}$$

(27)

Consequently, $\xi _2$ and $\mu _2$ will be formed by repetitions of strings $v_r$ and $y_s$, respectively, with $|\xi _2|=|\mu _2|=|v_r||y_s|$. Also, $\xi _4$ and $\mu _4$ will be formed by repetitions of strings $y_r$ and $y_s$, respectively, with $|\xi _4|=|\mu _4|=|y_r||y_s|$.

Next, we set $\xi _1 =u_r\alpha _1$, $\xi _3 =\alpha _2x_r\beta _1$, $\xi _5 =\alpha _2z_r$, $\mu _1 =x_s\gamma _1$, $\mu _3=\gamma _2$, $\mu _5 =\gamma _3z_s$. Substrings $\alpha _1$, $\alpha _2$, $\beta _1$, $\beta _2$, $\gamma _1$, $\gamma _2$, and $\gamma _3$ are selected so that $|\xi _1=\mu _1|$, $|\xi _3=\mu _3|$, and $|\xi _5=\mu _5|$, with

$$\begin{aligned} \left\{ \begin{array}{l} \gamma _1={\epsilon }, |\alpha _1|= |x_s|-|u_r|, \text { if } |x_s|\ge |u_r|,\\ \alpha _1={\epsilon }, |\gamma _1|= |u_r|-|x_s|, \text { if } |x_s|<|u_r|, \end{array} \right. \end{aligned}$$

(28)

$$\begin{aligned} \left\{ \begin{array}{l} \gamma _3={\epsilon }, |\beta _2|= |z_s|-|z_r|, \text { if } |z_s|\ge |z_r|,\\ \beta _2={\epsilon }, |\gamma _3|= |z_r|-|z_s|, \text { if } |z_s|<|z_r|, \end{array} \right. \end{aligned}$$

(29)

and using Eqs. (25) to (27) for a value of $j_0$ large enough.

Finally, we compute $h(r_j, s_j)$ using Eqs. (20), (21), and the identity in Eq. (4). Then, letting $i=j-j_0$,

$$\begin{aligned}&h(\xi _1\xi _2^i\xi _3\xi _4^i\xi _5, \mu _1\mu _2^i\mu _3\mu _4^i\mu _5) \nonumber \\&\quad =(\xi _5)_\texttt {u}^\mathcal {R}[(\xi _4)_\texttt {u}^\mathcal {R}]^i(\xi _3)_\texttt {u}^\mathcal {R}\nonumber \\&\qquad [(\xi _2)_\texttt {u}^\mathcal {R}]^i(\xi _1)_\texttt {u}^\mathcal {R}(\xi _1)_\texttt {d}(\xi _2)_\texttt {d}^i(\xi _3)_\texttt {d}(\xi _4)_\texttt {d}^i(\xi _5)_\texttt {d}. \end{aligned}$$

(30)

The condition stated by the lemma is obtained from Eq. (30) with $w_1=(\xi _5)_\texttt {u}^\mathcal {R}$, $w_2=(\xi _4)_\texttt {u}^\mathcal {R}$, $w_3=(\xi _3)_\texttt {u}^\mathcal {R}$, $w_4=(\xi _2)_\texttt {u}^\mathcal {R}$, $w_5=(\xi _1)_\texttt {u}^\mathcal {R}(\xi _1)_\texttt {d}$, $w_6=(\xi _2)_\texttt {d}$, $w_7=(\xi _3)_\texttt {d}$, $w_8=(\xi _4)_\texttt {d}$, $w_9=(\xi _5)_\texttt {d}$. Also, $|w_2w_4w_6w_8|=|\xi _2\xi _4|=|v_ry_r||y_s|>0$.

b) Consider next the case $L \in \mathcal {F}(\textsf {REG}, \textsf {CF})$. This case is treated as the previous one, except that r and s are decomposed following the pumping lemmas for regular languages and context-free languages, respectively. Thus, strings $r_j$ and $s_j$ are now defined as

$$\begin{aligned} r_j&= x_ry_r^{|v_sy_s|j+1}z_r, \end{aligned}$$

(31)

$$\begin{aligned} s_j&= u_sv_s^{|y_r|j+1}x_sy_s^{|y_r|j+1}z_s, \end{aligned}$$

(32)

with $|y_r|>0$, $|v_sy_s|>0$, and for any $j\ge 0$.

In Eqs. (31) and (32), the iterated portions are decomposed as

$$\begin{aligned} y_r^{|v_sy_r|s+1}&=\alpha _1\xi _2^{j-j_0}\alpha _2\xi _4^{j-j_0}\alpha _3, \end{aligned}$$

(33)

$$\begin{aligned} v_s^{|y_r|j+1}&=\beta _1\mu _2^{j-j_0}\beta _2, \end{aligned}$$

(34)

$$\begin{aligned} y_s^{|y_r|j+1}&=\gamma _1\mu _4^{j-j_0}\gamma _2, \end{aligned}$$

(35)

with

$$\begin{aligned} \alpha _1\alpha _2\alpha _3&= y_r^{j_0|v_sy_s| + 1}, \end{aligned}$$

(36)

$$\begin{aligned} \beta _1\beta _2&= v_s^{j_0|y_r| + 1}, \end{aligned}$$

(37)

$$\begin{aligned} \gamma _1\gamma _2&= y_s^{j_0|y_r| + 1}. \end{aligned}$$

(38)

The demonstration then follows similar steps as in the previous case: $r_j$ and $s_j$ are expressed as in Eqs. (20) and (21) with $\xi _1 =x_r\alpha _1$, $\xi _3 =\alpha _2$, $\xi _5 =\alpha _3z_r$, $\mu _1 =u_s\beta _1$, $\mu _3 =\beta _2x_s\gamma _1$, $\mu _5 =\gamma _2z_s$. $\square$

The last lemma considers the case in which both the core and the folding procedure languages are context-free. It has a longer demonstration; nevertheless, it follows the same technique as the previous ones.

Lemma 3

Let $L \in \mathcal {F}(\textsf {CF}, \textsf {CF})$ be an infinite language over an alphabet $\varSigma$. Then, there are strings $w_1, w_2, \ldots , w_{13}\in \varSigma ^*$, with $|w_2w_4w_6\ldots w_{12}| >0$, such that $w_1w_2^iw_3w_4^iw_5\ldots w_{11}w_{12}^iw_{13}\in L$ for all $i\ge 0$.

Proof

We proceed as in the previous lemmas, excepting that the pumping lemma for context-free languages is used for both strings $r\in L_1$ and $s\in L_2$. Thus, r is written as $r=u_rv_rx_ry_rz_r$, with $|v_ry_r|>0$ and $r_j=u_rv_r^jx_ry_r^jz_r\in L_1$ for any $j\ge 0$, and s is written as $s=u_sv_sx_sy_sz_s$, with $|v_sy_s|>0$ and $s_j=u_sv_s^jx_sy_s^jz_s\in L_2$ for any $j\ge 0$.

a) Consider first the case in which $|v_r||y_s|> |v_s||y_r|$. Strings $r_j$ and $s_j$ are defined as

$$\begin{aligned} r_j&= u_rv_r^{|v_r||y_s||v_sy_s|j+1}x_ry_r^{|v_r||y_s||v_sy_s|j+1}z_r, \end{aligned}$$

(39)

$$\begin{aligned} s_j&= u_sv_s^{|v_r||y_s||v_ry_r|j+1}x_sy_s^{|v_r||y_s||v_ry_r|j+1}z_s, \end{aligned}$$

(40)

for any $j\ge 0$, and their double stranded arrangement is illustrated in Fig. 5.

Fig. 5

Double stranded structure built with strings $r_j\in L_1$ and $s_j\in L_2$, in the case in which both $L_1$ and $L_2$ are context-free languages and $|v_r||y_s|>|v_s||y_r|$

For j large enough, and since $|v_r||y_s|> |v_s||y_r|$, then repetitions of $v_r$ overlap with repetitions of both $v_s$ (if $|v_s|>0$) and $y_s$, and repetitions of $y_s$ overlap with repetitions of both $v_r$ and $y_r$ (if $|y_r|>0$). Then, we may seek expressions of $r_j$ and $s_j$ of the form

$$\begin{aligned} r_j&=\xi _1\xi _2^{j-j_0}\xi _3\xi _4^{j-j_0}\xi _5\xi _6^{j-j_0}\xi _7, \end{aligned}$$

(41)

$$\begin{aligned} s_j&=\mu _1\mu _2^{j-j_0}\mu _3\mu _4^{j-j_0}\mu _5\mu _6^{j-j_0}\mu _7, \end{aligned}$$

(42)

with substrings $\xi _k$ and $\mu _k$ such that $|\xi _k|=|\mu _k|$ for $k=1, 2, \ldots , 7$, and for $j\ge j_0$, where $j_0$ is a constant to be determined.

In Eqs. (39) and (40), the iterated portions may be decomposed as

$$\begin{aligned} v_r^{|v_r||y_s||v_sy_s|j+1}&= \alpha _1\xi _2^{(j-j_0)}\alpha _2\xi _4{(j-j_0)}\alpha _3, \end{aligned}$$

(43)

$$\begin{aligned} y_r^{|v_r||y_s||v_sy_s|j+1}&=\beta _1\xi _6^{(j-j_0)}\beta _2, \end{aligned}$$

(44)

$$\begin{aligned} v_s^{|v_r||y_s||v_ry_r|j+1}&=\gamma _1\mu _2^{(j-j_0)}\gamma _2, \end{aligned}$$

(45)

$$\begin{aligned} y_s^{|v_r||y_s||v_ry_r|j+1}&=\delta _1\mu _4^{(j-j_0)}\delta _2\mu _6^{(j-j_0)}\delta _3, \end{aligned}$$

(46)

with

$$\begin{aligned} \alpha _1\alpha _2\alpha _3&= v_r^{j_0|v_r||y_s||v_sy_s| + 1}, \end{aligned}$$

(47)

$$\begin{aligned} \beta _1\beta _2&= y_r^{j_0|v_r||y_s||v_sy_s| + 1}, \end{aligned}$$

(48)

$$\begin{aligned} \gamma _1\gamma _2&= v_s^{j_0|v_r||y_s||v_ry_r| + 1}, \end{aligned}$$

(49)

$$\begin{aligned} \delta _1\delta _2\delta _3&= v_s^{j_0|v_r||y_s||v_ry_r| + 1}. \end{aligned}$$

(50)

Consequently, $\xi _2$ and $\mu _2$ will be formed by repetitions of strings $v_r$ and $v_s$, respectively, with $|\xi _2|=|\mu _2|=|v_r||v_s||y_s||v_ry_r|$; $\xi _4$ and $\mu _4$ will be formed by repetitions of strings $v_r$ and $y_s$, respectively, with $|\xi _4|=|\mu _4|=|v_r||y_s|(|v_r||y_s|-|v_s||y_r|)$; and $\xi _6$ and $\mu _6$ will be formed by repetitions of strings $y_r$ and $y_s$, respectively, with $|\xi _6|=|\mu _6|=|v_r||y_r||y_s||v_sy_s|$. Next, we set $\xi _1 =u_r\alpha _1$, $\xi _3 =\alpha _2$, $\xi _5=\alpha _3x_r\beta _1$, $\xi _7 =\beta _2z_r$, $\mu _1 =u_s\gamma _1$, $\mu _3=\gamma _2x_s\delta _1$, $\mu _5 =\delta _2$, $\mu _7=\delta _3z_s$.

Substrings $\alpha _1$, $\alpha _2$, $\alpha _3$, $\beta _1$, $\beta _2$, $\gamma _1$, $\gamma _2$, $\delta _1$, $\delta _2$ and $\delta _3$ are selected so that $|\xi _1|=|\mu _1|$, $|\xi _3|=|\mu _3|$, $|\xi _5|=|\mu _5|$, $|\xi _7|=|\mu _7|$, with $\delta _1={\epsilon }$, $|\alpha _2|=|\gamma _2| +|x_s|$,

$$\begin{aligned} \left\{ \begin{array}{l} \gamma _1={\epsilon }, |\alpha _1|= |u_s|-|u_r|, \text { if } |u_s|\ge |u_r|,\\ \alpha _1={\epsilon }, |\gamma _1|= |u_r|-|u_s|, \text { if } |u_s|<|u_r|, \end{array} \right. \end{aligned}$$

(51)

$$\begin{aligned} \left\{ \begin{array}{l} \delta _3={\epsilon }, |\beta _2|= |z_s|-|z_r|, \text { if } |z_s|\ge |z_r|,\\ \beta _2={\epsilon }, |\delta _3|= |z_r|-|z_s|, \text { if } |z_s|<|z_r|, \end{array} \right. \end{aligned}$$

(52)

and using Eqs. (47) to (50) for a value of $j_0$ large enough.

Finally, we compute $h(r_j, s_j)$ using Eqs. (41), (42), and the identity in Eq. (4). Then, letting $i=j-j_0$,

$$\begin{aligned}&h(\xi _1\xi _2^i\xi _3\xi _4^i\xi _5\xi _6^i\xi _7, \mu _1\mu _2^i\mu _3\mu _4^i\mu _5\mu _6^i\mu _7)\nonumber \\&\quad =(\xi _7)_\texttt {u}^\mathcal {R}[(\xi _6)_\texttt {u}^\mathcal {R}]^i (\xi _5)_\texttt {u}^\mathcal {R}[(\xi _4)_\texttt {u}^\mathcal {R}]^i(\xi _3)_\texttt {u}^\mathcal {R}\nonumber \\&\qquad [(\xi _2)_\texttt {u}^\mathcal {R}]^i(\xi _1)_\texttt {u}^\mathcal {R}(\xi _1)_\texttt {d}(\xi _2)_\texttt {d}^i(\xi _3)_\texttt {d}(\xi _4)_\texttt {d}^i(\xi _5)_\texttt {d}(\xi _6)_\texttt {d}^i(\xi _7)_\texttt {d}. \end{aligned}$$

(53)

The condition stated by the lemma is obtained from Eq. (53) with $w_1=(\xi _7)_\texttt {u}^\mathcal {R}$, $w_2=(\xi _6)_\texttt {u}^\mathcal {R}$, $w_3=(\xi _5)_\texttt {u}^\mathcal {R}$, $w_4=(\xi _4)_\texttt {u}^\mathcal {R}$, $w_5=(\xi _3)_\texttt {u}^\mathcal {R}$, $w_6=(\xi _2)_\texttt {u}^\mathcal {R}$, $w_7=(\xi _1)_\texttt {u}^\mathcal {R}(\xi _1)_\texttt {d}$, $w_8=(\xi _2)_\texttt {d}$, $w_9=(\xi _3)_\texttt {d}$, $w_{10}=(\xi _4)_\texttt {d}$, $w_{11}=(\xi _5)_\texttt {d}$, $w_{12}=(\xi _6)_\texttt {d}$, $w_{13}=(\xi _7)_\texttt {d}$. Also, $|w_2w_4w_6w_8w_{10}w_{12}|=|\xi _2\xi _4\xi _6|=|v_r||y_s||v_ry_r||v_sy_s|> 0$.

b) Consider next the case in which $|v_r||y_s|<|v_s||y_r|$, and define

$$\begin{aligned} r_j&= u_rv_r^{|v_s||y_r||v_sy_s|j+1}x_ry_r^{|v_s||y_r||v_sy_s|j+1}z_r, \end{aligned}$$

(54)

$$\begin{aligned} s_j&= u_sv_s^{|v_s||y_r||v_ry_r|j+1}x_sy_s^{|v_s||y_r||v_ry_r|j+1}z_s, \end{aligned}$$

(55)

for any $j\ge 0$, with the double stranded arrangement illustrated in Fig. 6.

Fig. 6

Double stranded structure built with strings $r_j\in L_1$ and $s_j\in L_2$, in the case in which both $L_1$ and $L_2$ are context-free languages and $|v_r||y_s|<|v_s||y_r|$

We seek expressions of $r_j$ and $s_j$ of the form in Eqs. (41) and (42), and decompose the iterated portions in Eqs. (54) and (55) as

$$\begin{aligned} v_r^{|v_s||y_r||v_sy_s|j+1}&= \alpha _1\xi _2^{(j-j_0)}\alpha _2, \end{aligned}$$

(56)

$$\begin{aligned} y_r^{|v_s||y_r||v_sy_s|j+1}&=\beta _1\xi _4^{(j-j_0)}\beta _2\xi _6^{(j-j_0)}\beta _3, \end{aligned}$$

(57)

$$\begin{aligned} v_s^{|v_s||y_r||v_ry_r|j+1}&=\gamma _1\mu _2^{(j-j_0)}\gamma _2\mu _4^{(j-j_0)}\gamma _3, \end{aligned}$$

(58)

$$\begin{aligned} y_s^{|v_s||y_r||v_ry_r|j+1}&=\delta _1\mu _6^{(j-j_0)}\delta _2, \end{aligned}$$

(59)

with

$$\begin{aligned} \alpha _1\alpha _2&= v_r^{j_0|v_s||y_r||v_sy_s| + 1}, \end{aligned}$$

(60)

$$\begin{aligned} \beta _1\beta _2\beta _3&= y_r^{j_0|v_s||y_r||v_sy_s| + 1}, \end{aligned}$$

(61)

$$\begin{aligned} \gamma _1\gamma _2\gamma _3&= v_s^{j_0|v_s||y_r||v_ry_r| + 1}, \end{aligned}$$

(62)

$$\begin{aligned} \delta _1\delta _2&= v_s^{j_0|v_s||y_r||v_ry_r| + 1}. \end{aligned}$$

(63)

Consequently, $\xi _2$ and $\mu _2$ will be formed by repetitions of strings $v_r$ and $v_s$, respectively, with $|\xi _2|=|\mu _2|=|v_r||v_s||y_r||v_sy_s|$; $\xi _4$ and $\mu _4$ will be formed by repetitions of strings $y_r$ and $v_s$, respectively, with $|\xi _4|=|\mu _4|=|y_r||v_s|(|v_s||y_r|-|v_r||y_s|)$; and $\xi _6$ and $\mu _6$ will be formed by repetitions of strings $y_r$ and $y_s$, respectively, with $|\xi _6|=|\mu _6|=|y_s||v_s||y_r||v_ry_r|$. Next, we set $\xi _1 =u_r\alpha _1$, $\xi _3 =\alpha _2x_r\beta _1$, $\xi _5=\beta _2$, $\xi _7 =\beta _3z_r$, $\mu _1 =u_s\gamma _1$, $\mu _3=\gamma _2$, $\mu _5 =\gamma _3x_s\delta _1$, $\mu _7=\delta _2z_s$.

Substrings $\alpha _1$, $\alpha _2$, $\alpha _3$, $\beta _1$, $\beta _2$, $\gamma _1$, $\gamma _2$, $\delta _1$, $\delta _2$ and $\delta _3$ are selected so that $|\xi _1|=|\mu _1|$, $|\xi _3|=|\mu _3|$, $|\xi _5|=|\mu _5|$, $|\xi _7|=|\mu _7|$, with $\gamma _3={\epsilon }$, $|\beta _2|=|\delta _1| +|x_s|$,

$$\begin{aligned} \left\{ \begin{array}{l} \delta _2={\epsilon }, |\beta _3|= |z_s|-|z_r|, \text { if } |z_s|\ge |z_r|,\\ \beta _3={\epsilon }, |\delta _2|= |z_r|-|z_s|, \text { if } |z_s|<|z_r|, \end{array} \right. \end{aligned}$$

(64)

and using Eq. (51) and Eqs. (60) to (63), for a value of $j_0$ large enough.

The demonstration then follows similar steps as in the previous case.

c) Finally, consider the remaining case of $|v_r||y_s|=|v_s||y_r|$. If $|v_r||y_s|\ne 0$ and $|v_s||y_r|\ne 0$, then the same constructions of the previous cases work, resulting in $\xi _4=\mu _4={\epsilon }$ and therefore $w_4=w_{10}={\epsilon }$.

If $|v_r||y_s|=|v_s||y_r|=0$, then either $v_r=v_s={\epsilon }$ or $y_r=y_s={\epsilon }$ (recall that the pumping lemma for context-free languages demands $|v_ry_r|>0$ and $|v_sy_s|>0$). Assume first $v_r=v_s={\epsilon }$, and define

$$\begin{aligned} r_j&= u_rx_ry_r^{|y_s|j+1}z _r, \end{aligned}$$

(65)

$$\begin{aligned} s_j&= u_sx_sy_s^{|y_r|j+1}z_s, \end{aligned}$$

(66)

for any $j\ge 0$. Next, follow the same procedure as in Lemma 1 to express $r_j$ and $s_j$ in the form of Eqs. (9) and (10), with the exception that $\xi _1 =u_rx_r\alpha _1$ and $\mu _1 =u_sx_s\beta _1$ (instead of $\xi _1 =x_r\alpha _1$ and $\mu _1 =x_s\beta _1$, respectively). Then, $h(r_j, s_j)$ is given by Eq. (17) and the condition stated by the present lemma is obtained with $w_1=(\xi _3)_\texttt {u}^\mathcal {R}$, $w_2=(\xi _2)_\texttt {u}^\mathcal {R}$, $w_3=w_4=w_5=w_6={\epsilon }$, $w_7=(\xi _1)_\texttt {u}^\mathcal {R}(\xi _1)_\texttt {d}$, $w_8=w_9=w_{10}=w_{11}={\epsilon }$, $w_{12}=(\xi _2)_\texttt {d}$, $w_{13}=(\xi _3)_\texttt {d}$. Also, $|w_2w_4w_6w_8w_{10}w_{12}|=|\xi _2|=|y_r||y_s|\ge 1$.

If $y_r=y_s={\epsilon }$, proceed as above with

$$\begin{aligned} r_j&= u_rv_r^{|v_s|j+1}x_rz _r, \end{aligned}$$

(67)

$$\begin{aligned} s_j&= u_sv_s^{|v_r|j+1}x_sz_s, \end{aligned}$$

(68)

for any $j\ge 0$. $\square$

4 Final remarks and example

The lemmas only apply to infinite languages. However, any finite language is in class $\mathcal {F}(\textsf {REG}, \textsf {REG})$. Let $L_1$ be any arbitrary language and define $\varPhi =(L_1, \texttt {d}^*)$; then, $L_1=L(\varPhi )$. Therefore, if $L_1$ is finite then it is regular and, consequently, $L_1\in \mathcal {F}(\textsf {REG}, \textsf {REG})$. Further, since $\textsf {REG}\subset \textsf {CF}$, then $L_1$ also is in $\mathcal {F}(\textsf {CF}, \textsf {REG})$, $\mathcal {F}(\textsf {REG}, \textsf {CF})$, and $\mathcal {F}(\textsf {CF}, \textsf {CF})$.

In spite of the lemmas being weak, they still are useful to prove non membership of some languages in a class, as the following example shows.

Example 2

Consider $L=\{\texttt {a}^n|\,n$ is prime $\}$ and assume that L satisfies the lemma. Then, there are strings $w_1, w_2, \ldots , w_{13}\in \texttt {a}^*$, with $|w_2w_4w_6\ldots w_{12}| >0$, such that $w_1w_2^iw_3w_4^iw_5\ldots w_{11}w_{12}^iw_{13}\in L$ for all $i\ge 0$. Letting $i=1$, we have that $w_1w_2w_3w_4w_5\ldots w_{11}w_{12}w_{13}=\texttt {a}^k$ for some prime k. Then, $w_2w_4w_6\ldots w_{12}=\texttt {a}^\ell$ with $0<\ell \le k$. Next, letting $i=k+1$, we obtain $w_1w_2^iw_3w_4^iw_5\ldots w_{11}w_{12}^iw_{13}= \texttt {a}^{k(1+\ell )}$. However, this string is not in $L_2$, because the number of a’s is not a prime. The contradiction implies that $L_2\notin \mathcal {F}(\textsf {CF}, \textsf {CF})$.

The existence of strong pumping lemmas for the studied classes remains as an open problem. It must be noted that some classes of languages possess only weak forms of pumping lemmas. For instance, if L is an infinite m-multiple context-free language, then there are strings of the form $u_0w^i_1u_1w^i_2u_2\ldots u_{2m-1}w^i_{2m}u_{2m}\in L$, for all $i\ge 0$ and $|w_1w_2\ldots w_{2m}|>0$ (Seki et al. 1991). However, there is at least one 3-multiple context-free language which has an infinite subset of strings that can not be pumped (Kanazawa et al. 2014). Therefore, a strong pumping lemma for the class of m-multiple context-free languages does not exist.

The present study has considered a folding operation model in the one dimensional case. As a next step, an extended model to capture two-dimensional aspects (as in origami processes) would be desirable.