key: cord-0043260-an8xlnnd
authors: Yamakami, Tomoyuki
title: Intersection and Union Hierarchies of Deterministic Context-Free Languages and Pumping Lemmas
date: 2020-01-07
journal: Language and Automata Theory and Applications
DOI: 10.1007/978-3-030-40608-0_24
sha: c38b814ee0dad02f02855ff7abdfc672bbf5cc1c
doc_id: 43260
cord_uid: an8xlnnd

We study the computational complexity of finite intersections and unions of deterministic context-free languages. Earlier, Wotschke (1978) demonstrated that intersections of [Formula: see text] deterministic context-free languages are in general more powerful than intersections of d deterministic context-free languages for any positive integer d based on the hierarchy separation of Liu and Weiner (1973). The argument of Liu and Weiner, however, works only on bounded languages of particular forms, and therefore Wotschke’s result cannot be extended to disprove any other language to be written in the form of an intersection of d deterministic context-free languages. To deal with the non-membership of a wide range of languages, we circumvent their proof argument and instead devise a new, practical technical tool: a pumping lemma for finite unions of deterministic context-free languages. Since the family of deterministic context-free languages is closed under complementation, this pumping lemma enables us to show a non-membership relation of languages made up with finite intersections of even non-bounded languages as well. We also refer to a relationship to Hibbard’s limited automata.

e.g., [13] ). With this notation, the above language L abc belongs to CFL(2)−CFL. Similarly, the language L d = {a n1 1 a n2 2 · · · a n d d b n1 1 b n2 2 · · · b n d d | n 1 , n 2 , . . . , n d ≥ 0} over an alphabet {a 1 , a 2 , . . . , a d , b 1 , b 2 , . . . , b d } falls into CFL(d) because L d can be expressed as an intersection of d context-free languages of the form {a n1 1 a n2 2 · · · a n d d b m1 1 b m2 2 · · · b m d d | n 1 , n 2 , . . . , n d , m 1 , m 2 , . . . , m d ≥ 0, n k = m k } (1 ≤ k ≤ d). In 1973, Liu and Weiner [8] gave a contrived proof to their key statement that (*) L d is outside of CFL(d − 1) for any index d ≥ 2. Therefore, the collection {CFL(d) | d ≥ 1} truly forms an infinite hierarchy.

Deterministic context-free (dcf) languages have been a focal point in CFL since a systematic study of Ginsburg and Greibach [1] . The importance of such languages can be exemplified by the facts that dcf languages are easy to parse and that every context-free language is simply the homomorphic image of a dcf language. Unlike CFL, the family DCFL of dcf languages is closed under neither union nor intersection. We use the terms of d-intersection deterministic contextfree (dcf ) languages and d-union deterministic context-free (dcf ) languages to express intersections of d dcf languages and unions of d dcf languages, respectively. For brevity, we write DCFL(d) and DCFL [d] respectively for the family of all d-intersection dcf languages and that of all d-union dcf languages, while Wotschke [11, 12] earlier referred DCFL(d) to the d-intersection closure of DCFL. In particular, we obtain DCFL(1) = DCFL [ Wotschke [11, 12] noted that the aforementioned result (*) of Liu and Weiner leads to the conclusion that {DCFL[d] | d ≥ 1} truly forms an infinite hierarchy.

To be more precise, since the language L d belongs to DCFL(d), the statement (*) implies DCFL(d) CFL(d−1), which instantly yields DCFL(d−1) = DCFL(d). Wotschke's argument, nonetheless, heavily relies on the separation result of Liu and Weiner, who employed a notion of stratified semi-linear set to prove the statement (*). Notice that the proof technique of Liu and Weiner was developed only for a particular form of bounded languages 1 and it is therefore applicable to specific languages, such as L d . In fact, the key idea of the proof of Liu and Weiner for L d is to focus on the number of the occurrences of each base symbol in

) in order to exploit the semi-linearity of Ψ (L d ), where # σ (w) expresses the total number of symbols σ in a string w.

Because of the aforementioned limitation of Liu and Weiner's proof technique, the scope of their proof cannot be extended to other forms of languages. Simple examples of such languages include L language expanding L d but its Parikh images do not have semi-linearity. As another example, let us take a look at a "non-palindrome" language NP al # d = and NP al # d to be outside of DCFL(d)? Moreover, given a language, how can we verify that it is not in DCFL(ω)? We can ask similar questions for d-union dcf languages and the union hierarchy of dcf languages. Ginsburg and Greibach [1] remarked with no proof that the context-free language P al = {ww R | w ∈ Σ * } for any non-unary alphabet Σ is not in DCFL[ω]. It is natural to call for a formal proof of the remark of Ginsburg and Greibach. Using a quite different language L wot = {wcx | w, x ∈ {a, b} * , w = x}, however, Wotschke [11, 12] actually proved that L wot does not belong to DCFL(ω) (more strongly, the Boolean closure of DCFL) by employing the closure property of DCFL(d) under inverse gsm mappings as well as complementation and intersection with regular languages. Wotschke's proof relies on the following two facts. (i) The language L d+1 can be expressed as the inverse gsm map of the language

Dup c is expressed as the complement of L wot , restricted to a certain regular language. Together with these facts, the final conclusion comes from the aforementioned result (*) of Liu and Weiner because Dup c ∈ DCFL(d) implies L d+1 ∈ DCFL(d) by (i) and (ii). To our surprise, the fundamental results on DCFL(d) that we have discussed so far are merely "corollaries" of the main result (*) of Liu and Weiner! For further study on DCFL(d) and answering more general non-membership questions to DCFL(d), we need to divert from Liu and Weiner's contrived argument targeting the statement (*) and to develop a completely different, new, more practical technical tool. The sole purpose of this exposition is, therefore, set to (i) develop a new proof technique, which can be applicable to many other languages, (ii) present an alternative proof for the fact that the intersection and union hierarchies of DCFL are infinite hierarchies, and (iii) present other languages in CFL that do not belong to DCFL(ω) (in part, verifying Ginsburg and Greibach's remark for the first time).

In relevance to the union hierarchy of dcf languages, there is another known extension of DCFL using a different machine model called limited automata, 2 which are originally invented by Hibbard [3] and later discussed extensively in, e.g., [9, 14] . Of all such machines, a d-limited deterministic automaton (or a dlda, for short) is a deterministic Turing machine that can rewrite each tape cell in between two endmarkers only during the first d visits (except that making a turn of a tape head counts as double visits). We can raise a question of whether there is any relationship between the union hierarchy and d-lda's.

In Sect. 1.1, we have noted that fundamental properties associated with DCFL(d) heavily rely on the single separation result (*) of Liu and Weiner. However, Liu and Weiner's technical tool that leads to their main result does not seem to withstand a wide variety of direct applications. It is thus desirable to develop a new, simple, and practical technical tool that can find numerous applications for a future study on DCFL(d) and DCFL [d] . Thus, our main contribution of this exposition is to present a simple but powerful, practical technical tool, called the pumping lemma of languages in DCFL[d] with d ≥ 1, which also enriches our understanding of DCFL[d] as well as DCFL(d). Notice that there have been numerous forms of so-called pumping lemmas (or iteration theorems) for variants of context-free languages in the past literature, e.g., [2, [4] [5] [6] [7] 10, 15] . Our pumping lemma is a crucial addition to the list of such lemmas.

For a string x of length n and any number i ∈ [n], x[i] stands for the ith symbol of x and x i for the i repetitions of x.

As a special case of d = 1, we obtain Yu's pumping lemma [15, Lemma 1] from Lemma 1. Since there have been few machine-based analyses to prove various pumping lemmas in the past literature, one of the important aspects of this exposition is a clear demonstration of the first alternative proof to Yu's pumping lemma, which is solely founded on an analysis of behaviors of 1dpda's instead of derivation trees of LR(k) grammars as in [15] . The proof of Lemma 1, in fact, exploits early results of [14] on an ideal shape form (Sect. 2.3) together with a new approach of ε-enhanced machines by analyzing transitions of crossing state-stack pairs (Sect. 2.4). These notions will be explained in Sect. 2 and their basic properties will be explored therein.

Using our pumping lemma (Lemma 1), we can expand the scope of the statement (*) of Liu and Weiner [8] targeting specific bounded languages to other types of languages, including L

Since Lemma 1 concerns with DCFL[d], in our proof of Theorem 1, we first take the complements of the above languages, restricted to suitable regular languages, and we then apply Lemma 1 appropriately to them. The proof sketch of this theorem will be given in Sect. 3. From Theorem 1, we instantly obtain the following consequences of Wotschke [11, 12] . Corollary 1. [11, 12] The intersection hierarchy of dcf languages and the union hierarchy of dcf languages are both infinite hierarchies.

Concerning the limitation of DCFL(ω) and DCFL[ω] in recognition power, since all unary context-free languages are also regular languages and the family REG of regular languages is closed under intersection, all unary languages in DCFL(ω) are regular as well. It is thus easy to find languages that are not in DCFL(ω). Such languages, nevertheless, cannot serve themselves to separate CFL from DCFL(ω) ∪ DCFL[ω]. As noted in Sect. 1.1, Ginsburg and Greibach [1] remarked with no proof that the context-free language P al = {ww R | w ∈ {0, 1} * } does not belong to DCFL(ω) (as well as DCFL[ω]). As another direct application of our pumping lemma, we give a formal written proof of their remark.

As an immediate consequence of the above theorem, we obtain Wotschke's separation of DCFL(ω) from CFL. Here, we stress that, unlike the work of Wotschke [11, 12] , our proof does not depend on the main result (*) of Liu and Weiner. Corollary 2. [11, 12] CFL DCFL(ω) and DCFL[ω] CFL.

We turn our interest to limited automata. Let us write d-LDA for the family of all languages recognized by d-limited deterministic automata, in which their tape heads are allowed to rewrite tape symbols only during the first d accesses (except that, in the case of tape heads making a turn, we treat each turn as double visits). Hibbard [3] demonstrated that d-LDA = (d − 1)-LDA for any d ≥ 3. A slightly modified language of his, which separates d-LDA from (d − 1)-LDA, also belongs to the 2 d−2 -th level of the union hierarchy of dcf languages but not in the (2 d−2 − 1)-th level. We thus obtain the following separation.

The proofs of all the above assertions will be given after introducing necessary notions and notation in the subsequent section.

The set of all natural numbers (including 0) is denoted by N. An integer interval [m, n] Z for two integers m, n with m ≤ n is the set {m, m + 1, m + 2, . . . , n}. In particular, for any integer n ≥ 1, [1, n] Z is abbreviated as [n]. For any string x, |x| indicates the total number of symbols in x. The special symbol ε is used to denote the empty string of length 0. For a language L over alphabet Σ, L denotes Σ * − L, the complement of L. Given a family F of languages, co-F expresses the complement family, which consists of languages L for any L ∈ F.

A one-way deterministic pushdown automaton (or a 1dpda, for short) M is a tuple (Q, Σ, {| c, $}, Γ, δ, q 0 , Z 0 , Q acc , Q rej ), where Q is a finite set of inner states, Σ is an input alphabet withΣ = Σ ∪ {ε, | c, $}, Γ is a stack alphabet, δ is a deterministic transition function from Q ×Σ × Γ to Q × Γ * , q 0 is the initial state in Q, Z 0 is the bottom marker in Γ , and Q acc and Q rej are subsets of Q. The symbols | c and $ respectively express the left-endmarker and the right-endmarker. Let Γ (−) = Γ − {Z 0 }. We assume that, if δ(p, ε, a) is defined, then δ(p, σ, a) is undefined for all symbols σ ∈Σ − {ε}. Moreover, we require δ(q, σ, Z 0 ) = (p, ε) for any p, q ∈ Q and σ ∈Σ. Each content of a stack is expressed as a 1 a 2 · · · a k in which a 1 is the topmost stack symbol, a k is the bottom marker Z 0 , and all others are placed in order from the top to the bottom of the stack.

Given d ∈ N + , a d-intersection deterministic context-free (dcf ) language is an intersection of d deterministic context-free (dcf) languages. Let DCFL(d) denote the family of all d-intersection dcf languages. Similarly, we define d-union dcf languages and DCFL[d] by substituting "union" for "intersection" in the above definitions. Note that DCFL[d] = co-(DCFL(d)) because DCFL = co-DCFL.

For two language families F 1 and F 2 , the notation F 1 ∧ F 2 (resp., F 1 ∨ F 2 ) denotes the family of all languages L for which there are two languages L 1 ∈ F 1 and L 2 ∈ F 2 over the same alphabet satisfying L = L 1 ∩ L 2 (resp., L = L 1 ∪ L 2 ). Lemma 2. [11, 12] From Lemma 3(1) follows Corollary 1, provided that Theorem 1 is true. Theorem 1 itself will be proven in Sect. 3.

Let us recall from [14] a special "pop-controlled form" (called an ideal shape), in which the pop operations always take place by first reading an input symbol and then making a series (one or more) of the pop operations without reading any further input symbol. This notion was originally introduced for one-way probabilistic pushdown automata (or 1ppda's); however, in this exposition, we apply this notion only to 1dpda's. To be more formal, a 1dpda in an ideal shape is a 1dpda restricted to take only the following transitions. (1) Scanning σ ∈ Σ, preserve the topmost stack symbol (called a stationary operation). It was shown in [14] that any 1ppda can be converted into its "errorequivalent" 1ppda in an ideal shape. In Lemma 4, we restate this result for 1dpda's. We say that two 1dpda's are (computationally) equivalent if, for any input x, their acceptance/rejection coincide. The push size of a 1ppda is the maximum length of any string pushed into a stack by any single move.

Let n ∈ N + . Any n-state 1dpda M with stack alphabet size m and push size e can be converted into another (computationally) equivalent 1dpda N in an ideal shape with O(en 2 m 2 (2m) 2enm ) states and stack alphabet size O(enm(2m) 2enm ).

We want to define two basic notions of boundaries and crossing state-stacks. For this purpose, we visualize a single move of a 1dpda M as three consecutive actions: (i) firstly replacing the topmost stack symbol, (ii) updating an inner state, and (iii) thirdly either moving a tape head or staying still.

A boundary is a borderline between two consecutive tape cells. We index all such boundaries from 0 to || cx$| as follows. The boundary 0 is located at the left of cell 0 and boundary i+1 is in between cell i and i+1 for every index i ≥ 0. When a string xy is written in |xy| consecutive cells, the (x, y)-boundary indicates the boundary |x| + 1, which separates between x and y. A boundary block between boundaries t 1 and t 2 with t 1 ≤ t 2 is a consecutive series of boundaries between t 1 and t 2 (including t 1 and t 2 ). These t 1 and t 2 are called ends of this boundary block. For brevity, we write [t 1 , t 2 ] to denote a boundary block between t 1 and t 2 . For two boundaries t 1 , t 2 with t 1 < t 2 , the (t 1 , t 2 )-region refers to the consecutive cells located in the boundary block [t 1 , t 2 ]. When an input string x is written in the (t 1 , t 2 )-region, we conveniently call this region the x-region unless the region is unclear from the context.

The stack height of M at boundary t is the length of the stack content while passing the boundary t. E.g., a stack content a 1 a 2 · · · a k has stack height k.

A boundary block [t 1 , t 2 ] is called convex if there is a boundary s between t 1 and t 2 (namely, s ∈ [t 1 , t 2 ]) such that there is no pop operation in the (t 1 , s)region and there is no push operation in the (s, t 2 )-region. A boundary block [t 1 , t 2 ] is flat if the stack height does not change in the (t 1 , t 2 )-region. A boundary block [t 1 , t 2 ] with t 1 < t 2 is pseudo-convex if the stack height at every boundary s ∈ [t 1 , t 2 ] does not go below h 2 − h1−h2 t2−t1 (s − t 1 ), where h i is the stack height at boundary t i for any i ∈ {1, 2}. By their definitions, either convex or flat boundary blocks are also pseudo-convex.

A peak is a boundary t such that the stack heights at the boundaries t−1 and t+1 are smaller than the stack height at the boundary t. A plateau is a boundary block [t, t ] such that any stack height at a boundary i ∈ [t, t ] is the same. A hill is a boundary block [t, t ] such that (i) the stack height at the boundary t and the stack height at the boundary t coincide, (ii) there is at least one peak at a certain boundary i ∈ [t, t ], and (iii) both [t, i] and [i, t ] are convex. The height of a hill is the difference between the topmost stack height and the lowest stack height.

Given strings over alphabet Σ, ε-enhanced strings are strings over the extended alphabet Σ ε = Σ ∪ {ε}, where ε is treated as a special input symbol expressing the absence of symbols in Σ. An ε-enhanced 1dpda (or an ε-1dpa, for short) is a 1dpda that takes ε-enhanced strings and works as a standard 1dpda except that a tape head always moves to the right without stopping. This tape head movement is sometimes called "real time".

For any 1dpda M , there exists an ε-1dpda N such that, for any input string x, there is an appropriate ε-enhanced stringx for which M accepts (resp., rejects) x iff N accepts (resp., rejects)x. Moreover,x is identical to x except for the ε symbol and is uniquely determined from x and M .

Let M be either a 1dpda or an ε-1dpda, and assume that M is in an ideal shape. A crossing state-stack pair at boundary i is a pair (q, γ) of inner state q and stack content γ. In a computation of M on input x, a crossing state-stack pair (q, γ) at boundary i refers to the machine's current status where (1) M is reading an input symbol, say, σ at cell i − 1 in a certain state, say, p with the stack content aγ and then M changes its inner state to q, changing a by either pushing another symbol b satisfying γ = baγ or popping a with γ = γ . Any computation of M on x can be expressed as a series of crossing state-stack pairs at every boundary in the | cx$-region. Two boundaries t 1 and t 2 with t 1 < t 2 are mutually correlated if there are two crossing state-stack pairs (q, γ) and (p, γ) at the boundaries t 1 and t 2 , respectively, for which the boundary block [t 1 , t 2 ] is pseudo-convex. Moreover, assume that t 1 < t 2 < t 3 < t 4 . Two boundary blocks [t 1 , t 2 ] and [t 3 , t 4 ] are mutually correlated if (i) [t 1 , t 2 ], [t 2 , t 3 ], and [t 3 , t 4 ] are all pseudo-convex, (ii) (q, γ) and (p, αγ) are crossing state-stack pairs at the boundaries t 1 and t 2 , respectively, and (iii) (s, αγ) and (r, γ) are also crossing state-stack pairs at the boundaries t 3 and t 4 , respectively, for certain p, q, r, s ∈ Q, γ ∈ (Γ (−) ) * Z 0 , and α ∈ (Γ (−) ) * .

If an ε-1dpda is in an ideal shape, then it pops exactly one stack symbol whenever it reads a single symbol of a given ε-enhanced input string. Lemma 6. Let w be any string.

such that t 1 is the (x 1 , x 2 )-boundary and t 2 is the (x 2 , x 3 )-boundary. If the boundaries t 1 and t 2 are mutually correlated and inner states at the boundaries t 1 and t 2 coincide, then it follows that w ∈ L iff 

We intend to present the proof sketches of three separation claims (Theorems 1 and 2 and Proposition 1) before verifying the pumping lemma. There is a constant c > 0 that satisfies the lemma. Let n = c + 1 and consider w i = a n b in for each index i ∈ [d]. Since each w i belongs to L (d) , we can take an index pair j, k ∈ [d] with j < k such that w j and w k satisfy the conditions of the lemma. Since Condition (1) of the lemma is immediate, we hereafter consider Condition (2) . Let x = a n b jn−1 , y = b, andŷ = b (k−j)n+1 . Firstly, we consider Case (a) with a factorization x = x 1 x 2 x 3 x 4 x 5 with |x 2 x 4 | ≥ 1 and |x 2 x 3 x 4 | ≤ c. Since x 1 x i 2 x 3 x i 4 x 5 y ∈ L (d) for any number i ∈ N, we conclude that x 2 ∈ {a} * and x 4 ∈ {b} * . Let x 2 = a m and x 4 = b r for certain numbers m, r ∈ [c]. Note that x 1 x i 2 x 3 x i 4 x 5 y equals a n+(i−1)m b jn+(i−1)r . Hence, n + (i − 1)m = g(jn + (i − 1)r) for a certain g ∈ [d]. This implies that (jg−1)n = (m−gr)(i−1). We then obtain jg − 1 = m − gr = 0, which further implies that j = g = 1 and m = r. Similarly, from x 1 x i 2 x 3 x i 4 x 5ŷ ∈ L (d) , it follows that n + (i − 1)m = g (kn + (i − 1)r). Thus, (kg − 1)n = (m − g r)(i − 1). This implies k = g = 1 and m = r. Since j = k, we obtain a contradiction.

Next, we consider Case (b) with appropriate factorizations x = x 1 x 2 x 3 , y = y 1 y 2 y 3 , andŷ = z 1 z 2 z 3 with |x 2 | ≥ 1 and |x 2 x 3 | ≤ c such that x 1 x i 2 x 3 y 1 y i 2 y 3 ∈ L (d) and x 1 x i 2 x 3 z 1 z i 2 z 3 ∈ L (d) for any number i ∈ N. Since |x 2 x 3 | ≤ c, we obtain x 2 ∈ {b} * . Assume that x 2 = b m for a certain number m ∈ [c]. This is impossible because x 1 x i 2 x 3 y 1 y i 2 y 3 has the form a n b jn+(i−1)m and the exponent of b is not of the form rn for any number r ∈ [d].

General Case of d ≥ 2: We begin with proving this case by considering d 1dpda's M 1 , M 2 , . . . , M d . The language recognized by each machine M i is denoted by L(M i ). Let us assume that L = d i=1 L(M i ). Take d + 1 strings w 1 , w 2 , . . . , w d+1 in L and assume that each w k has the form xy (k) with |x| > c. Since all w k 's are in L, define a function f as follows. Let f (k) denote the minimal index i k satisfying that w k ∈ L(M i k ) but w k / ∈ L(M j ) for all j = i k . Since there are at most d different languages, there are two distinct indices j 1 , j 2 ∈ [d + 1] such that f (j 1 ) = f (j 2 ). In what follows, we fix such a pair (j 1 , j 2 ).

Consider the case of w = xy (j1) and w = xy (j2) . Take arbitrary factorizations w = x y and w = x ŷ. We apply the basis case of d = 1 again and obtain one of the following (a)-(b). (a) There is a factorization x = x 1 x 2 x 3 x 4 x 5 with |x 2 x 4 | ≥ 1 and |x 2 x 3 x 4 | ≤ c such that x 1 x i 2 x 3 x i 4 x 5 y ∈ L and x 1 x i 2 x 3 x i 4 x 5 y ∈ L for any number i ∈ N. (b) There are factorizations x = x 1 x 2 x 3 , y = y 1 y 2 y 3 , and y = z 1 z 2 z 3 such that |x 2 | ≥ 1, |x 2 x 3 | ≤ c, x 1 x i 2 x 3 y 1 y i 2 y 3 ∈ L, and x 1 x i 2 x 3 z 1 z i 2 z 3 ∈ L for any number i ∈ N.

Deterministic context free languages

Iteration theorems for deterministic families of languages. Fundamenta Informaticae

A generalization of context-free determinism

A pumping lemma for real-time deterministic context-free languages

Iteration theorems for families of strict deterministic languages

The Boolean closure of linear context-free languages

An Introduction to Kolmogorov Complexity and Its Applications

An infinite hierarchy of intersections of context-free languages

Limited automata and regular languages

A strong pumping lemma for context-free languages

The Boolean closures of the deterministic and nondeterministic context-free languages

Nondeterminism and Boolean operations in pda's

under a slightly different title 14. Yamakami, T.: Behavioral Strengths and weaknesses of various models of limited automata

A pumping lemma for deterministic context-free languages

. Take a pumping-lemma constant c > 0 that satisfies Lemma 1. We set n = c+1 and consider the set. Lemma 1 guarantees the existence of a specific distinct pairBy Lemma 1, since |x | > c, there are two conditions to consider separately. Condition (1) is not difficult. Next, we consider Condition (2) .Note that x y = xy (j1) and x ŷ = xy (j2) . There are three factorizations x = u 1 u 2 u 3 with |u 2 | ≥ 1 and |u 2 u 3 | ≤ c, y = y 1 y 2 y 3 , andŷ = z 1 z 2 z 3 satisfying both u 1 u i 2 u 3 y 1 y i 2 y 3 ∈ L and u 1 u ifor a certain e ≥ 1. In particular, take i = 2. Note that u 1 u 2 2 u 3 y 1 y 2 2 y 3 has factors a j1n. Thus, we obtain j 1 n = j 1 n + 2e − 1, a clear contradiction.We omit from this exposition the proofs of Theorems 1(2), 2, and Proposition 1. These proofs will be included in its complete version.

We are now ready to provide the proof of the pumping lemma for DCFL[d] (Lemma 1). Our proof has two different parts depending on the value of d. The first part of the proof targets the basis case of d = 1. This special case directly corresponds to Yu's pumping lemma [15, Lemma 1] . To prove his lemma, Yu utilized a so-called left-part theorem of his for LR(k) grammars. We intend to re-prove Yu's lemma using only 1dpda's with no reference to LR(k) grammars. Our proof argument is easily extendable to one-way nondeterministic pushdown automata (or 1npda's) and thus to the pumping lemma for CFL. The second part of the proof deals with the general case of d ≥ 2. Hereafter, we give the sketches of these two parts.Basis Case of d = 1: Let Σ be any alphabet and take any infinite dcf language L over Σ. Let us consider an appropriate ε-1dpda M = (Q, Σ, {| c, $}, Γ, δ, q 0 , Z 0 , Q acc , Q rej ) in an ideal shape that recognizes L by Lemmas 4-5. For the desired constant c, we set c = 2 |Q| . Firstly, we take two arbitrary strings xy and xŷ over Σ with y[1] =ŷ[1] = a and |x| > c.Our goal is to show that Condition (2) in the basis case of d = 1 holds. There are four distinct cases to deal with. Hereafter, we intend to discuss them separately. Note that, since M is one-way, every crossing state-stack pair at any boundary in the x-region does not depend on the choice of y andŷ.Case 1: Consider the case where there are two boundaries t 1 , t 2 with 1 ≤ t 1 < t 2 ≤ |xa| and |t 2 − t 1 | ≤ c such that (i) the boundaries t 1 and t 2 are mutually correlated and (ii) inner states at the boundaries t 1 and t 2 coincide. In this case, we factorize x into x 1 x 2 x 3 so that t 1 = |x 1 | and t 2 = |x 1 x 2 |. By Lemma 6(1), it then follows that, for any number i ∈ N, x 1 x i 2 x 3 y ∈ L and x 1 x i 2 x 3ŷ ∈ L. Case 2: Consider the case where there are four boundaries t 1 , t 2 , t 3 , t 4 with 1 ≤ t 1 < t 2 < t 3 < t 4 ≤ |xa| and |t 4 − t 1 | ≤ c and there are p, q ∈ Q, γ ∈ (Γ (−) ) * Z 0 , and α ∈ (Γ (−) ) * for which (i) (q, γ) and (q, αγ) are the crossing state-stack pairs respectively at the boundaries t 1 and t 2 , (ii) (p, αγ) and (p, γ) are the crossing statestack pairs respectively at the boundaries t 3 and t 4 , and (iii) the boundary block [t i , t i+1 ] for each index i ∈ [3] is pseudo-convex. We then take a factorization x = [4] . Note that |x 2 x 4 | ≥ 2 because of t 1 < t 2 and t 3 < t 4 . By an application of Lemma 6(2), we conclude that, for any z ∈ {y,ŷ}, Clearly, m > |Q| 2 . We choose {t i } i∈ [m] and {r i } i∈ [m] so that (i) for each index i ∈ [m], t i and r i are boundaries in the y-region and in theŷ-region, respectively, satisfying that t 1 < t 2 < · · · < t m and r 1 < r 2 < · · · < r m , and (ii) for each index i ∈ [m − 1], [s i , s i+1 ] is mutually correlated to [t i , t i+1 ] in the y-region and also to [r i , r i+1 ] in theŷ-region. Note that the boundary blocks [t 1 , t 2 ], . . . , [t m−1 , t m ], [r 1 , r 2 ], . . . , [r m−1 , r m ] are all pseudo-convex. Since m > |Q| 2 , it follows that there is a pair j 1 , j 2 ∈ [m] with j 1 < j 2 such that inner states at the boundaries r j1 and r j2 coincide. Using Lemma 6(2), we can obtain the desired conclusion.Case 4: Assume that Cases 1-3 fail. In this case, we define a notion of "true gain" in the R-region and estimate its value. Choose s 1 and s 2 so that |xa| − c ≤ s 1 , s 2 ≤ |xa|, and the boundary block [s 1 , s 2 ] is pseudo-convex. Let G(s 1 , s 2 ) denote the set of boundary blocks [t 1 ,is pseudo-convex but cannot be flat, (ii) [t j , t j+1 ] is pseudo-convex (and could be flat), (iii) there are crossing state-stack pairs (q i , γ), (q i , γ) at the boundaries t i , t i for every i ∈ [m], (iv) the stack height at the boundary t i is higher than the stack height at the boundary t i , (v) the boundary t i is a pit (i.e., the lowest point within its small vicinity). Define the true gain tg(s 1 , s 2 ) to be m i=1 |t i − t i |. It is possible to prove that tg(s 1 , s 2 ) > |Q| 3 . Using this inequality, we can employ an argument similar to Case 3 to obtain the lemma.