Growing Context-Sensitive Languages and Automata

Gerhard Buntrock

Institut für Informatik Universität Würzburg D-97072 Würzburg bunt@informatik.uni-wuerzburg.de

September 1993

Abstract. One motivation for this investigation of the growing context-sensitive languages (GCSL) is their low complexity: we show that they are accepted by one-way auxiliary pushdown automata in polynomial time with a simultaneous logarithmic space bound. Further we introduce the model of a two-pushdown automaton (TPDA). Since the unrestricted model accepts all recursive enumerable languages, we investigate several restrictions which give us characterizations of the classes CFL, DCFL, GCSL, and CSL. The restrictions are based on a generalization of the weight concept for grammars. The essential restriction is given by the so called shrinking TPDA, i. e. an automaton which looses some weight in every computation step. As such main result we get that shrinking TPDAs characterize growing context-sensitive languages. To prove the characterization we adapt the connection theorem from Gladkij and Book and conclude that growing context-sensitive languages can be described by connected growing context-sensitive grammars. The deterministic version of the shrinking TPDA is stronger than deterministic pushdown automata. Interestingly deterministic TPDAs need only linear time and accept languages from CFL\DCFL and even languages outside of CFL.

1 Introduction

In formal language theory automata can be very useful to obtain an impression of the complexity of a language class or to get easy proofs for closure properties (e. g. closure under inverse homomorphisms).

The class of growing context-sensitive languages (GCSL) is of some importance since it is an enrichment of the context-free languages with the same complexity: it is contained in LOGCFL, the closure of the class of context-free languages (CFL) under logarithmic space-bounded manyone reductions [DW86]. In a first result of this paper (Theorem 3.1) we will sharpen this result: we will show that GCSL is in OW-LOGCFL, the closure of CFL under one-way logarithmic space-bounded many-one reductions (Theorem 3.1).

Another important fact, that motivates our investigation, is that GCSL forms an abstract family of languages [BL92]. In order to find an automaton characterization we give weights to the symbols and claim that the weight of a configuration has to decrease in every step; we call this a shrinking automaton. Pushdown automata with two pushdowns, so called two-pushdown automata (TPDA), with such a shrinking restriction characterize the desired class GCSL. Shrinking automata have an important relation to forgetting automata [JMP93] (Theorem 5.3).

In our model the input is found on the second pushdown. Comparable models (with only one pushdown) have already been investigated: in [BDLM91] the input is on the pushdown and additionally a bounded working tape is available; in [Mag69] besides the pushdown the input is on a writable tape (bounded by the length of the input, cf. an LBA). Cook modified the latter model to the important model of auxiliary pushdown automata [Coo71]. Brandenburg introduced one-way auxiliary pushdown automata [Bra77]. With a polynomial time bound and a simultaneous logarithmic space bound these automata characterize OW-LOGCFL [Lau88]. All these models have the property that the classes defined by their automata form a basis for the recursively enumerable sets^{1} (for a discussion of this topic see [Lan93]). The same holds for GCSL.

This property is reflected by the well known fact that automata with two pushdowns accept all recursive enumerable sets, but shrinking TPDAs accept only GCSL (Theorem 6.5). Nonstrictly shrinking TPDAs (the weights of the configurations are not growing) characterize the context-sensitive languages.

The main difficulty in proving that GCSL can be accepted by shrinking TPDAs is the proof of the connectivity theorem for GCSL (Theorem 7.3). Connectivity means that there exists a grammar such that for all derivations there is an equivalent derivation which is connected. The connectivity theorem is proved by adapting the connectivity theorem for context-sensitive languages, a result by [Gla64, Boo69] (Sect. 7).

Another interesting model is the deterministic TPDA. We suspect that the shrinking version does not even accept the linear languages (e. g. {w w^{←} |w ∈ {0, 1}^{∗}}). On the other hand it can be shown that the languages {a^{n}b^{n}c^{n}|n ∈ IN} and {a^{n}b^{n}|n ∈ IN} ∪ {a^{n}b^{2n}|n ∈ IN} are accepted by such automata (Theorem 5.1). Note that the first language is not in CFL and the second one is in CFL\DCFL. Moreover, the TPDA is only a slight generalization of the ordinary pushdown automaton: if we restrict the input pushdown to be read-only, it accepts exactly the context-free languages.

2 Preliminaries and Weight Functions

We assume the reader to be familiar with elementary formal language theory and computational complexity theory, and use the standard notations according to [HU79, Sal73]. The set of natural numbers is denoted by IN. A grammar is a quadruple ⟨N, T, S, P ⟩, where N and T are finite, disjoint alphabets of nonterminal and terminal symbols, respectively; S ∈ N is a start symbol and P is a finite set of productions of the form α → β, with α, β ∈ (N ∪ T)^{∗}, where α contains at least one nonterminal symbol. The grammars fulfilling |α| ≤ |β| for all productions from P are called context-sensitive grammars (CSG).

Replacing the inequality above by a sharp one, we obtain growing context-sensitive grammars.

Definition 2.1 A context-sensitive grammar G = ⟨N, T, S, P ⟩ is growing if S does not appear on the right side of any rule and ∀(α → β) ∈ P : α ≠ S ⟹ |α| < |β|. We denote the growing grammars by GCSG and the class of languages generated by such grammars by GCSL.

We distinguish two types of grammars which are growing with respect to a weight function, namely those, which are in addition context-sensitive, and those, which are not. We define a weight function to be a homomorphism from words with concatenation to the natural numbers (IN) with addition:

1I. e. the closure under homomorphisms yields all recursive enumerable sets (cf. [Smu61]).

Definition 2.2 We call a function f : Σ^{∗} → IN a weight function if ∀a ∈ Σ : f(a) > 0 and ∀w, v ∈ Σ^{∗} : f(w) + f(v) = f(wv).

It has been proven that weight functions for grammars are good tools to restrict grammars such that they characterize CSL or GCSL [BL92]. Such grammars are often easier to construct than context sensitive or growing ones. Here we recall the definitions:

Definition 2.3 Let G = ⟨N, T, S, P ⟩ be a grammar and f : (N ∪ T)^{∗} → IN a weight function. We call G quasi growing if f(α) < f(β) for all productions (α → β) ∈ P. We denote the set of quasi growing grammars by QGG. We call G quasi growing context-sensitive if it is quasi growing and a context-sensitive grammar. We denote the set of quasi growing context-sensitive grammars by QGCSG. We call G quasi context-sensitive if f(α) ≤ f(β) for all productions (α → β) ∈ P. We denote the set of quasi context-sensitive grammars by QCSG.

In quasi growing grammars sentence forms (with respect to weight functions) are growing in every derivation step. Turning to automata, we will replace this effect by shrinking the configurations in every computation step. In this way we now apply the weight concept for automata:

Definition 2.4 Let A be an automaton. All configurations of A may be encoded in the alphabet Σ and let f : Σ^{∗} → IN be a weight function. We call A shrinking if the weights of the configurations in every step are decreasing. We call A nonstrictly shrinking if the weights of the configurations in every step are not increasing.

3 On the Complexity of GCSL

Context-free languages are very important since they are easy to handle and of low complexity. Here we will show that concerning their complexity there is no difference between CFL and GCSL.

On the other hand it is known from [BL93] that the complexity of the variable membership problem for grammars^{2} characterizing GCSL varies over a wide area of complexity classes even though they characterize the same language class. For GCSG we have NP-completeness, for QGCSG PSPACE-completeness, and for QGG NEXPTIME-completeness [BL93]. Note that all these results are proven by grammars producing a context-free language. Therefore the result of succinct representation of languages applies to CFL too.

From [DW86] we know that GCSL belongs to LOGCFL, i. e. the closure of CFL under logarithmic space-bounded reductions. This class is characterized by polynomially time-bounded pushdown automata with an auxiliary logarithmically bounded tape (aux-PDA[logspace,poltime]) [Sud78].

In a similar way OW-LOGCFL is defined and characterized. (For one-way logarithmic spacebounded reductions see [HIM78], for one-way polynomially time-bounded pushdown automata with an auxiliary logarithmically bounded tape (OWauxPDA[logspace,poltime]) [Bra77], and for the characterization [Lau88].) Here we will strengthen Dahlhaus’ and Warmuth’s result:

Theorem 3.1 Every language in GCSL can be accepted by an auxPDA[logspace,poltime] with one-way input tape.

2I. e. input: a grammar, a string, question: is it possible to derive the string according to the grammar?

Before we will give a proof we need some notions and notations. A derivation according to a GCSG is represented by a directed acyclic planar graph with to kinds of nodes, production nodes and symbol nodes [DW86]. Symbol nodes have only one incoming and one outgoing edge. Every edge in such a graph connects a production and a symbol node. A path in a derivation graph can have incoming and outgoing edges to the left and to the right. All these edges have one end in a production node of the path. We call a symbol node connected with an outgoing edge to the right (left) of the path an outgoing branching point to the right (left) and a symbol node connected with an incoming edge to the right (left) of the path an incoming branching point to the right (left). A branching point of a path is called a self-matching point if it is an incoming and an outgoing branching point of this path. A branching point of two different paths is called a matching point if it is an incoming branching point to the right of the one path and an outgoing branching point to the left of the other path. It is evident that the branching points of a matching point are identical, i. e. they have the same symbol. Dahlhaus and Warmuth make the following important observation:

Proposition 3.2 [DW86] For every derivation graph according to a growing context-sensitive grammar and every nonterminal symbol node in this graph there exists a terminal symbol such that they are connected by a logarithmically bounded path.

Proof (of Theorem 3.1). Let G = ⟨N, T, S, P ⟩ a GCSG and w ∈ T^{∗} an input string. Now we describe an auxPDA M with one-way input which will accept L(G). Since the auxPDA has a logarithmically bounded working tape we can assume that every cell on the pushdown is of logarithmic length. At first we will describe some important procedures:

• “Self-matching:” For a path the self-matching points are nondeterministically computed: it is guessed an outgoing branching point P and an incoming branching point Q of the same side and marked with the same symbol; now it is guessed if they should be identified as a self-matching point. This is done only if all branching points of the same side between P and Q are self-matching points too.

•• “Left matching:” For a path φ_{p} on the pushdown and a path φ_{w} on the working tape a left matching (i. e. φ_{p} should be to the left of φ_{w}) is nondeterministically computed. If an outgoing (incoming) branching point P to the left of φ_{p} has the same symbol as an incoming (outgoing) branching point Q to the right of φ_{t} it is guessed, if they should be identified to a matching point. This is done only if all branching points before P on φ_{p} and before Q on φ_{w} are matching points too.

••• “Right matching:” For a path φ_{p} on the pushdown and a path φ_{w} on the working tape a right matching (i. e. φ_{p} should be to the right of φ_{w}) is computed by interchanging the contents of the working tape and the top of the pushdown. Now we can use ••. After computing the matching points we interchange the contents again.

•••• “Recursion:” Let φ_{w} on the working tape and φ_{p} on the top of the pushdown, if there is any. With • all self-matching points of φ_{w} are computed and marked. With •• all left matching points of φ_{w} and φ_{p} are computed and marked on the pushdown and on the tape.

– If φ_{w} contains an unmarked branching point P to the left, it is taken and with Proposition 3.2 we guess a path beginning at P and ending at a terminal symbol x ∈ T and store it on the tape, while φ_{w} is pushed on the pushdown. Recursively •••• is started.

∗ If P was the only unmarked branching point to the left on the path φ_{w} the next input symbol is read and compared with the sink of φ_{w}. If the symbols are not equal the input is rejected.

– If there does not exist any unmarked branching point to the left, the last unmarked branching point P to the right is taken and again with Proposition 3.2 we guess a path beginning at P and ending at a terminal symbol x ∈ T and store it on the tape, while φ_{w} is pushed on the pushdown. With ••• we mark all matching points and again •••• is started.

– If there does not exist any unmarked branching point neither to the left nor to the right, the path is erased, the top of the pushdown will be moved to the tape, and again recursively •••• is started.

Now we can describe how M is working: at first M guesses a path φ of logarithmic length starting at S and ending at a symbol x ∈ T and stores φ on the tape. Now M performs the recursive procedure ••••. M continues if there is a path on the tape. On empty tape and empty pushdown M accepts if the entire input is read, otherwise M rejects.

Since M accepts the input iff there is a derivation according to G, the OWauxPDA M accepts L(G). Since the number of steps is linearly bounded in the number of production nodes in the simulated derivation, the time of M is also linearly bounded in the length of the input. □

Note that this one-way algorithm is still working for quasi growing grammars.

4 Two-Pushdown Automata

Now we will give a general definition of the two-pushdown automaton. Without further restrictions this automaton can accept all recursively enumerable sets. The shrinking and the nonstrictly shrinking versions will characterize GCSL and CSL, respectively. Other models in order to characterize GCSL are possible too. Krzysztof Loryś proposes an automaton simulating grammars from GCSG [Lor93].

Definition 4.1 A two-pushdown automaton (TPDA) is a nondeterministic automaton with two pushdowns and is denoted by a 6-tuple: M = (Q, Σ, Γ, δ, q_{0}, ⊥, F)

Q is a finite set of states. Σ is an alphabet, called the input alphabet. Γ is an alphabet, called the working alphabet (Σ ⊆ Γ). q_{0} ∈ Q the initial state. ⊥ is a particular pushdown symbol, called the start symbol (⊥ ∈ Γ \ Σ). F ⊆ Q is the set of final states. δ is a mapping from (Q × Γ × Γ) to finite subsets of (Q × Γ^{∗} × Γ^{∗}).

Additionally we assume that Q and Γ are disjoint. In the case that δ is a mapping to sets with only one element M is called a deterministic two-pushdown automaton (DTPDA).

Let w be an input string. At the beginning w⊥ stands on the right pushdown and ⊥ on the left. We denote this by: ⊥q_{0}w⊥. Intuitively we say that the automaton looks with its state on both pushdowns, on the left one from the right and on the right one from the left. Therefore we write the pushdown contents of the left pushdown backwards. The interpretation of δ(q, A, B) = {(q_{1}, α_{1}, β_{1}), (q_{2}, α_{2}, β_{2}), ..., (q_{m}, α_{m}, β_{m})} where q, q_{1}, ..., q_{m} ∈ Q, A, B ∈ Γ, α_{1}, β_{1}, α_{2}, β_{2}, ..., α_{m}, β_{m} ∈ Γ^{∗} is that the TPDA in state q, with the top symbols A and B on the pushdowns can for any i enter state q_{i}, replace the symbol A by the string α_{i} and B by β_{i}.

We denote this by: γ_{1}AqBγ_{2} ⊢_{M} γ_{1}α_{i}q_{i}β_{i}γ_{2} As usual, let ⊢_{M}^{∗} denote the reflexive and transitive closure of ⊢_{M}. The sets

\begin{aligned}N(M) := & \{w ∈ Σ^{∗} & |∃q ∈ Q & : ⊥q_{0}w⊥ ⊢_{M}^{∗} q\} \\ L(M) := & \{w ∈ Σ^{∗} & |∃q ∈ F, α ∈ Γ^{∗} & : ⊥q_{0}w⊥ ⊢_{M}^{∗} αq\} \end{aligned}

are called the accepted languages by empty pushdowns or by final state, respectively. Note that in the definition of L(M) we expect the right pushdown to be empty. With this condition we enforce the TPDA to read all the input symbols. We argue that such a condition is implicitly contained in other models.

Proposition 4.2 A language is accepted by a TPDA by empty pushdowns if and only if it is accepted by a TPDA by final state.

The same holds for shrinking, nonstrictly shrinking, deterministic shrinking, and deterministic nonstrictly shrinking TPDA.

Proof.

(i) ‘⟹’ Let M = (Q, Σ, Γ, δ, q_{0}, ⊥, ∅) be a TPDA. We describe a TPDA M′ = (Q′, Σ, Γ′, δ′, q_{1}, \underline{⊥}, \{q_{fin}\}) and show N(M) = L(M′). The automaton M′ will perform the following steps:

\underline{⊥}q_{1}w\underline{⊥} ⊢ \underline{⊥}⊥q_{1}w\underline{⊥} ⊢^{∗} \underline{⊥}⊥wq_{2}\underline{⊥} ⊢ \underline{⊥}⊥wq_{2}⊥\underline{⊥} ⊢^{∗} \underline{⊥}⊥q_{0}w⊥\underline{⊥}

Then M′ will simulate M on the configuration ⊥q_{0}w⊥. Clearly, it is easy to construct M′ in such a way that it stops in the final state q_{fin} iff M stops with empty pushdowns. ‘⟸’ Let M = (Q, Σ, Γ, δ, q_{1}, ⊥, F) be a TPDA. We describe a TPDA M′ = (Q′, Σ, Γ′, δ′, q_{1}, \underline{⊥}, ∅) and show L(M) = N(M′). M′ will start in the same way as above (cf. ‘⟹’). But M′ will stop with at least the symbol \underline{⊥} in both pushdowns, if M is accepting. In the case that M stops in a final state, M′ can empty its left pushdown.

(ii) We show, that the proposition remains true for shrinking and nonstrictly shrinking automata: ‘⟹’ The only problem is to copy the string w from one pushdown to the other. For this we need a copy of Σ and \underline{⊥} in Γ′ with sufficiently smaller weights. In this way the same construction will work. ‘⟸’ Again we need only copy w from one pushdown to the other.

(iii) For the deterministic cases we observe, all steps given in (i) can be performed deterministically.

□

If in the TPDA model we postulate the transition function δ to be a mapping from (Q×Γ×Γ) to finite subsets of (Q×Γ^{∗}×Γ) it characterizes the context-free languages^{3}. In the case of DTPDA we get the deterministic context-free languages. Note that the additional symbol on the input tape gives more power to the DTPDA accepting by empty pushdown than the DPDA accepting by empty pushdown since the real input language for the DTPDA is prefix free^{4}. Therefore for the case of deterministic automata we have a small difference in the models of PDA and shrinking TPDA.

3Substituting (Q × Γ^{∗} × Γ) by (Q × Γ^{∗} × {ε}) yields a “PDA” without ε-moves.

4L is prefix free if ∀w ∈ L : v ≠ ε ⟹ wv ∉ L.

[figure: DTPDA; TPDA; PDA; DPDA]

Inclusion relation of language classes defined by pushdown automata

5 On the power of shrinking Two-Pushdown Automata

At first we will compare PDAs and shrinking TPDAs. Further we relate forgetting automata to shrinking TPDAs.

Theorem 5.1 1. There exists a language that is accepted by a shrinking DTPDA, but not by a PDA.

2. There exists a language that is accepted by a PDA and by a shrinking DTPDA, but not by a DPDA.

Proof.

1. We show that L := {a^{n}b^{n}c^{n}|n ∈ IN} is accepted by a DTPDA. Let A, B, and C be the numbers of occurrences of a, b, and c in the input string, respectively. The DTPDA M works as follows: M copies the input from the right pushdown to the left and compares the parity of A, B, and C. The comparison is done by substituting pairs of symbols by singletons. If the parities do not coincide, M rejects the input; otherwise M again copies the contents of the pushdown and compares the parity. M accepts the input if both pushdowns are empty. In this way M checks, if all binary representations of A, B, and C are equal.

On the other hand, it is a well known fact that there is no PDA which accepts L.

2. We show that L := {a^{n}b^{n}|n ∈ IN}∪{a^{n}b^{2n}|n ∈ IN} is accepted by a DTPDA. This DTPDA checks if the input is of the form a^{n}b^{n} with the method above. Simultaneously it checks with the same method, if the input is of the form a^{n}b^{2n}. It is well known that there is no DPDA which accepts L (see e. g. [HU79]).

□

This result is interesting since the class of deterministic linear time decidable sets has important applications (e. g. in parsing theory). Note that it is also possible to show the existence of a language that is accepted by a PDA but not by a shrinking DTPDA. For this we need 3.1, our characterization (Theorem 6.5), and the result of Lautemann that one-way auxPDA with sublinear space cannot accept the language {ww|w ∈ Σ^{∗}} ([Lau88], for an similar result see [Bra77]). In this way it can be shown that the complement of {w#w|w ∈ (Σ \ {#})^{∗}} belongs to CFL but is not accepted by any DTPDA.

In Section 6 we show that shrinking TPDAs characterize GCSL. With deterministic shrinking TPDAs we define DGCSL:

Definition 5.2

DGCSL := {L | ∃M ∈ DTPDA, M is shrinking, L(M) = L}

For context-free grammars it is known that the emptyness problem is decidable (pumping lemma). Note that even for intersections of linear languages (LIN) this problem is undecidable (e. g. [WW86]). This holds since the emptiness problem for every basis for the recursive enumerable sets is undecidable. Remember that DTPDAs accept all recursive enumerable languages. From this we can conclude that DGCSL forms a basis for the recursive enumerable sets. Therefore we know that the emptyness problem for shrinking DTPDAs is undecidable. Now it is also clear that e. g. the equality problem for DGCSL is also undecidable. This contrasts the long standing open question concerning the equality-problem for DCFL (e. g.[HU79]).

Forgetting automata [JMP93] are restricted linear bounded automata performing only three different operations: moving (MV), erasing (ER), and deleting (DL). The difference between erasing and deleting is that erased symbols are rewritten by a unique blank symbol where deleting means a “cut out” of the cell. All these operations can be used in two different forms: in direction right and left. With this six different operations ({MV_{R}, MV_{L}} = MV, {ER_{R}, ER_{L}} = ER, {DL_{R}, DL_{L}} = DL) several different classes are defined. For the relation to the Chomsky classes see [JMP93].

Theorem 5.3 Forgetting automata with the operations {MV_{R}, DL, ER} can be simulated by shrinking TPDAs.

Proof. (Idea) We mention here only that the simulation of moving steps in only one direction is possible by using a copy of the alphabet with smaller weights. □

We conjecture that the concept of erasing is not powerful enough to simulate shrinking automata.

6 Characterization Results

In this section we give the main motivation for the two-pushdown automata: the characterization of GCSL. The first theorem in this section is the easier part of the characterization theorem:

Theorem 6.1 Every set accepted by a shrinking TPDA can be produced by a quasi growing context-sensitive grammar.

Proof. Let M = (Q, Σ, Γ, δ, q_{0}, ⊥, ∅) be a shrinking TPDA and f : Σ∪Q → IN a weight function such that M is shrinking with respect to f. We will define a grammar G = ⟨N, T, S, P ⟩:

N := Q ∪ Γ ∪ {S}, T := Σ ∪ {q_{0}, ⊥}, ({q_{0}, ⊥} ∩ Σ = ∅)

P consists of the following rules:

\begin{matrix}∀(q′, ε, ε) ∈ δ(q, A, B) : & S → & AqB \\ ∀(q′, α, β) ∈ δ(q, A, B) : & αq′β → & AqB \end{matrix}

Now it can be proven that ⊥q_{0}w⊥ ⊢_{M}^{∗} q iff S ⇒_{G}^{∗} ⊥q_{0}w⊥ by inductively showing ⊥q_{0}w⊥ ⊢_{M}^{(n)} αqβ ⟺ αqβ ⇒_{G}^{(n)} ⊥q_{0}w⊥. From this we can conclude that N(M) ∈ GCSL, since GCSL is closed under inverse homomorphisms [BL92]. Obviously G is quasi growing with respect to the function f, if we extend the definition of f by f(S) := 1. □

From this proof we can infer:

Corollary 6.2 Every set accepted by a nonstrictly shrinking TPDA can be produced by a context-sensitive grammar.

For the next result we need the Connectivity Theorem (7.3 from the next section). It is also possible to define an automaton in order to characterize GCSL without the Connectivity theorem. For such a model we need a special state q_{s} for browsing in the contents of the pushdowns, i. e. it is allowed to make the following moves^{5}: δ(q_{s}, A, B) = {(q, A, B), (q_{s}, AB, ε), (q_{s}, ε, AB)}. Here q is a state after browsing. Note that this model is rather sensitive. Adding more than one state for browsing changes the power.

Theorem 6.3 Every growing context-sensitive language is accepted by a shrinking TPDA.

Proof. Let G = ⟨N, T, S, P ⟩ be a grammar from QGCSG with a weight function f:N ∪ T → IN such that all rules are growing with respect to this weights given by f.

By Theorem 7.3 we can assume that the grammar G ∈ QCSG is connected and the strings are produced from the left to the right. We define a TPDA with only one state M = ({q}, T, Γ, δ, q, ⊥, ∅), Γ := N ∪ T ∪ {⊥}

δ(q, ⊥, ⊥) := {(q, ε, ε)}
δ(q, S, ⊥) := {(q, ε, ⊥)}
δ(q, ⊥, S) := {(q, ⊥, ε)}
δ(q, A, B) := {(q, CD, ε), (q, C, D), (q, ε, CD) | CD → AB ∈ P }
∪ {(q, C, ε), (q, ε, C)  | C → AB ∈ P }
∪ {(q, C, B), (q, ε, CB)  |  C → A ∈ P }
∪ {(q, A, C), (q, AC, ε)  |  C → B ∈ P }

Note that in this way every sentence corresponds to a configuration and conversely. Inductively can be proven that

∃α, β : αβ = γ, ⊥αqβ⊥ ⊢_{M}^{∗} ⊥q⊥ ⟺ S ⇒^{∗} γ

For the opposite direction inductively can be proven that

γ ⇒^{∗} w ⟺ ∃α, β : αβ = γ, ⊥qw⊥ ⊢_{M}^{∗} ⊥αqβ⊥.

From this we conclude that N(M) = L(G).

In order to show that the TPDA M is shrinking we have to define a weight function. We can calculate that this TPDA is shrinking with respect to the function f, if we extend this definition by f(q) = f(⊥) = 1. □

Corollary 6.4 Every context-sensitive language is accepted by a nonstrictly shrinking TPDA.

Theorem 6.5 The class of growing context-sensitive languages is characterized by shrinking TPDAs.

Theorem 6.6 The class of context-sensitive languages is characterized by nonstrictly shrinking TPDAs.

Proof (of Theorems 6.5 and 6.6). The first one is a consequence of Theorems 6.1 and 6.3 and the second one is a consequence of Corollaries 6.2 and 6.4. □

5For the shrinking automaton we allow for this state moves without shrinking. This reflects that the part in a sentence to be substituted can be chosen arbitrarily. Proving that this automaton can be simulated by grammars we define a grammar which will delete the state simulating a step into the state q_{s}.

The Corollaries 6.2 and 6.4, can also directly be proven by taking the appropriate linear bounded automaton instead of the grammar.

7 Connectivity

Gladkij has proven that all grammars of type 0 or 1 can be transformed into equivalent connected ones of the same type [Gla64]. Our goal is to show that the same is true for quasi growing context-sensitive grammars. In the proof of the theorem we will use the proof given by Book [Boo69].

Definition 7.1 We call a derivation connected if for every triplet of sentences in this derivation γ_{1}, γ_{2} and γ_{3} it is true that, if γ_{1} ⇒ γ_{2} ⇒ γ_{3} is a part of the derivation then there exists a symbol A which belongs to the substitute in γ_{2} of the derivation step γ_{1} ⇒ γ_{2} and the same A belongs to the part in γ_{2} of the step γ_{2} ⇒ γ_{3} to be substituted. A grammar is called connected if for every derivable string w there exists a connected derivation. A grammar is called strongly connected if every derivation is connected.

Proposition 7.2 Every context-sensitive grammar G = ⟨N, T, P, S⟩ of the following form can be effectively transformed into an equivalent context-sensitive one which is strongly connected [Gla64]^{6}. If (α → β) ∈ P, then (α → β) is of one of the forms:

\begin{matrix}A → & CD \\ AB → & CD \\ A → & a \\ AB → & Ca \end{matrix}  A, B, C, D ∈ N, a ∈ T

Proof. We will only give the grammar G_{0} = ⟨N_{0}, T, P_{0}, Ŝ⟩ given in Book’s proof [Boo69], which is strongly connected: N_{0} := N ∪ N̂ where N and N̂ are disjoint sets and N̂ := {Â|A ∈ N}. The rules P_{0} := ⋃_{i=1}^{5} P_{i} are given by the following sets:

\begin{matrix}P_{1} := & \{Â → ĈD, Â → CD̂  | & A, C, D ∈ N, A → CD ∈ P \} \\ P_{2} := & \{ÂB → ĈD, ÂB → CD̂, AB̂ → ĈD, AB̂ → CD̂ | & A, B, C, D ∈ N, AB → CD ∈ P \} \\ P_{3} := & \{ÂB → Ĉa, AB̂ → Ĉa  | & A, B, C ∈ N, AB → Ca ∈ P \} \\ P_{4} := & \{Â → a, BÂ → B̂a  | & A ∈ N, A → a ∈ P \} \\ P_{5} := & \{AB̂ → ÂB  | & A, B ∈ N\} \end{matrix}

It can easily be seen that this grammar is strongly connected; since the start symbol is marked with a hat it follows from the definition of the rules that every derivable sentence from G_{0} contains at most one of the marked symbols from N̂. □

Theorem 7.3 For every quasi growing context-sensitive grammar G = ⟨N, T, P, S⟩ there exists an equivalent strongly connected quasi growing grammar. Moreover, there exists such a grammar that produces every string from the left to the right.

Proof. To use Prop. 7.2, we use that quasi growing context-sensitive grammars can be transformed in this form. In [BL92] it is shown that every quasi growing context-sensitive grammar can be transformed into Cremers’ normal form [Cre73]. The only remark is that in Cremers’ normal form the rules of the type AB → Ca are not allowed. Now we will show that a slight variation of the grammar in the proof of Prop. 7.2 is an equivalent strongly connected quasi growing context-sensitive grammar: G_{0} = ⟨N_{0}, T, P_{0}, Ŝ⟩, N_{0} := N ∪ N̂ ∪ N̄ where N, N̂, and N̄ are pairwise disjoint sets and N̂ := {Â|A ∈ N}, N̄ := {Ā|A ∈ N}. The rules are given by the following sets (compared with the rules in Prop. 7.2 we changed that in every sentence the part to the right of the symbol from N̂ consists only of symbols from N̄ ∪ T). Again the rules of P_{0} := ⋃_{i=1}^{5} P_{i} are given by the following sets:

6Gladkij and Book show a stronger result that holds also for type 0 grammars

\begin{matrix}P_{1} := & \{Â → ĈD̄, Â → CD̂ & | A, C, D ∈ N, A → CD ∈ P \} \\ P_{2} := & \{ÂB̄ → ĈD̄, ÂB̄ → CD̂, AB̂ → ĈD̄, AB̂ → CD̂ & | A, B, C, D ∈ N, AB → CD ∈ P \} \\ P_{3} := & \{ÂB̄ → Ĉa, AB̂ → Ĉa & | A, B, C ∈ N, AB → Ca ∈ P \} \\ P_{4} := & \{Â → a, B̂Ā → B̂a & | a ∈ T, A, B ∈ N, A → a ∈ P \} \\ P_{5} := & \{AB̂ → ÂB̄ & | A, B ∈ N\} \end{matrix}

Note that every derivable sentence is of a special regular form contained in the set

T^{∗} ∪ (N^{∗} N̂ N̄^{∗} T^{∗})

From this it is clear that G_{0} is equivalent to the grammar in the proof of Prop. 7.2. Let f : N ∪ T → IN be a function such that G is quasi growing with respect to f. Now with an easy calculation it can be seen that G_{0} is quasi growing with respect to the function f′ : N_{0} ∪ T → IN given by:

f′(x) := \{ \begin{matrix}3 · f(x) : & x ∈ N \\ 3 · f(x) + 1 : & x ∈ N̂ \\ 3 · f(x) + 2 : & x ∈ N̄ ∪ T \end{matrix}

□

Corollary 7.4 Every growing context-sensitive grammar can be effectively transformed into a connected one.

Proof. This is a consequence from Theorem 7.3 and [BL92]. In the proof of the characterization a grammar is effectively constructed such that the appropriate connected grammar can be found.

□

Acknowledgement

Thanks go to Hans-Jörg Burtschick, Diana Emme, Matthias Jantzen, Friedrich Otto, and Heribert Vollmer for several discussions and hints. Special thanks are due to Ulrich Hertrampf for reading and improving the readability of this paper, Krzysztof Loryś and Klaus Wagner for discussions on the shrinking TPDA, Clemens Lautemann, Krzysztof Loryś, and Gundula Niemann for discussions on the proof of Theorem 3.1.

References

[BDLM91] Gerhard Buntrock, Frank Drewes, Clemens Lautemann, and Till Mossakowski. Some modifications of auxiliary pushdown automata. Theoretical Informatics and Applications (RAIRO), 30(6):0, 1991.

[BL92] Gerhard Buntrock and Krzysztof Loryś. On growing context-sensitive languages. In Proc. of 19th ICALP, volume 623 of LNCS, pages 77–88. Springer, 1992.

[BL93] Gerhard Buntrock and Krzysztof Loryś. On variable membership problems for different contextsensitive grammars. Technical Report 60, Universität Würzburg, Institut für Informatik, Am Exerzierplatz 3, D-8700 Würzburg, 1993. To appear at 11th STACS 1994.

[Boo69] Ronald V. Book. Grammars with Time Functions. Dissertation, Harvard University, Cambridge, Massachusetts, February 1969.

[Bra77] Franz Josef Brandenburg. On one-way auxiliary pushdown automata. In Proc. of 3rd GI-Conference on Theoretical Computer Science, number 48 in LNCS, pages 132–144. Springer, 1977.

[Coo71] Stephen A. Cook. Characterizations of pushdown machines in terms of time–bounded computers. Journal of the ACM, 18(1):4–18, 1971.

[Cre73] A.B. Cremers. Normal forms for context–sensitive grammars. Acta Informatica, 3:59–73–96, 1973.

[DW86] Elias Dahlhaus and Manfred K. Warmuth. Membership for growing context–sensitive grammars is polynomial. JCSS, 33:456–472, 1986.

[Gla64] A.W. Gladkij. On the complexity of phrase structure grammars. Algebri i Logika Sem., 3:29–44, 1964. In Russian.

[HIM78] Juris Hartmanis, Neil Immerman, and Stephen R. Mahaney. One-way log-tape reductions. In Proc. of 19th FOCS, pages 65–71, 1978.

[HU79] John E. Hopcroft and Jeffrey D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979.

[JMP93] Petr Janc̆ar, Frantis̆ek Mráz, and Martin Plátek. A taxonomy of forgetting automata. In Proc. of 18th MFCS, volume ??? of LNCS, pages 527–536. Springer, 1993.

[Lan93] Klaus-Jörn Lange. Complexity and structure in formal language theory. In Proc. of 8th Structure in Complexity Theory, pages 224–238. IEEE, 1993.

[Lau88] Clemens Lautemann. One pushdown and a small tape. In Klaus W. Wagner, editor, Dirk Siefkes zum 50. Geburtstag, pages 42–47. TU Berlin and Universität Augsburg, 1988.

[Lor93] Krzysztof Loryś. Personal communication, 1993.

[Mag69] George Mager. Writing pushdown acceptors. JCSS, 3:233–247, 1969.

[Sal73] Arto K. Salomaa. Formal Languages. Academic Press, 1973.

[Smu61] Raymond M. Smullyan. Theory of formal systems, volume 47 of Annals of Mathematical Studies. Princeton University Press, Princeton, New Jersey, 1961.

[Sud78] Ivan H. Sudborough. On the tape complexity of deterministic context–free languages. Journal of the ACM, 25(3):405–414, 1978.

[WW86] Klaus Wagner and Gerd Wechsung. Computational Complexity. Reidel Verlag, Dordrecht and VEB Deutscher Verlag der Wissenschaften, 1986.