The Failure of the Strong Pumping Lemma for Multiple Context-Free Languages

Abstract

Seki et al. (Theor. Comput. Sci. 88(2):191–229, 1991) showed that every m-multiple context-free language L is weakly 2m-iterative in the sense that either L is finite or L contains a subset of the form $\{ u_{0} w_{1}^{i} u_{1} \cdots w_{2m}^{i} u_{2m} \mid i \in \mathbb {N}\}$, where w ₁⋯w _2n ≠ε. Whether every m-multiple context-free language L is 2m-iterative, that is to say, whether all but finitely many elements z of L can be written as z=u ₀ w ₁ u ₁⋯w _2m u _2m with w ₁⋯w _2m ≠ε and $\{ u_{0} w_{1}^{i} u_{1} \cdots w_{2m}^{i} u_{2m} \mid i \in \mathbb {N}\} \subseteq L$, has been open. We show that there is a 3-multiple context-free language that is not k-iterative for any k.

1 Introduction

The study of iterative properties of the languages of multiple context-free grammars (MCFG) [14] has had a peculiar history.¹ Seki et al. [14] proved that any language L generated by an MCFG of dimension m (i.e., m-MCFG) is weakly 2m-iterative (in the sense of Greibach [2, 3]): either L is finite or else it contains a subset of the form

$$ \bigl\{ u_0 w_1^i u_1 \cdots w_{2m}^i u_{2m} \mid i \in \mathbb {N}\bigr\} $$

(1)

for some strings u ₀,u ₁,…,u _2m and w ₁,…,w _2m such that w ₁⋯w _2m ≠ε.² Seki et al. [14] called this theorem a “pumping lemma” for m-MCFLs. Their proof of the theorem starts with an application of the pigeon-hole principle to a path in a derivation tree in a way familiar from the pumping lemma for context-free languages; beyond that, however, it involves much more intricate reasoning than in the context-free case, due to the complex relation between derivation trees of an MCFG and the derived strings. The proof goes roughly as follows.

Given a sufficiently long string z in the language L of an m-MCFG G, the derivation tree T for z must contain a “context” U[] inside it that can be iterated any number of times.³ That is to say, T can be written as T=U′[U[T′]], where U[T′] is a subtree of T which contains T′ as a proper subtree, and for each i≥0, U′[U ⁱ[T′]] is also a derivation tree. Here, the notation U ⁱ[T′] is defined by

$$\begin{aligned} U^0\bigl[T'\bigr] = & T', \\ U^{i+1}\bigl[T'\bigr] = & U\bigl[U^i \bigl[T'\bigr]\bigr]. \end{aligned}$$

In the case of a context-free grammar, each subtree of a derivation tree yields a single string. In the case of an m-MCFG, in contrast, each subtree of a derivation tree is associated with a tuple of strings. Thus, the contribution of the iterable context U[] to the derived string is some function g mapping an n-tuple of strings to another n-tuple, for some n≤m. Such a function can be specified by an equation of the form g(x ₁,…,x _n )=(α ₁,…,α _n ) using variables x _i and strings α _i over Σ∪{x ₁,…,x _n }, where Σ is the terminal alphabet, such that each x _i occurs in a unique α _j . In the special case where α _j =w _2j−1 x _j w _2j for all j=1,…,n (w ₁,…,w _2n ∈Σ ^∗), iteration of U[] inside the derivation tree translates into iteration of the strings w ₁,…,w _2n inside the derived string, giving rise to a set of the form (1). In general, since x _i may end up in some α _j with j≠i, the effect of iterating U[] in T=U′[U[T′]] is rather hard to describe. As a consequence, derivation trees of the form U′[U ⁱ[T′]] do not (necessarily) generate a set of the form (1). One can see, however, that for large enough k, the k-fold composition g ^k of g with itself has the property that if g ^k(x ₁,…,x _n )=(β ₁,…,β _n ), then for every j=1,…,n, β _j either is a constant string (i.e., string over Σ) or else contains x _j . It follows that g ^2k(x ₁,…,x _n )=g ^k(β ₁,…,β _n )=(w ₁ β ₁ w ₂,…,w _2n−1 β _n w _2n ) for some constant strings w ₁,…,w _2n such that w _2j−1 w _2j =ε whenever β _j is a constant string. It is not difficult to see that this implies that $g^{(i+1)k}(\boldsymbol {x}_{1},\dots,\boldsymbol {x}_{n}) = (w_{1}^{i} \beta_{1} w_{2}^{i},\dots,w_{2n-1}^{i} \beta_{n} w_{2n}^{i})$. Thus, derivation trees U′[U ^(i+1)k[T′]] (i≥0) yield a subset of L of the required form (1). Crucially, the original string z is not an element of this set.

By a strange quirk of fate, this proof was erroneously claimed by Radzinski [13] to implicitly demonstrate a much stronger property,⁴ namely, that every m-MCFL L is 2m-iterative (in the sense of Greibach [3]): all but finitely many z∈L can be written as z=u ₀ w ₁ u ₁⋯w _2m u _2m such that w ₁⋯w _2m ≠ε and $\{ u_{0} w_{1}^{i} u_{1} \cdots w_{2m}^{i} u_{2m} \mid i \in \mathbb {N}\} \subseteq L$. More strangely, Groenink [5] just took Radzinski’s word for it (see also [4]). A more recent book by Kracht [10] also states this property as a theorem.

We refer to the assertion that every m-MCFL is 2m-iterative as the strong pumping lemma for m-MCFLs, to distinguish it from Seki et al.’s [14] theorem. It is clear that no simple modification of the method of Seki et al. can establish the strong pumping lemma for m-MCFLs. It is only when the iterable context U[] maps an n-tuple (x ₁,…,x _n ) to an n-tuple of the form (w ₁ x ₁ w ₂,…,w _2n−1 x _n w _2n ) that it is possible to conclude, analogously to the context-free case, that the given string z contains factors w ₁,…,w _2m that can be pumped up and down without pushing the resulting string outside of the given m-MCFL.⁵ Kanazawa [6] called such a well-behaved iterable context an even pump in his proof that an m-MCFG satisfying the condition of well-nestedness always generates a 2m-iterative set. This proof works by induction on m. The base case is handled by the fact that well-nested 1-MCFGs are just CFGs. For the induction step, Kanazawa showed that given a well-nested m-MCFG G, one can always find a well-nested (m−1)-MCFG G′ for the language L′ consisting of strings generated by G with derivation trees containing no even pump. Hence the language L of G is a union of some 2m-iterative set and L′, which, by induction hypothesis, is a 2(m−1)-iterative set. It follows that L is 2m-iterative, completing the induction. This method is such that derivation trees of G′ have very different shapes from the original derivation trees of G for the same strings. Whereas the method also works for 2-MCFGs in general, the well-nestedness property is essential for m≥3, and there is no obvious way of extending it to the non-well-nested case.

In this paper, we prove that the strong pumping lemma indeed fails for non-well-nested m-MCFGs for m≥3. We do so by exhibiting a particular 3-MCFG that generates a language that is non-iterative in a very strong sense. This language, which we call H, is not k-iterative for any k. It is not even finitely pumpable in the sense of Groenink [4, 5], a condition which is similar to k-iterativity but allows the number of iterable factors to vary from string to string. In fact, H contains an infinite subset $\{ v_{n} \mid n \in \mathbb {N}\}$ consisting of strings that are almost anti-iterative in the following sense: whenever v _n =u ₀ w ₁ u ₁⋯w _k u _k and w ₁⋯w _k ≠ε (for any k), it holds that

$$\bigl|\bigl\{ i \mid\text{$i > 1$ and $u_{0} w_{1}^{i} u_{1} \cdots w_{k}^{i} u_{k} \in H$} \bigr\} \bigr| \leq1. $$

Most of the rest of the paper is devoted to the proof of this property of the language H (Sect. 3). Before we get to it, we briefly review basic notions concerning multiple context-free grammars for readers unfamiliar with this grammar formalism (Sect. 2). The proof in Sect. 3 does not use any general properties of MCFLs, and can be followed by anyone who understands the definition of the language H.

2 Multiple Context-Free Grammars

Like a context-free grammar, a multiple context-free grammar is a quadruple G=(N,Σ,P,S), where N is a finite set of nonterminals, Σ is a finite set of terminals, P is a set of rules, and S is a designated nonterminal. While a nonterminal of a CFG is associated with a set of terminal strings, a nonterminal of an MCFG is interpreted as a q-ary relation on terminal strings, where q is the dimension of the nonterminal. Each nonterminal comes with a unique dimension. (So the set N can be thought of as a ranked alphabet.) The dimension of the designated nonterminal S is always 1. A rule is of the form

$$A(\alpha_1,\dots,\alpha_q) \leftarrow B_1( \boldsymbol {x}_{1,1},\dots,\boldsymbol {x}_{1,q_1}),\dots,B_n( \boldsymbol {x}_{n,1},\dots,\boldsymbol {x}_{n,q_n}), $$

where n≥0, A,B ₁,…,B _n are nonterminals of dimension q,q ₁,…,q _n , respectively, the x _i,j are pairwise distinct variables, which are symbols not in Σ, and α ₁,…,α _q are strings over Σ∪{x _i,j ∣1≤i≤n,1≤j≤q _i } such that each x _i,j occurs at most once in α ₁⋯α _q .

A rule is interpreted like a universally quantified implication from right to left. Define a predicate ⊢ _G that holds of expressions of the form A(u ₁,…,u _q ) (called facts) inductively as follows:

• If A(u ₁,…,u _q )← is a rule of G, then ⊢ _G A(u ₁,…,u _q ).

• If $A(\alpha_{1},\dots,\alpha_{q}) \leftarrow B_{1}(\boldsymbol {x}_{1,1},\dots,\boldsymbol {x}_{1,q_{1}}),\dots,B_{n}(\boldsymbol {x}_{n,1},\dots,\boldsymbol {x}_{n,q_{n}})$ is a rule of G and $\vdash_{G} B_{i}(w_{i,1},\dots,w_{i,q_{i}})$ for i=1,…,n, then ⊢ _G A(u ₁,…,u _q ), where (u ₁,…,u _q ) is the result of substituting w _i,j for each x _i,j in (α ₁,…,α _q ).

When ⊢ _G A(u ₁,…,u _q ), we say that A(u ₁,…,u _q ) is derivable (in G). (We sometimes write ⊢ instead of ⊢ _G when the grammar is clear from the context.) The language of G is defined by L(G)={w∈Σ ^∗∣⊢ _G S(w)}.

An MCFG is an m-MCFG if the dimension of nonterminals does not exceed m. The language of an m-MCFG is called an m-MCFL. It is shown by Seki et al. [14] that each m-MCFG has an equivalent one such that the variables on the right-hand side of any rule all appear in the left-hand side. Such an MCFG is called non-deleting.

A rule $A(\alpha_{1},\dots,\alpha_{q}) \leftarrow B_{1}(\boldsymbol {x}_{1,1},\dots,\boldsymbol {x}_{1,q_{1}}),\dots,B_{n}(\boldsymbol {x}_{n,1},\dots,\boldsymbol {x}_{n,q_{n}})$ is called non-permuting if for each i=1,…,n and each j,k such that 1≤j<k≤q _i , it is not the case that

$$\varphi(\alpha_1 \cdots\alpha_q) = \boldsymbol {x}_{i,k} \boldsymbol {x}_{i,j}, $$

where φ is the homomorphism that erases all symbols in Σ and all variables other than x _i,j and x _i,k . An MCFG G is called non-permuting if all its rules are non-permuting. Every m-MCFG has an equivalent non-deleting non-permuting m-MCFG [10, 11].

A non-deleting non-permuting MCFG is called well-nested if every rule $A(\alpha_{1},\dots, \alpha_{q}) \leftarrow B_{1}(\boldsymbol {x}_{1,1},\dots,\boldsymbol {x}_{1,q_{1}}),\dots,B_{n}(\boldsymbol {x}_{n,q},\dots,\boldsymbol {x}_{n,q_{n}})$ satisfies the following condition: whenever i≠i′, 1≤j<k≤q _i , 1≤j′<k′≤q _i′, it is not the case that

$$\chi(\alpha_1 \cdots\alpha_q) = \boldsymbol {x}_{i,j} \boldsymbol {x}_{i',j'} \boldsymbol {x}_{i,k} \boldsymbol {x}_{i',k'} $$

where χ is the homomorphism that erases all symbols in Σ and all variables other than x _i,j ,x _i,k ,x _i′,j′,x _i′,k′. Kanazawa [6] showed that the languages of well-nested m-MCFGs are all 2m-iterative. See also [8] for the effect of the well-nestedness condition on the generative power of MCFGs.

In order to rigorously define the notion of a derivation tree, we view the rule set P as a ranked alphabet where π∈P has rank n if the right-hand side of π has n occurrences of nonterminals. A derivation tree of G=(N,Σ,P,S) is a local set of trees over P, defined inductively as follows:

• If π=A(u ₁,…,u _q )← is a rule in P, then π is a derivation tree for A(u ₁,…,u _q ).

• If $\pi= A(\alpha_{1},\dots,\alpha_{q}) \leftarrow B_{1}(\boldsymbol {x}_{1,1},\dots,\boldsymbol {x}_{1,q_{1}}),\dots,B_{n}(\boldsymbol {x}_{n,1},\dots,\boldsymbol {x}_{n,q_{n}})$ is a rule in P and for i=1,…,n, T _i is a derivation tree for $B_{i}(w_{i,1},\dots,w_{i,q_{i}})$, then πT ₁⋯T _n is a derivation tree for A(u ₁,…,u _q ), where (u ₁,…,u _q ) is the result of substituting w _i,j for each x _i,j in (α ₁,…,α _q ).

A derivation tree for A(u ₁,…,u _q ) is a derivation tree of type A. A complete derivation tree is a derivation tree of type S, and it is said to be a derivation tree for w if it is a derivation tree for S(w). When T is a derivation tree for a fact A(u ₁,…,u _q ), we also say T derives A(u ₁,…,u _q ). Clearly, ⊢ _G A(u ₁,…,u _q ) holds if and only if G has a derivation tree that derives A(u ₁,…,u _q ).

When a derivation tree of type B contains a derivation tree of type A as a subtree, the result of replacing that subtree by any other derivation tree of type A is again a derivation tree of type B. When a complete derivation tree T for w has a path containing more nodes than the number of nonterminals, then there must be a nonterminal A and two nodes on that path such that the subtree rooted at each of the two nodes is a derivation tree of type A. This is the starting point of Seki et al.’s [14] proof of their pumping lemma.

Example 1

Consider the following 2-MCFG:

$$\begin{aligned} \pi_1\colon& S(\boldsymbol {x}_1 \# \boldsymbol {x}_2) \leftarrow D(\boldsymbol {x}_1, \boldsymbol {x}_2) \\ \pi_2\colon& D(\varepsilon, \varepsilon) \leftarrow \\ \pi_3\colon& D(\boldsymbol {x}_1 \boldsymbol {y}_1, \boldsymbol {x}_2 \boldsymbol {y}_2) \leftarrow E( \boldsymbol {x}_1, \boldsymbol {x}_2), D(\boldsymbol {y}_1, \boldsymbol {y}_2) \\ \pi_4\colon& E(c \boldsymbol {x}_1 \bar{c}, c \boldsymbol {x}_2 \bar{c}) \leftarrow D(\boldsymbol {x}_1, \boldsymbol {x}_2) \end{aligned}$$

(π ₁,π ₂,π ₃,π ₄ are the names of the rules). Here, S is the designated nonterminal, and all other nonterminals are of rank 2. This grammar generates $\{ w \# w \mid w \in D_{1}^{\ast} \}$, where $D_{1}^{\ast}$ is the Dyck language over the alphabet $\{ c, \bar {c} \}$. Note that the third rule is not well-nested. Figure 1 shows a derivation tree for $cc\bar{c}\bar{c}c\bar{c} \# cc\bar{c}\bar{c}c\bar{c}$, alongside of the same tree with each node annotated by the fact derived by the subtree rooted at that node.

Fig. 1

A derivation tree for $cc\bar{c}\bar {c}c\bar{c} \# cc\bar{c}\bar{c}c\bar{c}$ (left) and the same tree augmented with additional information about what fact is derived at each step (right)

3 Counterexample to the Strong Pumping Lemma for 3-MCFLs

We fix two alphabets:

$$\begin{aligned} \varSigma = &\{ c,\bar{c},d,\bar{d} \}, \\ \hat{\varSigma} = &\varSigma\cup\{ a,b \}. \end{aligned}$$

Define a 3-MCFL $H \subseteq\hat{\varSigma}^{\ast}$ by the following 3-MCFG, where we use the symbol H itself as the designated nonterminal:

$$\begin{aligned} H(\boldsymbol {x}_2) \leftarrow& J( \boldsymbol {x}_1,\boldsymbol {x}_2,\boldsymbol {x}_3) \\ J(a\boldsymbol {x}_1, \boldsymbol {y}_1 c\boldsymbol {x}_2 \bar{c}d\boldsymbol {y}_2\bar{d}\boldsymbol {x}_3, \boldsymbol {y}_3 b) \leftarrow& J(\boldsymbol {x}_1, \boldsymbol {x}_2,\boldsymbol {x}_3), J(\boldsymbol {y}_1, \boldsymbol {y}_2,\boldsymbol {y}_3) \\ J(a, \varepsilon, b) \leftarrow& \end{aligned}$$

This is our counterexample to the strong pumping lemma. Note that the second rule is not well-nested. When J(u ₁,u ₂,u ₃) is derivable in this grammar, we always have u ₁=a ^k+1, u ₃=b ^l+1 for some $k,l \in \mathbb {N}$, and u ₂ is either ε or a string of the form $a^{m} c v \bar{c} d w \bar{d} b^{n}$ for some v,w∈H and m,n≥1. In the latter case, the (unique) derivation tree for $J(a^{k+1},a^{m} c v \bar{c} d w \bar{d} b^{n},b^{l+1})$ is a binary tree T where k and n are the numbers of nodes on the leftmost and rightmost branches, respectively, of the left immediate subtree of T, and m and l are the numbers of nodes on the leftmost and rightmost branches, respectively, of the right immediate subtree of T (Fig. 2).

Fig. 2

Derivation tree for $J(a^{k+1},a^{m} c v \bar{c} d w \bar{d} b^{n}, b^{l+1})$

The language H is related to a context-free language over Σ via the homomorphism $\psi\colon\hat{\varSigma}^{\ast} \rightarrow \varSigma^{\ast}$ defined by:

$$\psi(e) = \begin{cases} \varepsilon& \text{if $e \in\{ a,b \}$,}\\ e & \text{if $e \in\varSigma$.} \end{cases} $$

It is easy to see that ψ(H) is a context-free language included in the Dyck language $D_{2}^{\ast}$ over the alphabet Σ, where $(c,\bar{c})$ and $(d,\bar{d})$ are each regarded as a matching pair of parentheses. The homomorphism ψ is an injection when restricted to the strings in H, and for each v∈H, ψ(v) encodes in an obvious way the unique derivation tree for v. We can learn a lot about iterative properties of the 3-MCFL H from the CFL ψ(H), so we begin by studying the latter.

3.1 Properties of the CFL V=ψ(H)

The goal of this section is to state a necessary condition for w∈Σ ⁺ to be in

$$\bigl\{ w \mid\text{$ww$ is a factor of some string in $\psi(H)$} \bigr\} . $$

In what follows, we use regular expressions and (recursive) equations involving regular expressions to define various languages. In regular expressions, the vertical bar “∣” denotes union, and is assumed to have lower precedence than all other operators.

Define the reduction relation ⊳∈Σ ^∗×Σ ^∗ by

$${\vartriangleright} = \bigl\{ (v_1 c \bar{c} v_2, v_1 v_2) \mid v_1,v_2 \in \varSigma^{\ast} \bigr\} \cup\bigl\{ (v_1 d \bar{d} v_2, v_1 v_2) \mid v_1,v_2 \in\varSigma^{\ast} \bigr\} . $$

We write ⊳^∗ for the reflexive transitive closure of the relation ⊳, and ⊳ⁿ for the n-fold composition of ⊳ with itself (more precisely, ⊳ⁿ⁺¹ is ⊳ composed with ⊳ⁿ, where ⊳⁰ is the identity relation). When v⊳^∗ w, we say v reduces to w, and when v⊳ⁿ w, we say v reduces to w in n steps. A string w∈Σ ^∗ is said to be in normal form if neither $c\bar{c}$ nor $d\bar{d}$ is a factor of w. It is well known that the relation ⊳^∗ has the confluence (i.e., Church-Rosser) property and each string w∈Σ ^∗ reduces to a unique string in normal form, which is called the normal form of w. We write $\operatorname{nf}(w)$ for the normal form of w. The Dyck language $D_{2}^{\ast}$ over Σ is defined as $D_{2}^{\ast} = \{ w \in\varSigma^{\ast} \mid\operatorname {nf}(w) = \varepsilon \}$.

Lemma 2

The following conditions hold of all u,v,w,v′∈Σ ^∗:

• (i) If $v \vartriangleright^{\ast}v' \in\bar{c}\varSigma^{\ast}$, then $\operatorname{nf}(vw) \in\bar{c}\varSigma^{\ast}$.

• (ii) If $v \vartriangleright^{\ast}v' \in\bar{d}\varSigma^{\ast}$, then $\operatorname{nf}(vw) \in\bar{d}\varSigma^{\ast}$.

• (iii) If v⊳^∗ v′∈Σ ^∗ c, then $\operatorname{nf}(uv) \in\varSigma^{\ast} c$.

• (iv) If v⊳^∗ v′∈Σ ^∗ d, then $\operatorname{nf}(uv) \in\varSigma^{\ast} d$.

• (v) If $v \vartriangleright^{\ast}v' \in\varSigma^{\ast} c\bar{d} \varSigma ^{\ast}$, then $\operatorname{nf}(uvw) \in\varSigma^{\ast} c\bar{d} \varSigma^{\ast}$.

• (vi) If $v \vartriangleright^{\ast}v' \in\varSigma^{\ast} d\bar{c} \varSigma ^{\ast}$, then $\operatorname{nf}(uvw) \in\varSigma^{\ast} d\bar{c} \varSigma^{\ast}$.

Proof

(i). Since $v \vartriangleright^{\ast}v' \in\bar{c} \varSigma^{\ast}$ implies $vw \vartriangleright^{\ast}v'w \in\bar{c} \varSigma^{\ast}$ and, by the confluence property, $\operatorname{nf}(vw) = \operatorname{nf}(v'w)$, it suffices to show that $z \in\bar{c} \varSigma^{\ast}$ implies $\operatorname{nf}(z) \in\bar{c} \varSigma ^{\ast}$ for all z∈Σ ^∗. We prove this by induction on the number of reduction steps from z to $\operatorname{nf}(z)$. Suppose $z = \bar{c} y$. If $z = \operatorname{nf}(z)$, then $\operatorname{nf}(z) \in\bar{c} \varSigma^{\ast}$. Otherwise, $z = \bar{c}y \mathrel{\vartriangleright}^{n} \operatorname{nf}(z)$ for some n≥1. Then $\bar{c} y \mathrel{\vartriangleright} x \mathrel{\vartriangleright}^{n-1} \operatorname{nf}(z) = \operatorname{nf}(x)$ for some $x \in\bar{c}\varSigma^{\ast}$. By the induction hypothesis applied to x, we obtain $\operatorname{nf}(z) \in\bar{c}\varSigma^{\ast}$.

Part (ii)–(vi) may be proved similarly. □

Lemma 3

Let w∈Σ ^∗ and suppose $\operatorname{nf}(w) = e_{1} \cdots e_{n}$ for some e ₁,…,e _n ∈Σ. Then there exist u ₀,…,u _n ∈Σ ^∗ such that w=u ₀ e ₁ u ₁⋯e _n u _n and $\operatorname{nf}(u_{i}) = \varepsilon$ for i=0,…,n.

Proof

By induction on the number of reduction steps from w to e ₁⋯e _n . □

If K is a set of strings, let $\operatorname {fac}(K)$ be the set of factors of elements of K, i.e.,

$$\operatorname {fac}(K) = \{ v \mid uvw \in K \}. $$

Since the relation “is a factor of” is reflexive and transitive, $\operatorname {fac}(\operatorname {fac}(K)) = \operatorname {fac}(K)$ always holds.

Lemma 4

For every $w \in \operatorname {fac}(D_{2}^{\ast})$, it holds that $\operatorname {nf}(w) \in(\bar{c} \mid\bar{d})^{\ast} (c \mid d)^{\ast}$.

Proof

By the definition of normal form, $\operatorname{nf}(w)$ cannot contain $c\bar{c}$ or $d\bar{d}$ as a factor. Now $\operatorname {nf}(w)$ cannot contain $c\bar{d}$ or $d\bar{c}$ as a factor, either. To see this, let $uwv \in D_{2}^{\ast}$ and suppose $c\bar{d}$ or $d\bar{c}$ is a factor of $\operatorname{nf}(w)$. Then by Lemma 2, part (v) and (vi), $\operatorname{nf}(uwv)$ contains $c\bar {d}$ or $d\bar{c}$ as a factor, contradicting $\operatorname{nf}(uwv) = \varepsilon$. The desired conclusion now follows easily. □

Lemma 5

If $vw \in D_{2}^{\ast}$, then $\operatorname{nf}(v) \in(c \mid d)^{\ast}$ and $\operatorname{nf}(w) \in(\bar{c} \mid\bar {d})^{\ast}$.

Proof

Suppose $vw \in D_{2}^{\ast}$. By Lemma 4, $\operatorname {nf}(v)$ and $\operatorname{nf}(w)$ both belong to $(\bar{c} \mid \bar{d})^{\ast} (c \mid d)^{\ast}$. If $\operatorname{nf}(v) \in (\bar{c} \mid\bar{d})^{+} (c \mid d)^{\ast}$, then by Lemma 2, part (i) and (ii), $\operatorname{nf}(vw) \in(\bar{c} \mid \bar{d}) \varSigma^{\ast}$, contradicting $vw \in D_{2} ^{\ast}$. Hence $\operatorname{nf}(v) \in(c \mid d)^{\ast}$. Similarly, we can conclude $\operatorname{nf}(w) \in(\bar{c} \mid\bar{d})^{\ast}$ using Lemma 2, part (iii) and (iv). □

The set D ₂ of Dyck primes over Σ is defined as $D_{2} = c D_{2}^{\ast} \bar{c} \mid d D_{2}^{\ast} \bar{d}$. It is well known and easy to see that $D_{2}^{\ast}$ indeed equals (D ₂)^∗.

Define context-free languages V,L,R by⁶

$$\begin{aligned} V & = \varepsilon\mid LR, \\ L & = cV\bar{c}, \\ R & = dV\bar{d}. \end{aligned}$$

Then it is easy to see that $V \subset D_{2}^{\ast}$, L⊂D ₂, R⊂D ₂.

Lemma 6

$\operatorname {fac}(V) \cap\varSigma^{2} = \{ cc,c\bar{c},\bar{c}d,dc,d\bar{d},\bar {d}\bar{c},\bar{d}\bar{d} \}$.

Proof

First, note that V=ε∣LR implies that every v∈V satisfies $v \in\varepsilon\mid c \varSigma^{\ast} \bar{d}$. Let F be the set on the right-hand side of the equation to be proved. We can show by induction on the length of v that v∈V and $w \in \operatorname {fac}(v) \cap\varSigma^{2}$ imply w∈F. Suppose v∈V and $w \in \operatorname {fac}(v) \cap\varSigma^{2}$. Then $v \in LR = cV\bar{c} dV\bar{d}$, so $v = c v_{1} \bar{c} d v_{2} \bar{d}$ for some v ₁,v ₂∈V. Hence either $w \in \operatorname {fac}(\{ v_{1},v_{2} \}) \cap\varSigma^{2}$ or $w \in\{ cc,c\bar{c},\bar {d}\bar{c},\bar{c}d,dc,d\bar{d}, \bar{d}\bar{d} \} = F$. By induction hypothesis, $\operatorname {fac}(\{ v_{1},v_{2} \}) \cap\varSigma^{2} \subseteq F$, so it follows that w∈F. This establishes $\operatorname {fac}(V) \cap \varSigma^{2} \subseteq F$. To see the converse inclusion, just note that for $u = cc\bar{c}d\bar{d}\bar{c}dc\bar{c}d\bar{d}\bar{d} \in V$, we have $\operatorname {fac}(u) \cap\varSigma^{2} = F$. □

Lemma 7

V=ψ(H).

Proof

Applying the homomorphism ψ in each rule of the 3-MCFG for H, we get

$$\begin{aligned} H(\boldsymbol {x}_2) \leftarrow& J( \boldsymbol {x}_1,\boldsymbol {x}_2,\boldsymbol {x}_3) \\ J(\boldsymbol {x}_1,\boldsymbol {y}_1 c \boldsymbol {x}_2 \bar{c} d \boldsymbol {y}_2 \bar{d} \boldsymbol {x}_3, \boldsymbol {y}_3) \leftarrow& J(\boldsymbol {x}_1, \boldsymbol {x}_2,\boldsymbol {x}_3), J(\boldsymbol {y}_1, \boldsymbol {y}_2,\boldsymbol {y}_3) \\ J(\varepsilon,\varepsilon,\varepsilon) \leftarrow& \end{aligned}$$

In this grammar, whenever J(u ₁,u ₂,u ₃) is derivable, u ₁=u ₃=ε. So the first and third arguments of J can be dropped, and the grammar can be simplified to

$$\begin{aligned} J(c \boldsymbol {x} \bar{c} d \boldsymbol {y} \bar{d}) \leftarrow& J(\boldsymbol {x}), J(\boldsymbol {y}) \\ J(\varepsilon) \leftarrow& \end{aligned}$$

This is just a context-free grammar for V. □

Lemma 8

$D_{2} \cap \operatorname {fac}(V) = L \mid R$.

Proof

Since V=ε∣LR and L∣R⊆D ₂, it is clear that $L \mid R \subseteq D_{2} \cap \operatorname {fac}(V)$.

For the converse inclusion, we prove by induction on the length of x∈V that x=uvw and v∈D ₂ implies v∈L∣R. The base case of x=ε is trivial. For the induction step, let $x = c y \bar{c} d z \bar{d}$, where y,z∈V, and suppose x=uvw and v∈D ₂. We distinguish three cases.

Case 1.  v is a factor of $c y \bar{c}$. If $v = cy\bar {c}$, then v∈L, and if v is a factor of y, then v∈L∣R by the induction hypothesis. If v=cy′, where y′ is a prefix of y, then $\operatorname{nf}(v) = \operatorname{nf}(cy') \in c(c \mid d)^{\ast}$ by Lemma 5. So $\operatorname{nf}(v) \neq\varepsilon$, contradicting v∈D ₂. Likewise, if $v = y''\bar{c}$, where y″ is a suffix of y, then $\operatorname {nf}(v) = \operatorname{nf}(y''\bar{c}) \in(\bar{c} \mid\bar {d})^{\ast} \bar{c}$ and $\operatorname{nf}(v) \neq\varepsilon$, contradicting v∈D ₂.

Case 2.  v is a factor of $d z \bar{d}$. This case is completely analogous to Case 1, and we can conclude v∈L∣R.

Case 3.  v=v′v″, where v′ is a non-empty suffix of $c y \bar{c}$ and v″ is a non-empty prefix of $d z \bar{d}$. Since v∈D ₂, v cannot equal $x = c y \bar{c} d z \bar{d}$. So either v′ is a suffix of $y \bar{c}$, in which case $\operatorname{nf}(v) = \operatorname{nf}(v'v'') \in(\bar{c} \mid\bar{d})^{\ast} \bar {c} (c \mid d)^{\ast}$ by Lemma 5, or else v″ is a prefix of dz, in which case $\operatorname{nf}(v) = \operatorname {nf}(v' v'') \in(\bar{c} \mid\bar{d})^{\ast} d (c \mid d)^{\ast }$, again by Lemma 5. In either case, $\operatorname {nf}(v) \neq\varepsilon$, contradicting v∈D ₂.

We have seen that v∈L∣R holds in all cases, and the induction step is complete. □

Lemma 9

$D_{2}^{\ast} \cap \operatorname {fac}(V) = V \mid L \mid R$.

Proof

Since V=ε∣LR and L∣R⊆D ₂, it is clear that $V \mid L \mid R \subseteq D_{2}^{\ast} \cap \operatorname {fac}(V)$.

For the converse inclusion, suppose $w \in D_{2}^{\ast} \cap \operatorname {fac}(V)$. Since any factor of a string in $\operatorname {fac}(V)$ is itself in $\operatorname {fac}(V)$, it follows that $w \in(D_{2} \cap \operatorname {fac}(V))^{\ast}$. By Lemma 8, $w \in(L \mid R)^{\ast} \cap \operatorname {fac}(V)$. Since any string in LL∣RL∣RR has one of $\bar{c}c, \bar{d}c, \bar {d}d$ as a factor, Lemma 6 implies $(LL \mid RL \mid RR) \cap \operatorname {fac}(V) = \varnothing$. It follows that $(L \mid R)^{2} \cap \operatorname {fac}(V) = LR$ and for n≥3,

$$\begin{aligned} (L \mid R)^n \cap \operatorname {fac}(V) & = \bigl((L \mid R)^2 \cap \operatorname {fac}(V)\bigr) (L \mid R)^{n-2} \cap \operatorname {fac}(V) \\ & = LR(L \mid R)^{n-2} \cap \operatorname {fac}(V) \\ & \subseteq L\bigl((RL \mid RR) \cap \operatorname {fac}(V)\bigr) (L \mid R)^{n-3} \\ & = \varnothing. \end{aligned}$$

So

$$\begin{aligned} w & \in\bigl(\varepsilon\mid(L \mid R) \mid(L \mid R)^2\bigr) \cap \operatorname {fac}(V) \\ & = \varepsilon\mid(L \mid R) \mid LR \\ & = V \mid L \mid R. \end{aligned}$$

This proves $D_{2}^{\ast} \cap \operatorname {fac}(V) \subseteq V \mid L \mid R$. □

Lemma 10

Let u,w∈Σ ^∗ and v∈Σ ⁺. If uv∈V and vw∈V, then u=w=ε.

Proof

Since $V \subset D_{2}^{\ast}$, Lemma 5 implies $\operatorname{nf}(v) \in(\bar{c} \mid\bar{d})^{\ast} \cap(c \mid d)^{\ast}$, and hence $\operatorname{nf}(v) = \varepsilon$. It follows that $\operatorname{nf}(u) = \operatorname{nf}(w) = \varepsilon$, too, and hence u,v,w are all in $D_{2}^{\ast}$. By Lemma 9, u,v,w are all in V∣L∣R. Since v≠ε, the strings uv and vw are both in $V - \{ \varepsilon\} = LR = cV\bar{c}dV\bar{d}$. So v ends in $\bar {d}$ and begins in c. If u≠ε, then u∈LR∣L∣R, so $u \in\varSigma^{\ast} (\bar{c} \mid\bar{d})$. This implies either $\bar{c}c$ or $\bar{d}c$ is a factor of uv∈V, contradicting Lemma 6. Therefore, u=ε. Similarly, we can use Lemma 6 to conclude w=ε. □

We say that a string u is a proper prefix (proper suffix) of a string v if u is a prefix (suffix) of v and u≠v. Lemma 10 implies that no proper prefix or proper suffix of a string in V can belong to V, which is to say that V is both prefix-free and suffix-free.

Lemma 11

$$\begin{aligned} \operatorname {fac}(V) \subseteq & (V \mid L \mid R) \mid{} \\ & (V \mid R) (\bar{c}R \mid\bar{d})^{\ast} (\bar{c} \mid\bar{c}R \mid \bar{d}) \mid \\ & (c \mid Ld \mid d) (c \mid Ld)^{\ast} (V \mid L) \mid{} \\ & (V \mid R) (\bar{c}R \mid\bar{d})^{\ast} \bar{c} d (c \mid Ld)^{\ast} (V \mid L). \end{aligned}$$

Proof

Suppose $w \in \operatorname {fac}(V)$. By Lemma 4, $\operatorname {nf}(w) \in(\bar{c} \mid\bar{d})^{m} (c \mid d)^{n}$ for some m, n≥0, and by Lemma 3, there are strings u ₀,…,u _m+n such that $\operatorname{nf}(u_{i}) = \varepsilon$ for each i=0,…,m+n and

$$w \in u_0 (\bar{c} \mid\bar{d}) u_1 \cdots(\bar{c} \mid \bar{d}) u_m (c \mid d) u_{m+1} \cdots(c \mid d) u_{m+n}. $$

Since u _i is a factor of $w \in \operatorname {fac}(V)$, $u_{i} \in D_{2}^{\ast} \cap \operatorname {fac}(V)$. Lemma 9 then implies u _i ∈V∣L∣R.

By Lemma 6, each of the following sets is disjoint from $\operatorname {fac}(V)$:

$$\begin{aligned} & \bar{c}(\bar{c} \mid\bar{d}),\qquad (c \mid d)d, \\ &\bar{d}(c \mid d),\qquad (\bar{c} \mid\bar{d})c. \end{aligned}$$

This implies that the following conditions hold:

$$\begin{aligned} &u_0 \in V \mid R\quad\mbox{if $m \geq1$,} \end{aligned}$$

(2)

$$\begin{aligned} &u_{m+n} \in V \mid L\quad\mbox{if $n \geq1$,} \end{aligned}$$

(3)

$$\begin{aligned} &u_i \in\varepsilon\mid R\quad\mbox{if $u_{i}$ is preceded by $\bar {c}$,} \end{aligned}$$

(4)

$$\begin{aligned} &u_i \in R\quad\mbox{if $u_{i}$ is preceded by $\bar{c}$ and is followed by $\bar{c}$ or $\bar{d}$,} \end{aligned}$$

(5)

$$\begin{aligned} &u_i = \varepsilon\quad\mbox{if $u_{i}$ is preceded by $ \bar{d}$,} \end{aligned}$$

(6)

$$\begin{aligned} &u_i = \varepsilon\quad\mbox{if $u_{i}$ is followed by $c$,} \end{aligned}$$

(7)

$$\begin{aligned} &u_i \in\varepsilon\mid L\quad\mbox{if $u_{i}$ is followed by $d$,} \end{aligned}$$

(8)

$$\begin{aligned} &u_i \in L\quad\mbox{if $u_{i}$ is preceded by $c$ or $d$ and is followed by $d$.} \end{aligned}$$

(9)

Case 1.  m=n=0. Then w=u ₀∈V∣L∣R.

Case 2.  m≥1,n=0. Then $w \in u_{0} (\bar{c} \mid \bar{d}) u_{1} \cdots(\bar{c} \mid\bar{d}) u_{m}$. By (2), (4), (5), and (6), we get $w \in(V \mid R)(\bar{c}R \mid\bar{d})^{\ast} (\bar{c} \mid\bar{c} R \mid \bar{d})$.

Case 3.  m=0,n≥1. Then w∈u ₀(c∣d)⋯u _n−1(c∣d)u _n . By (3), (7), (8), and (9), we get w∈(c∣Ld∣d)(c∣Ld)^∗(V∣L).

Case 4.  m,n≥1. By (4), (6), (7), and (8), we see that u _m =ε. Since $(\bar{c}c \mid\bar{d}c \mid\bar{d}d) \cap \operatorname {fac}(V) = \varnothing$,

$$w \in u_0 (\bar{c} \mid\bar{d}) u_1 \cdots(\bar{d} \mid \bar{d}) u_{m-1} \bar{c} d u_{m+1} (c \mid d) \cdots u_{m+n-1} (c \mid d) u_{m+n}. $$

By (2), (3), (5), (6), (7), and (9), we see that $w \in(V \mid R)(\bar{c}R \mid\bar{d})^{\ast} \bar{c}d (c \mid Ld)^{\ast} (V \mid L)$.

This proves the lemma. □

Lemma 12

If w∈Σ ⁺ and $ww \in \operatorname {fac}(V)$, then one of the following conditions holds:

• (i) $w \in(\bar{c}R \mid\bar{d})^{+}$.

• (ii) $w \in R (\bar{c}R \mid\bar{d})^{\ast} \bar{c}$.

• (iii) w∈(c∣Ld)⁺.

• (iv) w∈d(c∣Ld)^∗ L.

• (v) $w \in(V \mid R)(\bar{c}R \mid\bar{d})^{m} \bar{c}d (c \mid Ld)^{n} (V \mid L)$ for some m,n≥0 such that m≠n.

Proof

Suppose w≠ε and $ww \in \operatorname {fac}(V)$. Since $w \in \operatorname {fac}(V)$, by Lemma 11,

$$\begin{aligned} \operatorname {fac}(V) \subseteq& (V \mid L \mid R) \mid{} \\ & (V \mid R) (\bar{c}R \mid\bar{d})^{\ast} (\bar{c} \mid\bar{c}R \mid \bar{d}) \mid{} \\ & (c \mid Ld \mid d) (c \mid Ld)^{\ast} (V \mid L) \mid{} \\ & (V \mid R) (\bar{c}R \mid\bar{d})^{\ast} \bar{c} d (c \mid Ld)^{\ast} (V \mid L). \end{aligned}$$

Case 1.  w∈V∣L∣R. Since w≠ε, w∈LR∣L∣R. It follows that ww has one of $\bar{d}c, \bar{c}c, \bar{d}d$ as a factor, which contradicts $ww \in \operatorname {fac}(V)$ by Lemma 6. So this case is impossible.

Case 2.  $w \in(V \mid R)(\bar{c}R \mid\bar{d})^{\ast} (\bar{c} \mid\bar{c}R \mid\bar{d})$. If w starts in c, then ww contains either $\bar{c}c$ or $\bar{d}c$ as a factor, which contradicts $ww \in \operatorname {fac}(V)$ by Lemma 6. So

$$w \in(\varepsilon\mid R) (\bar{c}R \mid\bar{d})^{\ast} (\bar{c} \mid \bar{c}R \mid\bar{d}). $$

Case 2.1.  $w \in(\bar{c}R \mid\bar{d})^{\ast} (\bar{c} \mid\bar{c}R \mid \bar{d})$. If w ends in $\bar{c}$, ww contains either $\bar {c}\bar{c}$ or $\bar{c}\bar{d}$ as a factor, which contradicts $ww \in \operatorname {fac}(V)$ by Lemma 6. So in this case $w \in(\bar {c}R \mid\bar{d})^{\ast} (\bar{c}R \mid\bar{d}) = (\bar{c}R \mid \bar{d})^{+}$.

Case 2.2.  $w \in R(\bar{c}R \mid\bar{d})^{\ast} (\bar{c} \mid\bar{c}R \mid \bar{d})$ In this case, w starts in d. If w ends in $\bar{d}$, then ww contains either $\bar{d}d$ as a factor, contradicting $ww \in \operatorname {fac}(V)$ by Lemma 6. So in this case $w \in R(\bar {c}R \mid\bar{d})^{\ast} \bar{c}$.

Case 3.  w∈(c∣Ld∣d)(c∣Ld)^∗(V∣L). This case is exactly symmetric to Case 2, and we can conclude w∈(c∣Ld)⁺ or w∈d(c∣Ld)^∗ L.

Case 4.  $w \in(V \mid R) (\bar{c}R \mid\bar{d})^{\ast} \bar{c} d (c \mid Ld)^{\ast} (V \mid L)$. Let m,n≥0 be such that

$$w \in(V \mid R) (\bar{c}R \mid\bar{d})^m \bar{c}d (c \mid Ld)^n (V \mid L). $$

We show that m≠n. Suppose, by way of contradiction, m=n. Then ww contains a factor u that belongs to

$$d(c \mid Ld)^n (V \mid L) (V \mid R) (\bar{c}R \mid \bar{d})^n \bar{c}. $$

Note that

$$u \vartriangleright^{\ast}u' \in d(c \mid d)^n (\bar{c} \mid\bar {d})^n \bar{c}. $$

It is easy to see from this that $\operatorname{nf}(u)$ has either $c \bar{d}$ or $d \bar{c}$ as a factor. But since u is a factor of ww, $u \in \operatorname {fac}(V) \subseteq \operatorname {fac}(D_{2}^{\ast})$. By Lemma 4, $\operatorname{nf}(u) \in(\bar{c} \mid\bar{d})^{\ast } (c \mid d)^{\ast}$, a contradiction.

We have proved that one of (i)–(v) holds in each case. □

3.2 Properties of the 3-MCFL H

Lemma 12 immediately yields a necessary condition for membership in $\{ w \in\hat{\varSigma}^{+} \mid ww \in \operatorname {fac}(H) \}$. For w to be in this set, it must be that $\psi(w)\psi(w) = \psi (ww) \in\psi(\operatorname {fac}(H)) = \operatorname {fac}(\psi(H)) = \operatorname {fac}(V)$, so either ψ(w)=ε, in which case w∈a ⁺∣b ⁺, or ψ(w) must satisfy one of the five conditions in Lemma 12. This will be used in the next section to give a necessary condition for membership in

$$\bigl\{ w \in\hat{\varSigma}^+ \mid ww \in \operatorname {fac}(H) \bigr\} \cap \operatorname {fac}\bigl(\{ v_n \mid n \in \mathbb {N}\}\bigr), $$

where $\{ v_{n} \mid n \in \mathbb {N}\}$ is a certain infinite subset of H. In this section, we establish some general properties of H that will be useful in the next section.

Lemma 13

For every v∈V, there is a unique string w∈H such that ψ(w)=v.

Proof

We prove by induction on the length of v∈V that there is a unique triple (w ₁,w ₂,w ₃) such that J(w ₁,w ₂,w ₃) is derivable and ψ(w ₂)=v. It is clear from the grammar for H that ⊢J(w ₁,w ₂,w ₃) and ψ(w ₂)=ε imply w ₁=a,w ₂=ε,w ₃=b. This takes care of the case v=ε. Now suppose v∈LR. Then $v = cu_{1}\bar{c} du_{2}\bar{d}$ for some u ₁,u ₂∈V. Note that the choice of u ₁ and u ₂ is unique. For, if $v = cu_{1}'\bar{c} du_{2}'\bar{d}$ for some $u_{1}',u_{2}' \in V$, then $u_{1}'$ either is a prefix of u ₁ or contains u ₁ as a prefix, which implies $u_{1} = u_{1}'$ by Lemma 10. Similarly, $u_{2}'$ either is a suffix of u ₂ or contains u ₂ as a suffix, and it follows that $u_{2} = u_{2}'$. If ⊢J(w ₁,w ₂,w ₃) and ψ(w ₂)=v, then w ₂ cannot be ε and there must be some x ₁,y ₁∈a ⁺, x ₂,y ₂∈H, and x ₃,y ₃∈b ⁺ such that

$$\begin{aligned} \vdash& J(x_1,x_2,x_3), \\ \vdash& J(y_1,y_2,y_3), \\ w_1 = & a x_1, \\ w_2 = & y_1 c x_2 \bar{c} d y_2 \bar{d} x_3, \\ w_3 = & y_3 b. \end{aligned}$$

Since ψ(w ₂)=v, we have $c \psi(x_{2}) \bar{c} d \psi(y_{2}) \bar{d} = c u_{1}\bar{c} du_{2}\bar{d}$. Since x ₂,y ₂∈H, both ψ(x ₂) and ψ(y ₂) are in ψ(H)=V. It follows that ψ(x ₂)=u ₁ and ψ(y ₂)=u ₂. By induction hypothesis, (x ₁,x ₂,x ₃) and (y ₁,y ₂,y ₃) are uniquely determined by u ₁ and u ₂, respectively. Since u ₁ and u ₂ are uniquely determined by v, the triple (w ₁,w ₂,w ₃) is uniquely determined by v. □

Let $\mathtt {\$}$ be a symbol not in $\hat{\varSigma}$. We use this symbol to mark the beginning and end of a string in H.

Lemma 14

$\operatorname {fac}(\mathtt {\$}H \mathtt {\$}) \cap(\{ \mathtt {\$}\} \cup \hat{\varSigma})^{2} = \{ \mathtt {\$}\mathtt {\$}, \mathtt {\$}a, aa,ac,b\mathtt {\$}, bb,b\bar{c},b\bar{d},ca,c\bar{c},\bar{c}d,da, d\bar{d},\bar{d}b \}$.

Proof

Let F denote the set on the right-hand side of the equation. We prove by induction on the length of u ₂ that ⊢J(u ₁,u ₂,u ₃) implies $\operatorname {fac}(\mathtt {\$}u_{2} \mathtt {\$}) \cap(\{ \mathtt {\$}\} \cup\hat {\varSigma})^{2} \subseteq F$. For the induction basis, observe that $\operatorname {fac}(\mathtt {\$}\varepsilon \mathtt {\$}) \cap(\{ \mathtt {\$}\} \cup\hat{\varSigma })^{2} = \{ \mathtt {\$}\mathtt {\$}\} \subseteq F$. Now suppose for some x ₁,x ₂,x ₃,y ₁,y ₂,y ₃ such that ⊢J(x ₁,x ₂,x ₃) and ⊢J(y ₁,y ₂,y ₃), we have $u_{1} = ax_{1}, u_{2} = y_{1} c x_{2} \bar{c} d y_{2} \bar{d} x_{3}, u_{3} = y_{3} b$. It follows from the induction hypothesis applied to x ₂ and y ₂ that

$$\begin{aligned} \operatorname {fac}(c x_2 \bar{c}) \cap\hat{\varSigma}^2 & \subseteq \bigl(F - \{ \mathtt {\$}\mathtt {\$}, \mathtt {\$}a, b \mathtt {\$}\}\bigr) \cup\{ c \bar{c}, ca, b \bar{c} \} \\ & = F - \{ \mathtt {\$}\mathtt {\$}, \mathtt {\$}a, b \mathtt {\$}\} \\ \operatorname {fac}(d y_2 \bar{d}) \cap\hat{\varSigma}^2 & \subseteq \bigl(F - \{ \mathtt {\$}\mathtt {\$}, \mathtt {\$}a, b \mathtt {\$}\}\bigr) \cup\{ d \bar{d}, da, b \bar{d} \} \\ & = F - \{ \mathtt {\$}\mathtt {\$}, \mathtt {\$}a, b \mathtt {\$}\}. \end{aligned}$$

Since y ₁∈a ⁺ and x ₃∈b ⁺, we get

$$\begin{aligned} &\operatorname {fac}(\mathtt {\$}y_1 c x_2 \bar{c} d y_2 \bar{d} x_3 \mathtt {\$}) \cap\bigl(\{ \mathtt {\$}\} \cup\hat{\varSigma} \bigr)^2 \\ &\quad \subseteq \{ \mathtt {\$}a, aa, ac \} \cup\bigl(\operatorname {fac}(c x_2 \bar{c}) \cap\hat{\varSigma }^2\bigr) \cup\{ \bar{c} d \} \cup\bigl(\operatorname {fac}(d y_2 \bar{d}) \cap\hat {\varSigma}^2\bigr) \cup\{ \bar{d} b, bb, b\mathtt {\$}\} \\ &\quad \subseteq F. \end{aligned}$$

Therefore, $\operatorname {fac}(\mathtt {\$}H \mathtt {\$}) \cap(\{ \mathtt {\$}\} \cup\hat {\varSigma})^{2} \subseteq F$. To see the converse inclusion, note that for $v \,{=}\, aacac\bar{c}d\bar{d}b\bar{c}dac\bar{c}d\bar{d}b\bar{d}bb \in H$, we have $\operatorname {fac}(\mathtt {\$}v \mathtt {\$}) \,{\cap}\,(\{ \mathtt {\$}\} \,{\cup}\,\hat {\varSigma})^{2} \,{=}\, F \,{-}\, \{ \mathtt {\$}\mathtt {\$}\}$. □

Lemma 15

Let $u,w \in\hat{\varSigma}^{\ast}$ and $v \in\hat{\varSigma}^{+}$. If uv∈H and vw∈H, then u=w=ε.

Proof

Since v≠ε, Lemma 14 implies that both uv and vw start in a and end in b. Hence v starts in a and ends in b. By Lemma 14, the only symbols that can follow a in v are a and c, and the only symbols that can precede b in v are b and $\bar{d}$. So $v \in a^{+} c \hat{\varSigma }^{\ast} \bar{d} b^{+}$. Since ψ(v)≠ε and ψ(uv) and ψ(vw) are both in ψ(H)=V, Lemma 10 implies that ψ(u)=ψ(w)=ε. Hence ψ(uv)=ψ(vw), and by Lemma 13, uv=vw. But ψ(u)=ψ(w)=ε implies u∈a ^∗ and w∈b ^∗, and it easily follows that u=w=ε. □

Lemma 15 implies that H is both prefix-free and suffix-free.

Lemma 16

• (i) $H \subseteq\varepsilon\mid(a^{+} c)^{+} \bar{c} \hat{\varSigma}^{\ast} d (\bar{d} b^{+})^{+}$.

• (ii) If ⊢J(u ₁,u ₂,u ₃) and $u_{2} \in(a^{\ast} c)^{k} (\bar{c} \hat {\varSigma}^{\ast} d \mid\varepsilon) (\bar{d} b^{\ast})^{l}$, then u ₁=a ^k+1 and u ₃=b ^l+1.

Proof

(i). Suppose v≠ε and v∈H. We reason using Lemma 14. The first symbol of v must be a. Also, in v, the only symbols that can follow a are a and c, and the only symbols that can follow c are a and $\bar{c}$. Since the last symbol of v must be b, it follows that v has a prefix that belongs to $(a^{+}c)^{+} \bar{c}$. By a symmetric reasoning, v has a suffix that belongs to $d (\bar{d} b^{+})^{+}$. Therefore, $v \in(a^{+} c)^{+} \bar{c} \hat{\varSigma}^{\ast} d (\bar{d} b^{+})^{+}$.

(ii). We prove this part⁷ by induction on the length of u ₂. Suppose ⊢J(u ₁,u ₂,u ₃). If $u_{2} = \varepsilon\in(a^{\ast} c)^{0} (\bar{c} \hat{\varSigma}^{\ast} d \mid\varepsilon) (\bar{d} b^{\ast})^{0}$, then we must have u ₁=a ¹ and u ₃=b ¹. If u≠ε, then there exist x ₁,x ₂,x ₃,y ₁,y ₂,y ₃ such that ⊢J(x ₁,x ₂,x ₃), ⊢J(y ₁,y ₂,y ₃), u ₁=ax ₁, $u_{2} = y_{1} c x_{2} \bar{c} d y_{2} \bar{d} x_{3}$, u ₃=y ₃ b. Suppose $u_{2} \in (a^{\ast} c)^{k}(\bar{c}\hat{\varSigma}^{\ast} d\mid\varepsilon)(\bar {d}b^{\ast})^{l}$. Since y ₁∈a ^∗ and x ₃∈b ^∗, we have k,l≥1, and part (i) of the lemma implies that for some m,n≥0,

$$\begin{aligned} x_2 \in &\bigl(a^{\ast} c\bigr)^{k-1}\bigl(\bar{c} \hat{\varSigma}^{\ast} d\mid \varepsilon\bigr) \bigl(\bar{d}b^{\ast} \bigr)^m, \\ y_2 \in& \bigl(a^{\ast} c\bigr)^n\bigl(\bar{c} \hat{\varSigma}^{\ast} d\mid \varepsilon\bigr) \bigl(\bar{d}b^{\ast} \bigr)^{l-1}. \end{aligned}$$

By induction hypothesis, x ₁=a ^k and y ₃=b ^l. Therefore, u ₁=a ^k+1 and u ₃=b ^l+1. □

Note that by Lemma 14, in any string in H, $\bar{c}$ always precedes d and d always follows $\bar{c}$.

Lemma 17

For all $u,v \in\hat{\varSigma}^{\ast}$, the following conditions hold:

• (i) If ucv∈H, then for some k≥1,

  $$u \in\bigl(\varepsilon\mid\hat{\varSigma}^{\ast} (c \mid d)\bigr) a^k,\qquad a^k c v \in H \bigl(\varepsilon\mid(\bar{c} \mid \bar{d}) \hat{\varSigma }^{\ast}\bigr) $$

• (ii) If $u\bar{d}v \in H$, then for some l≥1,

  $$u \bar{d} b^l \in\bigl(\varepsilon\mid\hat{\varSigma}^{\ast} (c \mid d)\bigr) H,\qquad v \in b^l \bigl(\varepsilon\mid(\bar{c} \mid \bar{d}) \hat{\varSigma }^{\ast}\bigr). $$

• (iii) If $u \bar{c}d v \in H$, then for some k,l≥1,

  $$u \in\bigl(\varepsilon\mid\hat{\varSigma}^{\ast} (c \mid d)\bigr) a^k c H,\qquad v \in H \bar{d} b^l \bigl(\varepsilon\mid( \bar{c} \mid\bar{d}) \hat {\varSigma}^{\ast}\bigr). $$

Proof

Each of the three conditions can be proved by easy induction on the combined length of u and v. We only prove (i). Suppose ucv∈H. Since ucv≠ε, there must be y ₁∈a ⁺, x ₂,y ₂∈H, and x ₃∈b ⁺ such that $ucv = y_{1} c x_{2} \bar{c} d y_{2} \bar{d} x_{3}$. If u=y ₁, then we can take a ^k=y ₁. Otherwise, either $u = y_{1} c x_{2}', v = x_{2}'' \bar{c} d y_{2} \bar{d} x_{3}$ for some $x_{2}',x_{2}''$ such that $x_{2} = x_{2}' c x_{2}''$, or $u = y_{1} c x_{2} \bar{c} d y_{2}', v = y_{2}'' \bar{d} x_{3}$ for some $y_{2}',y_{2}''$ such that $y_{2} = y_{2}' c y_{2}''$. In the former case, we can apply the induction hypothesis to $x_{2}',x_{2}''$ and obtain $x_{2}' \in(\varepsilon\mid\hat {\varSigma}^{\ast}(c \mid d))a^{k}$ and $a^{k} cx_{2}'' \in H(\varepsilon\mid (\bar{c} \mid\bar{d})\hat{\varSigma}^{\ast})$ for some k≥1. It follows that $u = y_{1} c x_{2}' \in\hat{\varSigma}^{\ast}(c \mid d)a^{k}$ and $a^{k}cv = a^{k}cx_{2}''\bar{c}dy_{2}\bar{d}x_{3} \in H(\bar{c} \mid\bar{d})\hat{\varSigma}^{\ast}$. In the latter case, we can apply the induction hypothesis to $y_{2}', y_{2}''$ and obtain $y_{2}' \in (\varepsilon\mid \hat{\varSigma}^{\ast}(c \mid d))a^{k}$ and $a^{k} c y_{2}'' \in H(\varepsilon\mid(\bar{c} \mid\bar{d})\hat{\varSigma }^{\ast})$ for some k≥1, and we can similarly infer $u = y_{1} c x_{2} \bar{c} d y_{2}' \in\hat{\varSigma}^{\ast}(c \mid d)a^{k}$ and $a^{k} c v = a^{k} c y_{2}'' \bar{d} x_{3} \in H (\bar{c} \mid\bar{d})\hat{\varSigma }^{\ast}$. □

Lemma 18

Suppose $w \in \operatorname {fac}(\mathtt {\$}H \mathtt {\$})$. For all k,l≥0, the following conditions hold:

• (i) $w \in(\mathtt {\$}\mid c \mid d) a^{k} c H \bar{c} d (a^{\ast} c)^{l} (\bar {c} \mid\bar{d})$ implies k=l+1.

• (ii) $w \in(c \mid d) (\bar{d} b^{\ast})^{k} \bar{c} d H \bar{d} b^{l} (\bar{c} \mid\bar{d} \mid \mathtt {\$})$ implies k+1=l.

Proof

We only prove part (i), since part (ii) is exactly symmetric. Suppose that $w \in \operatorname {fac}(\mathtt {\$}H \mathtt {\$})$ and for some u∈H,

$$\begin{aligned} w \in&(\mathtt {\$}\mid c \mid d) w', \\ w' \in& a^k cu\bar{c}d\bigl(a^{\ast} c \bigr)^l(\bar{c} \mid\bar{d}). \end{aligned}$$

By Lemma 17, part (i), there is a string z∈H such that w′ is a prefix of some string in $z(\varepsilon\mid(\bar{c} \mid \bar{d})\hat{\varSigma}^{\ast})$. Since w′ starts in a or c, the string z cannot be ε. Hence there are some strings x ₁,x ₂,x ₃,y ₁,y ₂,y ₃ such that ⊢J(x ₁,x ₂,x ₃), ⊢J(y ₁,y ₂,y ₃), and $z = y_{1} c x_{2} \bar{c} d y_{2} \bar{d} x_{3}$. So

$$\mbox{$w'$ is a prefix of some string in $y_{1} c x_{2} \bar{c} d y_{2} \bar{d} x_{3}(\varepsilon\mid(\bar{c} \mid\bar{d})\hat{\varSigma}^{\ast})$.} $$

Note that x ₁,y ₁∈a ⁺ and x ₃,y ₃∈b ⁺. So clearly, y ₁=a ^k, and either $x_{2} \bar{c}$ is a prefix of $u \bar{c}$, or else $u \bar{c}$ is a prefix of $x_{2} \bar{c}$. Since u∈H and x ₂∈H, neither u nor x ₂ can start in $\bar{c}$. It follows that u=ε if and only if x ₂=ε. If u≠ε and x ₂≠ε, then either u is a non-empty prefix of x ₂ or vice versa, and Lemma 15 implies that u=x ₂. Hence we always have $a^{k} c u \bar{c} d = y_{1} c x_{2} \bar{c} d$. It follows that $y_{2} \bar{d}$ has a prefix belonging to $(a^{\ast} c)^{l} (\bar{c} \mid\bar{d})$. Since y ₂∈H, by Lemma 16, part (i), either l=0 and y ₂=ε or l≥1 and y ₂ has a prefix belonging to $(a^{\ast} c)^{l} \bar{c}$. We can now apply Lemma 16, part (ii), to J(y ₁,y ₂,y ₃) and obtain k=l+1. □

3.3 Almost Anti-iterative Elements of H

Given a language K and a string w∈K, an iteration tuple for w in K is a tuple of strings (u ₀,w ₁,u ₁,…,w _k ,u _k ) such that

• w=u ₀ w ₁ u ₁⋯w _k u _k ,

• w ₁⋯w _k ≠ε, and

• $u_{0} w_{1}^{i} u_{1} \cdots w_{k}^{i} u_{k} \in K$ for all i≥0.

The notion of an iteration tuple is a generalization of the notion of an iterative pair [1]. A language K is said to be k-iterative if all but finitely many strings in K have an iteration tuple (u ₀,w ₁,u ₁,…,w _k ,u _k ) (of length 2k+1) in K. We simply say that K is iterative if all but finitely many strings in K have an iteration tuple (of any length) in K. (Iterativity is a slight weakening of the property Groenink [4, 5] called finite pumpability.)

We prove a theorem that implies that the language H is not iterative. In fact, the theorem states something much stronger. We say that a string v∈K is anti-iterative in K if v=u ₀ w ₁ u ₁⋯w _k u _k and w ₁⋯w _k ≠ε (for any k≥1) imply $u_{0} w_{1}^{i} u_{1} \cdots w_{k}^{i} u_{k} \notin K$ for all i>1. We say that v∈K is almost anti-iterative in K if v=u ₀ w ₁ u ₁⋯w _k u _k and w ₁⋯w _k ≠ε (for any k≥1) imply that there is at most one natural number i>1 such that $u_{0} w_{1}^{i} u_{1} \cdots w_{k}^{i} u_{k} \in K$. Clearly, if v is almost anti-iterative in K, then there is no iteration tuple for v in K.

Now for each n≥0, define a string v _n ∈H as follows:

$$\begin{aligned} v_0 = &\varepsilon, \\ v_{n+1} = &a^{n+1} c v_n \bar{c} d v_n \bar{d} b^{n+1}. \end{aligned}$$

It is easy to see ⊢J(a ⁿ⁺¹,v _n ,b ⁿ⁺¹) for all $n \in \mathbb {N}$. The strings v _n are precisely those elements of H that have a derivation tree whose immediate subtree is a perfect binary tree. We will show that each v _n is almost anti-iterative in H.

We start with some lemmas (Lemmas 19–22) stating some general properties of the strings v _n that are intuitively obvious from the way they are defined. We give a fairly rigorous proof to each of these lemmas.

Lemma 19

$v_{n} \in(a^{+}c)^{n} (\bar{c}\hat{\varSigma}^{\ast} d \mid\varepsilon )(\bar{d} b^{+})^{n}$ for all n.

Proof

For n=0, $v_{0} = \varepsilon= (a^{+}c)^{0}\varepsilon(\bar{d}b^{+})^{0}$, so the desired condition holds. For n≥1, we prove by induction on n that $v_{n} \in(a^{+}c)^{n} \bar{c}\hat{\varSigma}^{\ast} d (\bar {d} b^{+})^{n}$. For n=1, $v_{1} = ac\bar{c}d\bar{d}b \in(a^{+}c)^{1} \bar {c} \hat{\varSigma}^{\ast} d (\bar{d} b^{+})^{1}$. For n≥2, assume $v_{n-1} \in(a^{+}c)^{n-1} \bar{c} \hat{\varSigma}^{\ast} d (\bar{d} b^{+})^{n-1}$. Then $v_{n} = a^{n} c v_{n-1} \bar{c} d v_{n-1} \bar{d} b^{n} \in(a^{+}c)^{n} \bar{c}\hat{\varSigma}^{\ast} d (\bar{d}b^{+})^{n}$. □

Lemma 20

$\operatorname {fac}(\{ v_{n} \mid n \in \mathbb {N}\}) \cap H = \{ v_{n} \mid n \in \mathbb {N}\}$.

Proof

Clearly, it suffices to show the inclusion, $\operatorname {fac}(\{ v_{n} \mid n \in \mathbb {N}\}) \cap H \subseteq\{ v_{n} \mid n \in \mathbb {N}\}$. We prove by induction on $n \in \mathbb {N}$ that $w \in \operatorname {fac}(v_{n}) \cap H$ implies w=v _k for some k≤n. Since v ₀=ε∈H, the induction basis is immediate. Now assume w∈H and w is a factor of $v_{n+1} = a^{n+1} c v_{n} \bar{c} d v_{n} \bar{d} b^{n+1}$. By Lemma 16, part (i), either w=ε or $w \in (a^{+}c)^{+}\bar{c}\hat{\varSigma}^{\ast} d(\bar{d}b^{+})^{+}$. If w=ε, then w=v ₀. It remains to consider the case where $w \in(a^{+}c)^{+} \bar{c} \hat{\varSigma}^{\ast} d(\bar{d} b^{+})^{+}$. If ψ(w)=ψ(v _n+1), then w=v _n+1 by Lemma 13. If ψ(w)≠ψ(v _n+1), then either w is a factor of $v_{n} \bar{c}d v_{n} \bar{d} b^{n+1}$ or w is a factor of $a^{n+1} c v_{n} \bar{c} d v_{n}$.

Case 1.  w is a factor of $v_{n} \bar{c}d v_{n} \bar{d} b^{n+1}$. Since w starts in a, there must be a non-empty suffix y of v _n starting in a such that w is a prefix of $y\bar {c}dv_{n}\bar{d}b^{n+1}$ or of $y\bar{d}b^{n+1}$. Since y is a suffix of v _n ∈H, Lemma 15 implies that y cannot be a proper prefix of any element of H. Since w∈H, it follows that y is not a proper prefix of w. Since w is a prefix of $y\bar {c}dv_{n}\bar{d}b^{n+1}$ or of $y\bar{d}b^{n+1}$, w must be a prefix of y.

Case 2.  w is a factor of $a^{n+1} c v_{n} \bar{c} d v_{n}$. Since w ends in b, there must be a non-empty prefix x of v _n ending in b such that w is a suffix of a ⁿ⁺¹ cx or of $a^{n+1} c v_{n} \bar{c} d x$. By an analogous reasoning to the previous case, we can conclude that w is a suffix of x.

In both cases, w is a factor of v _n , and the induction hypothesis gives w=v _k for some k≤n. □

Lemma 21

Suppose $w \in \operatorname {fac}(\mathtt {\$}\{ v_{n} \mid n \in \mathbb {N}\} \mathtt {\$})$. For all k,l≥0, the following conditions hold:

• (i) $w \in(\mathtt {\$}\mid c \mid d) a^{k} (c \mid cH\bar{c} d) a^{l} (c \mid \bar{c} \mid\bar{d})$ implies k=l+1.

• (ii) $w \in(c \mid d \mid\bar{d}) b^{k} (\bar{c} dH\bar{d} \mid\bar{d}) b^{l} (\bar{c} \mid\bar{d} \mid \mathtt {\$})$ implies k+1=l.

• (iii) $w \in(c \mid\bar{d}) b^{k} \bar{c} d a^{l} (c \mid\bar{d})$ implies k=l.

Proof

(i). Suppose $uwv = \mathtt {\$}v_{n} \mathtt {\$}$ and

$$\begin{aligned} w \in & (\mathtt {\$}\mid c \mid d) w', \\ \\ w' \in & a^k(c \mid cH\bar{c}d)a^l(c \mid \bar{c} \mid\bar{d}). \end{aligned}$$

(10)

By Lemma 17, part (i), k≥1 and there is a z∈H such that $w'v \in z(\varepsilon\mid(\bar{c} \mid\bar {d})\hat{\varSigma}^{\ast})\mathtt {\$}$. Since w′ starts in a, z≠ε. Lemma 20 implies that $z = v_{k} = a^{k} c v_{k-1} \bar{c} d v_{k-1} \bar{d} b^{k}$. So

$$ w'v \in a^k c v_{k-1} \bar{c} d v_{k-1} \bar{d} b^k\bigl(\varepsilon\mid (\bar{c} \mid \bar{d}) \hat{\varSigma}^{\ast}\bigr) \mathtt {\$}. $$

(11)

By (11), either $w' \in a^{k} c a^{l}(c \mid\bar{c} \mid\bar {d})$ or $w' \in a^{k} cH\bar{c}d a^{l} (c \mid\bar{c} \mid\bar{d})$.

Case 1.  $w' \in a^{k}ca^{l}(c \mid\bar{c} \mid\bar{d})$. Then either k=1, v _k−1=ε, l=0, and $w' = a^{k} c \bar{c}$, or k≥2 and v _k−1 has a prefix that belongs to $a^{l} (c \mid\bar {c} \mid{d})$, which implies l=k−1. In either case, we get k=l+1.

Case 2.  $w' \in a^{k} c x \bar{c} d a^{l} (c \mid\bar{c} \mid\bar{d})$ for some x∈H. Then either $v_{k-1} \bar{c}$ is a prefix of $x \bar {c}$ or $x \bar{c}$ is a prefix of $v_{k-1} \bar{c}$. Since neither v _k−1 nor x can start in $\bar{c}$, it follows that v _k−1=ε if and only if x=ε. If v _k−1≠ε and x≠ε, then either v _k−1 is a non-empty prefix of x or x is a non-empty prefix of v _k−1. Lemma 15 then implies v _k−1=x. So we always have $a^{k} c v_{k-1} \bar{c} d = a^{k} c x \bar{c} d$. By (11), it follows that $v_{k-1} \bar{d}$ has a prefix that belongs to $a^{l} (c \mid\bar{c} \mid\bar{d})$. But the definition of v _n implies that $v_{k-1} \bar{d}$ always has a prefix in $a^{k-1} (c \mid\bar{d})$. Therefore, l=k−1 and so k=l+1.

(ii). Exactly symmetric to part (i).

(iii). Suppose $uwv = \mathtt {\$}v_{n} \mathtt {\$}$ and

$$\begin{aligned} w =& w' \bar{c}d w'', \\ w' \in&(c \mid\bar{d}) b^k,\qquad w'' \in a^l (c \mid\bar{d}). \end{aligned}$$

By Lemma 17, part (iii), there exist x,y∈H and k′,l′≥1 such that

$$uw' \in \mathtt {\$}\bigl(\varepsilon\mid\hat{\varSigma}^{\ast} (c \mid d)\bigr) a^{k'} c x,\qquad w''v \in y \bar{d} b^{l'}\bigl(\varepsilon\mid(\bar{c} \mid\bar {d})\hat{ \varSigma}^{\ast}\bigr)\mathtt {\$}. $$

Since x and y are factors of v _n , Lemma 20 implies that x=v _i and y=v _j for some i,j≥0. If i≥1, then v _i has $\bar{d} b^{i}$ as a suffix, so it follows that k=i. If i=0, then uw′ ends in c, so w′=c and k=0. So we always have k=i. By a symmetric reasoning, we get l=j. It follows that

$$uwv = uw'\bar{c}dw'' v \in \mathtt {\$}\bigl(\varepsilon\mid\hat{\varSigma }^{\ast}(c \mid d)\bigr) a^{k'} c v_k \bar{c} d v_l \bar{d} b^{l'} \bigl(\varepsilon\mid(\bar{c} \mid\bar{d})\hat{ \varSigma}^{\ast }\bigr)\mathtt {\$}. $$

Since $v_{k} \bar{c}$ has a prefix that belongs to $a^{k} (c \mid\bar {c})$ and $v_{l} \bar{d}$ has a prefix that belongs to $a^{l} (c \mid\bar {d})$, part (i) of this lemma implies k′=k+1=l+1. Therefore, k=l. □

We will make frequent use of Lemmas 18 and 21 in what follows. It will be important not to confuse part (i) and (ii) of Lemma 18, on the one hand, and part (i) and (ii) of Lemma 21, on the other. The former state general properties of elements of H, while the latter express special properties of the strings v _n .

Lemma 22

Suppose $w \in \operatorname {fac}(\{ v_{n} \mid n \in \mathbb {N}\})$.

• (i) If ψ(w)∈L, then $w = a^{i} c v_{k} \bar{c}$ for some i,k≥0 such that i≤k+1.

• (ii) If ψ(w)∈R, then $w = d v_{k} \bar{d} b^{j}$ for some j,k≥0 such that j≤k+1.

• (iii) If ψ(w)∈LR, then $w = a^{i} c v_{k} \bar{c} d v_{k} \bar{d} b^{j}$ for some i,j,k≥0 such that i, j≤k+1.

Proof

(i). Suppose uwv=v _n and $\psi(w) \in L = c V \bar{c}$. By Lemma 14, in the string w, b cannot precede a or c and neither a nor b can follow $\bar{c}$. Hence $w = a^{i} c x \bar{c}$ for some $i \in \mathbb {N}$ and some x such that ψ(x)∈V.

Since $uwv = ua^{i}cx\bar{c}v = v_{n} \in H$, Lemma 17, part (i), implies that there must be some l≥1 and y∈H such that l≥i, a ^l is a suffix of ua ⁱ and $a^{l} c x \bar{c} v \in y(\varepsilon\mid(\bar{c} \mid\bar{d})\hat {\varSigma}^{\ast})$. This means that y must contain a ^l c as a prefix, so Lemma 20 implies $y = v_{l} = a^{l} c v_{l-1} \bar{c} d v_{l-1} \bar{d} b^{l}$. Hence

$$a^l c x\bar{c}v \in a^l c v_{l-1} \bar{c}dv_{l-1}\bar {d}b^l\bigl(\varepsilon\mid(\bar{c} \mid \bar{d})\hat{\varSigma}^{\ast}\bigr). $$

This implies the following:

$$ \text{Either $x \bar{c}$ is a prefix of $v_{l-1} \bar{c}$, or else $v_{l-1} \bar{c}$ is a prefix of $x \bar{c}$.} $$

(12)

We claim x=v _l−1. The desired conclusion follows from this by putting k=l−1.

Case 1.  l=1. Then v _l−1=v ₀=ε. Since ψ(x)∈V implies that x cannot start in $\bar{c}$, it is clear from (12) that x must be ε. So the claim holds in this case.

Case 2.  l≥2. It follows from (12) that either $\psi(x) \bar{c}$ is a prefix of $\psi(v_{l-1}) \bar{c}$ or vice versa. Since l−1≥1, ψ(v _l−1) starts in c. Then ψ(x) must also start in c. Hence either ψ(x) is a non-empty prefix of ψ(v _l−1) or ψ(v _l−1) is a non-empty prefix of ψ(x). By Lemma 10, we get ψ(v _l−1)=ψ(x). Consequently, $x \bar{c}$ is not a prefix of v _l−1, and $v_{l-1} \bar{c}$ is not a prefix of x, so by (12), we can conclude v _l−1=x.

(ii). This is proved in an exactly symmetric way to (i).

(iii). By Part (i) and (ii) of this lemma, $w = a^{i} c v_{k} \bar{c} d v_{l} \bar{d} b^{j}$ for some i,j,k≥0 such that i≤k+1 and j≤l+1. Since w contains a factor that belongs to $(c \mid\bar {d}) b^{k} \bar{c} d a^{l} (c \mid\bar{d})$, part (iii) of Lemma 21 gives k=l. □

We now state and prove our main lemma. Let

$$\begin{aligned} \widehat{L} = &\{ cv_n\bar{c} \mid n \in \mathbb {N}\}, \\ \widehat{R} = &\{ dv_n\bar{d} \mid n \in \mathbb {N}\}, \\ \widehat{LR} = &\{ c v_n \bar{c} d v_n \bar{d} \mid n \in \mathbb {N}\}. \end{aligned}$$

Then Lemma 22 implies

$$\begin{aligned} \psi^{-1}(L) \cap \operatorname {fac}\bigl(\{ v_n \mid n \in \mathbb {N}\}\bigr) \subseteq& a^{\ast} \widehat{L}, \end{aligned}$$

(13)

$$\begin{aligned} \psi^{-1}(R) \cap \operatorname {fac}\bigl(\{ v_n \mid n \in \mathbb {N}\}\bigr) \subseteq& \widehat{R} b^{\ast}, \end{aligned}$$

(14)

$$\begin{aligned} \psi^{-1}(LR) \cap \operatorname {fac}\bigl(\{ v_n \mid n \in \mathbb {N}\}\bigr) \subseteq& a^{\ast} \widehat{LR} b^{\ast}. \end{aligned}$$

(15)

Lemma 23

If $w \in \operatorname {fac}(\{ v_{n} \mid n \in \mathbb {N}\})$ and $ww \in \operatorname {fac}(H)$, then

$$\psi(w) \in c^{\ast} \mid Ldc^{\ast} \mid\bar{d}^{\ast} \mid\bar {d}^{\ast} \bar{c} R \mid V \bar{c} d c^+ \mid\bar{d}^+ \bar{c} d V. $$

Proof

Since ε clearly belongs to the required set, assume ψ(w)∈Σ ⁺. Since $ww \in \operatorname {fac}(H)$ implies $\psi(w)\psi(w) \in \operatorname {fac}(V)$, ψ(w) must satisfy one of the five cases of Lemma 12:

• 1. $\psi(w) \in(\bar{c}R \mid\bar{d})^{+}$.

• 2. $\psi(w) \in R (\bar{c}R \mid\bar{d})^{\ast} \bar{c}$.

• 3. ψ(w)∈(c∣Ld)⁺.

• 4. ψ(w)∈d(c∣Ld)^∗ L.

• 5. $\psi(w) \in(V \mid R)(\bar{c}R \mid\bar{d})^{m} \bar {c}d (c \mid Ld)^{n} (V \mid L)$ for some m,n≥0 such that m≠n.

Below we treat the five cases in turn.

Case 1.  $\psi(w) \in(\bar{c}R \mid\bar{d})^{+}$. We show that $\psi(w) \in\bar{d}^{+} \mid\bar{d}^{\ast}\bar{c}R$. Suppose by way of contradiction that $\psi(w) \in\bar{d}^{\ast} \bar{c}R(\bar{c}R \mid\bar{d})^{+}$. Lemma 14 says that in the string w, a cannot precede $\bar{d}$ or $\bar{c}$, b can follow only $\bar{d}$, and $\bar{d}$ can be followed only by b. Together with (14), this allows us to infer

$$w \in b^{\ast} \bigl(\bar{d} b^+\bigr)^{\ast} \bar{c} \widehat{R} b^+ \bigl((\bar {c} \widehat{R} \mid\bar{d})b^+\bigr)^{\ast} ( \bar{c} \widehat{R} \mid \bar{d}) b^{\ast}. $$

Recall that $\widehat{R}$ consists of the strings $d v_{i} \bar{d}$. Recall also that v _i =ε when i=0 and $v_{i} = a^{i} c v_{i-1} \bar{c} d v_{i-1} \bar{d} b^{i}$ otherwise. So if w contains a factor that belongs to

$$d v_i \bar{d} b^j (\bar{c} \mid\bar{d}), $$

then w contains a factor that belongs to

$$(d \mid\bar{d}) b^i \bar{d} b^j (\bar{c} \mid\bar{d}), $$

and part (ii) of Lemma 21 allows us to infer j=i+1. Hence w must be of the form⁸

$$w = u x_1 \cdots x_m \bar{c} d v_k \bar{d} b^{k+1} y_1 \cdots y_n z, $$

where m,n≥0 and

$$\begin{aligned} u \in & b^{\ast}, \\ x_i = & \bar{d} b^{p_i} \quad \text{for some $p_{i} \geq1$,} \\ y_i \in &(\bar{c} d v_{q_i} \bar{d} \mid\bar{d}) b^{q_i+1} \quad \text{for some $q_{i} \geq0$,} \\ z \in &(\bar{c}d v_l \bar{d} \mid\bar{d})b^{\ast} \quad \text{for some $l \geq0$.} \end{aligned}$$

Lemma 21, part (ii), also implies

$$\begin{aligned} q_{i+1} = & q_i + 1 \quad \text{for $i = 1,\dots,n-1$,} \\ q_1 = & k+1 \quad\text{if $n \geq1$.} \end{aligned}$$

So

$$q_i = k+i \quad \text{for $i=1,\dots,n$.} $$

It immediately follows that

$$ \text{$\bar{d} b^{k+1} y_{1} \cdots y_{n}$ contains $\bar{d} b^{k+n+1}$ as a suffix.} $$

(16)

Note that this holds even when n=0.

Next, we claim that

$$ \text{$d v_{k} \bar{d} b^{k+1} y_{1} \cdots y_{n}$ has a suffix that belongs to $d\bigl(\bar{d} b^{\ast}\bigr)^{k+n+1}$.} $$

(17)

By Lemma 19, this is clearly true when n=0. When n≥1, we can prove by induction on i∈{1,…,n} that $d v_{k} \bar{d} b^{k+1} y_{1} \cdots y_{i}$ always has a suffix in $d(\bar{d} b^{\ast})^{k+i+1}$. For i=0, $d v_{k} \bar{d} b^{k+1}$ has a suffix in $d(\bar{d} b^{\ast})^{k+1}$ by Lemma 19. For 1≤i≤n, assume that $d v_{k} \bar{d} b^{k+1} y_{1} \cdots y_{i-1}$ has a suffix in $d(\bar{d} b^{\ast})^{k+i}$. If $y_{i} = \bar{d} b^{q_{i}+1} = \bar{d} b^{k+i}$, then it follows that $d v_{k} \bar{d} b^{k+1} y_{1} \cdots y_{i}$ has a suffix in $d(\bar{d} b^{\ast})^{k+i+1}$. If $y_{i} = \bar{c} d v_{q_{i}} \bar{d} b^{q_{i}+1} = \bar{c} d v_{k+i} \bar{d} b^{k+i+1}$, then y _i has a suffix in $d(\bar{d} b^{\ast})^{k+i+1}$ by Lemma 19.

Now note that

$$ \text{$ww$ has a factor in $\bar{c} d v_{k} \bar{d} b^{k+1} y_{1} \cdots y_{n} z u x_{1} \cdots x_{m} \bar{c} d v_{k} \bar{d} b^{k+1} (\bar{c} \mid \bar{d})$.} $$

(18)

Since $ww \in \operatorname {fac}(H)$, this factor must also belong to $\operatorname {fac}(H)$. We distinguish two cases.

Case 1.1.  $z \in\bar{c} d v_{l} \bar{d} b^{\ast}$. Then by Lemma 19, zux ₁⋯x _m has a suffix in $d (\bar{d} b^{\ast})^{l+1+m}$, so by Lemma 18, part (ii), we get l+1+m+1=k+1, i.e.,

$$ k = l+m+1. $$

(19)

By (16), w contains as a factor

$$\bar{d}b^{k+n+1}z \in\bar{d}b^{k+n+1} \bar{c}d v_l \bar{d} b^{\ast}. $$

Since this factor belongs to $\operatorname {fac}(\{ v_{n} \mid n \in \mathbb {N}\})$, we must have

$$l = k+n+1 $$

by Lemma 21, part (iii). But this last equation contradicts (19).

Case 1.2.  $z \in\bar{d} b^{\ast}$. By (17), we see that $d v_{k} \bar{d} b^{k+1} y_{1} \cdots y_{n} z u x_{1} \cdots x_{m}$ has a suffix in $d(\bar{d} b^{\ast})^{k+n+1+1+m} = d(\bar{d} b^{\ast})^{k+n+m+2}$. By Lemma 18, part (ii), we obtain from (18) that k+n+m+2+1=k+1, a contradiction.

We have derived a contradiction in each case. So the assumption that $\psi(w) \in\bar{d}^{\ast} \bar{c} R(\bar{c}R \mid\bar{d})^{+}$ is incorrect and ψ(w) must be in $\bar{d}^{+} \mid\bar{d}^{\ast } \bar{c} R$.

Case 2.  $\psi(w) \in R (\bar{c}R \mid\bar{d})^{\ast} \bar{c}$. We derive a contradiction. By Lemma 14, in the string w, $\bar{c}$ can be followed only by d and $\bar{d}$ can be followed only by b. Together with (14), this allows us to infer

$$w \in\widehat{R} b^+\bigl((\bar{c} \widehat{R} \mid\bar{d}) b^+ \bigr)^{\ast } \bar{c}. $$

By Lemma 21, part (ii), w must be of the form

$$w = d v_k \bar{d} b^{k+1} y_1 \cdots y_n \bar{c}, $$

where n≥0 and

$$y_i \in(\bar{c} d v_{q_i} \bar{d} \mid\bar{d}) b^{q_i+1} \quad\text{for some $q_{i} \geq0$.} $$

Lemma 21, part (ii), also implies

$$\begin{aligned} q_{i+1} = & q_i + 1 \quad \text{for $i = 1,\dots,n-1$,} \\ q_1 = & k+1 \quad \text{if $n \geq1$.} \end{aligned}$$

So we have

$$q_i = k+i \quad \text{for $i=1,\dots,n$.} $$

As in Case 1, we can see that $v_{k} \bar{d} b^{k+1} y_{1} \cdots y_{n}$ has a suffix that belongs to $d(\bar{d}b^{\ast})^{k+n+1}$. Since ww has a factor in

$$v_k \bar{d} b^{k+1} y_1 \cdots y_n \bar{c} d v_k \bar{d} b^{k+1} (\bar{c} \mid\bar{d}) $$

and this factor belongs to $\operatorname {fac}(H)$, Lemma 18, part (ii), implies k+n+1+1=k+1, a contradiction.

Case 3.  ψ(w)∈(c∣Ld)⁺. This case is exactly symmetric to Case 1 and we can derive ψ(w)∈c ⁺∣Ldc ^∗.

Case 4.  ψ(w)∈d(c∣Ld)^∗ L. This case is exactly symmetric to Case 2 and we can derive a contradiction.

Case 5.  $\psi(w) \in(V \mid R)(\bar{c} R \mid\bar {d})^{m} \bar{c} d(c \mid Ld)^{n}(V \mid L)$ for some m,n≥0 such that m≠n. We show that $\psi(w) \in\bar{d}^{+} \bar{c} d V \mid V \bar{c} d c^{+}$. By Lemma 14, a cannot precede $\bar{c}$ or $\bar{d}$, and b cannot follow c or d. Together with (13), (14), and (15), this allows us to infer

$$w \in\bigl(b^{\ast} \mid a^{\ast} \widehat{LR} b^{\ast} \mid\widehat {R} b^{\ast}\bigr) \bigl((\bar{c} \widehat{R} \mid \bar{d})b^{\ast}\bigr)^m \bar {c}d \bigl(a^{\ast}(c \mid\widehat{L}d)\bigr)^n\bigl(a^{\ast} \mid a^{\ast} \widehat{LR} b^{\ast} \mid a^{\ast} \widehat{L}\bigr). $$

By Lemma 21, part (i) and (ii), we can write w as

$$w = x x_1 \cdots x_m \bar{c}d y_n \cdots y_1 y, $$

where

$$\begin{aligned} x \in& b^{\ast} \mid a^{\ast} c v_k \bar{c} d v_k \bar{d} b^{k+1} \mid d v_k \bar{d} b^{k+1} \quad \text{for some $k \geq0$}, \\ y \in& a^{\ast} \mid a^{l+1} c v_l \bar{c} d v_l \bar{d} b^{\ast} \mid a^{l+1} c v_l \bar{c} \quad \text{for some $l \geq0$}, \\ x_i \in &(\bar{c} d v_{p_i} \bar{d} \mid\bar{d}) b^{p_i+1} \quad \text{for some $p_{i} \geq0$}, \\ y_i \in& a^{q_i+1} (c \mid c v_{q_i} \bar{c} d) \quad\text{for some $q_{i} \geq0$}. \end{aligned}$$

Lemma 21, part (i) and (ii), also implies

$$\begin{aligned} p_{i+1} = & p_i + 1 \quad\text{for $i = 1,\dots,m-1$,} \end{aligned}$$

(20)

$$\begin{aligned} q_{i+1} = &q_i + 1 \quad\text{for $i = 1,\dots,n-1$.} \end{aligned}$$

(21)

We first show that

$$ yx = v_j \quad\text{for some $j$.} $$

(22)

Since ww contains $d y_{n} \cdots y_{1} yx x_{1} \cdots x_{m} \bar{c}$ as a factor and $ww \in \operatorname {fac}(H)$,

$$ (c \mid d)yx(\bar{c} \mid\bar{d}) \cap \operatorname {fac}(H) \neq\varnothing. $$

(23)

By Lemma 14, the only symbol that can follow $\bar{c}$ in yx is d and the only symbol that can precede d in yx is $\bar{c}$. So $x = d v_{k} \bar{d} b^{k+1}$ if and only if $y = a^{l+1} c v_{l} \bar{c}$. Lemma 14 also implies that neither a nor c can follow b or $\bar{d}$ in yx, so we cannot have both $x \in a^{\ast} c v_{k} \bar{c} d v_{k} \bar{d} b^{k+1}$ and $y \in a^{l+1} c v_{l} \bar{c} d v_{l} \bar{d} b^{\ast}$. Hence

$$yx \in a^{\ast} b^{\ast} \mid a^{\ast} c v_k \bar{c}d v_k \bar {d}b^{k+1} \mid a^{l+1} c v_l \bar{c} d v_l \bar{d} b^{\ast} \mid a^{l+1} c v_l \bar{c} d v_k \bar{d} b^{k+1}. $$

If yx∈a ^∗ b ^∗, Lemma 14 together with (23) implies yx=ε=v ₀. Otherwise, Lemmas 18 and 19 together with (23) imply

$$yx = a^{j+1} c v_j \bar{c} d v_j \bar{d} b^{j+1} = v_{j+1}, $$

where j=k or j=l. This establishes (22).

Since m≠n, either m≥1 or n≥1. We distinguish three cases:

Case 5.1.  m≥1,n≥1. In this case, ww contains a factor in

$$(c \mid d) y_1 v_j x_1 (\bar{c} \mid \bar{d}). $$

This factor is in $\operatorname {fac}(H)$. Since $\psi(ww) \in \operatorname {fac}(V) \subseteq \operatorname {fac}(D_{2}^{\ast})$, we have $\psi(y_{1} v_{j} x_{1}) \in \operatorname {fac}(D_{2}^{\ast })$. By Lemma 4, $\operatorname{nf}(\psi(y_{1} v_{j} x_{1})) \in(\bar{c} \mid\bar{d})^{\ast} (c \mid d)^{\ast}$, and it follows that

$$y_1 v_j x_1 \in a^{q_1+1} c v_j \bar{c} d v_{p_1} \bar{d} b^{p_1+1} \mid a^{q_1+1} c v_{q_1} \bar{c} d v_j \bar{d} b^{p_1+1}. $$

So

$$(c \mid d) \bigl(a^{q_1+1} c v_j \bar{c} d v_{p_1} \bar{d} b^{p_1+1} \mid a^{q_1+1} c v_{q_1} \bar{c} d v_j \bar{d} b^{p_1+1}\bigr) (\bar{c} \mid \bar{d}) \cap \operatorname {fac}(H) \neq\varnothing. $$

By Lemmas 18 and 19, we obtain p ₁=q ₁=j. By (20) and (21), then, we get p _m =j+m−1 and q _n =j+n−1. Since

$$x_m \bar{c} d y_n \in(\bar{c} d v_{j+m-1} \bar{d} \mid\bar{d}) b^{j+m} \bar{c} d a^{j+n} (c \mid c v_{j+n-1} \bar{c} d) $$

is a factor of w, we get j+m=j+n by Lemma 21, part (iii), but this contradicts m≠n.

Case 5.2.  m≥1,n=0. Since

$$ww = x x_1 \cdots x_m \bar{c} d v_j x_1 \cdots x_m \bar{c} d y $$

and $\psi(ww) \in \operatorname {fac}(V) \subseteq \operatorname {fac}(D_{2}^{\ast})$, we get $\psi (d v_{j} x_{1}) \in \operatorname {fac}(D_{2}^{\ast})$. By Lemma 4, $\operatorname{nf}(\psi(d v_{j} x_{1})) = \operatorname{nf}(d \psi (x_{1})) \in(\bar{c} \mid\bar{d})^{\ast} (c \mid d)^{\ast}$. Hence we must have

$$x_1 = \bar{d} b^{p_1+1}. $$

By (20), p _i =p ₁+i−1 for i=1,…,m. We consider three subcases, depending on whether x∈b ^∗, and whether $x_{i} = \bar{d} b^{p_{1}+i}$ for all i=1,…,m.

Case 5.2.1.  x∈b ^∗ and $x_{i} = \bar{d} b^{p_{1}+i}$ for all i=1,…,m. Then since yx=v _j , either x=y=ε or j=l+1 and $y \in a^{l+1} c v_{l} \bar{c} d v_{l} \bar {d} b^{\ast}$. Hence

$$\psi(w) \in\bar{d}^+ \bar{c} d V. $$

Case 5.2.2.  x∉b ^∗ and $x_{i} = \bar{d} b^{p_{1}+i}$ for all i=1,…,m. Then j=k+1, yx=v _k+1, and $d v_{k} \bar{d} b^{k+1}$ is a suffix of x. Since w contains a factor in

$$d v_k \bar{d} b^{k+1} x_1 (\bar{c} \mid\bar{d}) = d v_k \bar{d} b^{k+1} \bar{d} b^{p_1+1} (\bar{c} \mid\bar{d}), $$

we get p ₁=k+1 by Lemma 21, part (ii). By Lemma 19, we also see that xx ₁⋯x _m has a suffix in $d (\bar {d} b^{\ast})^{k+m+1}$. Since ww has a factor in

$$\begin{aligned} x x_1 \cdots x_m \bar{c} d v_{k+1} x_1 (\bar{c} \mid\bar{d}) = & x x_1 \cdots x_m \bar{c} d v_{k+1} \bar{d} b^{k+2} (\bar{c} \mid\bar {d}) \\ \subseteq & \hat{\varSigma}^{\ast} d \bigl(\bar{d} b^{\ast} \bigr)^{k+m+1} \bar {c} d H \bar{d} b^{k+2} (\bar{c} \mid\bar{d}), \end{aligned}$$

we get by Lemma 18, part (ii),

$$k+m+1+1 = k+2, $$

which contradicts m≥1.

Case 5.2.3.  $x_{h} = \bar{c} d v_{p_{1}+h-1} \bar{d} b^{p_{1}+h}$ for some h∈{2,…,m}. (Recall $x_{1} = \bar{d} b^{p_{1}+1}$.) We can assume h to be the largest such number, i.e., $x_{i} = \bar{d} b^{p_{1}+i}$ for all i∈{h+1,…,m}. By Lemma 19, x _h has a suffix in $d (\bar{d} b^{\ast})^{p_{1}+h}$. It follows that x _h ⋯x _m has a suffix in $d (\bar{d} b^{\ast})^{p_{1}+m}$. Since ww has a factor in

$$\begin{aligned} x_h \cdots x_m \bar{c} d v_j x_1 (\bar{c} \mid\bar{d}) = & x_h \cdots x_m \bar{c} d v_j \bar{d} b^{p_1+1} (\bar{c} \mid \bar{d}) \\ \subseteq &\hat{\varSigma}^{\ast} d \bigl(\bar{d}b^{\ast} \bigr)^{p_1+m} \bar {c} d H \bar{d} b^{p_1+1} (\bar{c} \mid\bar{d}), \end{aligned}$$

we get by Lemma 18, part (ii),

$$p_1+m+1 = p_1+1, $$

which contradicts m≥1.

Case 5.3.  m=0,n≥1. This case is exactly symmetric to the preceding case, and we can conclude

$$\psi(w) \in V \bar{c} d c^+. $$

This concludes the proof of the lemma. □

Theorem 24

For each n≥0, the string v _n is almost anti-iterative in H.

Before embarking on the proof of the theorem, let us consider a simple example:

$$v_2 = \underbrace{aac}_{w_1} \underbrace{ac\bar{c}d\bar {d}}_{u_1} \underbrace{b\bar{c}dac\bar{c}d\bar{d}b\bar {d}b}_{w_2} \underbrace{b}_{w_3}. $$

In this example, u ₀=u ₂=u ₃=ε. Note

$$\psi(w_1) = c,\qquad \psi(w_2) \in\bar{c}R,\qquad \psi(w_3) = \varepsilon. $$

We have

$$w_1^2 u_1 w_2^2 w_3^2 = aac \underbrace{aac \underbrace{ac\bar{c}d \bar{d} b}_{v_1}\bar{c}d\underbrace{ac\bar{c}d\bar{d}b}_{v_1} \bar{d}b b}_{v_2}\bar{c}d\underbrace{ac\bar{c}d\bar{d}b}_{v_1} \bar{d}b b b \in H, $$

but

$$\begin{aligned} & w_1^3 u_1 w_2^3 w_3^3 \\ &\quad=aac \underbrace{aac \underbrace{aac \underbrace{ac\bar {c}d\bar{d} b}_{v_1}\bar{c}d\underbrace{ac\bar{c}d\bar {d}b}_{v_1} \bar{d}b b}_{v_2}\bar{c}d\underbrace{ac\bar{c}d\bar {d}b}_{v_1} \bar{d}b b}_{\notin H}\bar{c}d\underbrace{ac\bar {c}d\bar{d}b}_{v_1} \bar{d}b b b b \notin H \end{aligned}$$

After the occurrence of $\bar{d}$ following the third occurrence of v ₁, one should find b ³, rather than b ², in order to have a string in H (as required by Lemma 18, part (ii)).

Proof of Theorem 24

Suppose that v _n =u ₀ w ₁ u ₁⋯w _k u _k and w ₁⋯w _k ≠ε. If there is some j such that $w_{j}^{3}$ is not in $\operatorname {fac}(H)$, then there is no i≥3 such that $u_{0} w_{1}^{i} u_{1} \cdots w_{k}^{i} u_{k} \in H$, and the conclusion of the theorem is clearly satisfied. Hence we may assume that each $w_{j}^{3}$ belongs to $\operatorname {fac}(H)$.

Suppose that $u_{0} w_{1}^{h} \cdots w_{k}^{h} u_{k} \in H$ for some h>1. We show that such h is unique.

Since $w_{j}^{2}$ is a factor of $w_{j}^{3}$ and hence belongs to $\operatorname {fac}(H)$, by Lemma 23, each ψ(w _j ) must belong to one of the six sets

$$c^{\ast},\qquad Ld c^{\ast},\qquad \bar{d}^{\ast},\qquad \bar{d}^{\ast} \bar{c} R,\qquad V \bar{c} d c^+,\qquad \bar{d}^+ \bar{c} d V. $$

Since w ₁⋯w _k ≠ε, we have $u_{0} w_{1} u_{1} \cdots w_{k} u_{k} \neq u_{0} w_{1}^{h} u_{1} \cdots w_{k}^{h} u_{k}$. By Lemma 13, we know that $\psi(u_{0} w_{1} u_{1} \cdots w_{k} u_{k}) \neq\psi(u_{0} w_{1}^{h} u_{1} \cdots w_{k}^{h} u_{k})$. Therefore, it cannot be that ψ(w _j )=ε for all j. Since both ψ(u ₀ w ₁ u ₁⋯w _k u _k ) and $\psi(u_{0} w_{1}^{h} u_{1} \cdots w_{k}^{h} u_{k})$ belong to V, the string ψ(w ₁)⋯ψ(w _k ) must have the same number of occurrences of $c,\bar{c},d,\bar{d}$. It follows that there is a j such that $\psi(w_{j}) \in Ld c^{\ast} \mid\bar{d}^{\ast} \bar{c} R \mid V \bar{c} d c^{+} \mid\bar{d}^{+} \bar{c} d V$.

Case 1.  ψ(w _j )∈Ldc ^∗. Lemma 14 implies that in the string w _j , b can follow only $\bar {d}$. So

$$w_j \in v d \bigl(a^{\ast} c \bigr)^{\ast} a^{\ast} $$

for some $v \in \operatorname {fac}(\{ v_{n} \mid n \in \mathbb {N}\})$ such that ψ(v)∈L. By Lemma 22, $v \in a^{\ast} c v_{l} \bar{c}$ for some l≥0. Lemma 14 also implies that in u ₀ w ₁ u ₁⋯w _k u _k , (i) the only symbols that can precede a are a, c, and d, (ii) the only symbols that can follow a are a and c, and (iii) the only symbols that can follow c or d are a, $\bar{c}$, and $\bar{d}$. Hence we can write

$$\begin{aligned} u_0 w_1 u_1 \cdots w_{j-1} u_{j-1} \in &\bigl(\varepsilon\mid\hat{\varSigma }^{\ast} (c \mid d)\bigr) a^{m_0}, \\ w_j \in &a^{m_1} c v_l \bar{c} d \bigl(a^{\ast} c\bigr)^p a^{m_2}, \\ u_j w_{j+1} u_{j+1} \cdots w_k u_k \in &\bigl(a^{\ast} c\bigr)^q (\bar{c} \mid \bar{d}) \hat{\varSigma}^{\ast}, \end{aligned}$$

for some l,m ₀,m ₁,m ₂,p,q≥0. We get m ₀+m ₁=l+1 by Lemma 21, part (i), and m ₀+m ₁=p+q+1 by Lemma 18, part (i). Hence l=p+q.

Let g≥j the largest number such that u _j w _j+1⋯u _g−1 w _g ∈(a ^∗ c)^∗ a ^∗. Let r be the number of occurrences of c in w _j+1⋯w _g . Then for every i≥1,

$$u_j w_{j+1}^i u_{j+1} \cdots w_k^i u_k \in\bigl(a^{\ast} c \bigr)^{q+(i-1)r} (\bar{c} \mid\bar{d}) \hat{\varSigma}^{\ast}. $$

Thus, $w_{j}^{h} u_{j} w_{j+1}^{h} u_{j+1} \cdots w_{k}^{h} u_{k}$ has a factor in

$$d\bigl(a^{\ast} c\bigr)^p a^{m_2+m_1} c v_l \bar{c} d\bigl(a^{\ast} c\bigr)^p a^{m_2} \bigl(a^{\ast} c\bigr)^{q+(h-1)r} (\bar{c} \mid \bar{d}). $$

Since this factor is in $\operatorname {fac}(H)$, Lemma 18, part (i), implies

$$\begin{aligned} m_2+m_1 = & p + q+(h-1)r+1 \\ = &(h-1)r+l+1. \end{aligned}$$

(24)

Note that the string $w_{j}^{3}$ has a factor in

$$d\bigl(a^{\ast} c\bigr)^p a^{m_2+m_1} c v_l \bar{c} d \bigl(a^{\ast} c\bigr)^p a^{m_2+m_1} c v_l \bar{c}. $$

Since we assumed that $w_{j}^{3} \in \operatorname {fac}(H)$, this factor is also in $\operatorname {fac}(H)$. By Lemma 19, $v_{l} \bar{c}$ has a prefix that belongs to $(a^{\ast} c)^{l} \bar{c}$. By Lemma 18, part (i), then, we have

$$\begin{aligned} m_2+m_1 = & p+1+l+1 \\ = &p+l+2. \end{aligned}$$

(25)

From (24) and (25), we get

$$(h-1) r = p + 1. $$

Since p≥0, this implies r≠0 and

$$h = \frac{p+1}{r}+1, $$

which shows that h is unique.

Case 2.  $\psi(w_{j}) \in\bar{d}^{\ast} \bar{c} R$. This case is exactly symmetric to the preceding case.

Case 3.  $\psi(w_{j}) \in V \bar{c} d c^{+}$. We can use Lemma 14 to infer

$$\begin{aligned} w_j \in &v \bar{c} d \bigl(a^{\ast} c\bigr)^+ a^{\ast}, \\ u_j w_{j+1} u_{j+1} \cdots w_k u_k \in &\bigl(a^{\ast} c\bigr)^{\ast} \bar{c} \hat{ \varSigma}^{\ast} \end{aligned}$$

for some string $v \in \operatorname {fac}(\{ v_{n} \mid n \in \mathbb {N}\})$ such that ψ(v)∈V. By Lemma 21, part (i), we can write

$$\begin{aligned} w_j \in &v \bar{c} d a^{l_1+l_2} c \cdots a^{l_1+1} c a^{m_1}, \\ u_j w_{j+1} u_{j+1} \cdots w_k u_k \in &a^{m_2} c a^{l_1-1} c \cdots c a^1 c \bar{c} \hat{\varSigma}^{\ast} \\ \subseteq&\bigl(a^{\ast} c\bigr)^{l_1} \bar{c} \hat{ \varSigma}^{\ast}. \end{aligned}$$

for some l ₁,m ₁,m ₂≥0 and l ₂≥1 such that m ₁+m ₂=l ₁. Similarly to Case 1, there must be some r≥0 such that

$$u_j w_{j+1}^i u_{j+1} \cdots w_k^i u_k \in\bigl(a^{\ast} c \bigr)^{l_1+(i-1)r} \bar{c} \hat{\varSigma}^{\ast} $$

for all i≥1. Then $w_{j}^{h} u_{j} w_{j+1}^{h} u_{j+1} \cdots w_{k}^{h} u_{k}$ has a factor in

$$\begin{aligned} &(c \mid d) a^{l_1+1} c a^{m_1} v \bar{c} d a^{l_1+l_2} c \cdots a^{l_1+1} c a^{m_1} \bigl(a^{\ast} c \bigr)^{l_1+(h-1)r} \bar{c} \hat {\varSigma}^{\ast} \\ &\quad \subseteq(c \mid d) a^{l_1+1} c a^{m_1} v \bar{c} d \bigl(a^{\ast} c\bigr)^{l_2+l_1+(h-1)r} \bar{c} \hat{\varSigma}^{\ast}. \end{aligned}$$

(26)

This factor is in $\operatorname {fac}(H)$. Note that the above inclusion holds even when l ₁=r=0, since l ₁=0 implies m ₁=0.

We show that $a^{m_{1}} v \in H$. Recall ψ(v)∈V and $v \in \operatorname {fac}(\{ v_{n} \mid n \in \mathbb {N}\})$. If ψ(v)=ε, then v∈(a∣b)^∗, but since $c a^{m_{1}} v \bar{c} \in \operatorname {fac}(H)$, Lemma 14 implies $a^{m_{1}} v = \varepsilon\in H$. If ψ(v)∈LR, Lemma 22 implies that $a^{m_{1}} v \in a^{\ast} cv_{l}\bar{c}dv_{l}\bar{d}b^{\ast}$ for some l. Since $c a^{m_{1}} v \bar{c} \in \operatorname {fac}(H)$, it follows from Lemma 19 and Lemma 18, part (i) and (ii), that $a^{m_{1}} v = a^{l+1} c v_{l} \bar{c} d v_{l} \bar{d} b^{l+1} = v_{l+1} \in H$.

So the set (26) is included in

$$(c \mid d) a^{l_1+1} c H \bar{c} d \bigl(a^{\ast} c \bigr)^{l_2+l_1+(h-1)r} \bar {c} \hat{\varSigma}^{\ast}. $$

Since there is an element of $\operatorname {fac}(H)$ belonging to this set, we obtain by Lemma 18, part (i)

$$l_1+1 = l_2 + l_1 + (h-1)r + 1. $$

Since h>1, r≥0 and l ₂≥1, this is a contradiction.

Case 4.  $\psi(w_{j}) \in\bar{d}^{+} \bar{c} d V$. This case is exactly symmetric to the preceding case. □

Corollary 25

The language H is not iterative.

Corollary 26

There is a 3-MCFL that is not k-iterative for any k.

4 Conclusion

We have proved that the language H is a 3-MCFL that is not iterative. A simple consequence of this theorem is that if $\mathcal{C}$ is a subclass of the class MCFL of multiple context-free languages and $\mathcal{C}$ consists entirely of iterative sets, then the language H does not belong to $\mathcal{C}$ and hence $\mathcal{C}$ must be a proper subclass of MCFL.

Kanazawa and Salvati [8] showed that the class MCFL_wn of well-nested multiple context-free languages is properly included in MCFL, and in particular, the language $\{ w \mathtt{\#} w \mid w \in D_{2}^{\ast} \}$ belongs to MCFL−MCFL_wn. Since every language in MCFL_wn is k-iterative for some k, the language H serves as a further witness to the separation of MCFL and MCFL_wn.

Another subclass of MCFL that only contains languages that are k-iterative for some k is the class of languages in Weir’s control language hierarchy [7, 12, 16]. As far as we know, it has been an open question whether the inclusion of the control language hierarchy in the class of multiple context-free languages is proper. The language H serves as a witness to the properness of the inclusion.

Corollary 27

There is a 3-MCFL that does not belong to Weir’s control language hierarchy.