We study descriptional complexity of push down automata (PDA) accepting regular languages and context free languages. We have shown that the number of states of a PDA accepting a regular language can be smaller than that of a corresponding finite state automaton by utilizing stack symbols. No complexity function having desirable properties and combining the number of states and the number of stack symbols exists. We therefore study the number of stack symbols complexity in the family of one state PDA and the state complexity in the family of PDA using at most two stack symbols. We exhibit two infinite sequences of regular languages and prove tight bounds on their complexity using the above families of PDA. We also prove upper and lower bounds on the complexity of sequences of contextfree languages and analyze the impact of the mode of acceptance.
Although measuring complexity of problem solution
by time and space requirements is most frequently
used, the descriptional complexity is achieving more
interest in recent decades. The complexity of a
problem (given by a language L) solution is measured by
a complexity of a device (e.g., an automaton)
defining L. Measuring complexity of finite automata by
the number of states dates back to the early days
of automata theory. Majority of descriptional
complexity of automata research concerns finite automata
(see, e.g., survey papers [
The number of states was a natural descriptional complexity measure for finite state automata (FSA). In case of PDA there are two measures at hand – the number of states measure and the number of stack *This research has been supported in part by the grant 1/0601/20 of the Slovak Scientific Grant Agency VEGA.
Copyright ©2020 for this paper by its authors. Use
permitted under Creative Commons License Attribution 4.0 International
(CC BY 4.0).
symbols measure. Both states and stack symbols
are depended on each other. Goldstine, Price and
Wotschke showed that there exists a transformation
for any PDA using n states and p stack symbols to an
equivalent PDA reducing the number of states to any
desired number n0 1 [
In this paper, we study descriptional complexity of
PDA accepting regular and context-free languages.
We exhibit some infinite sequences of languages
allowing us to prove some lower and upper bounds on
their descriptional complexity using the above
subfamilies of PDA. We also show that acceptance mode
can have impact on the descriptional complexity. The
results presented are based on the Master Thesis of
Lukáš Kiss [
We shall assume basic knowledge and notation in formal languages theory. We mention some of the notation we shall use. The length of a word w is denoted by jwj. We use e to denote the empty word. The cardinality of a set S is denoted by jSj. A nondeterministic push down automaton (PDA) is a 7-tuple A = (Q; S; G; d ; q0; Z0; F) with the usual meaning of its components. Note that a PDA can in one computation step replace the top of the stack symbol by a word. Moreover, the PDA cannot move with the empty stack. The language accepted by a PDA A accepting by empty stack is denoted by N(A) and the language accepted by a PDA A accepting by final state is denoted by L(A). The family of contextfree languages is denoted by LCF . We shall also use the operation shuffle. Given an alphabet S, the Shuffle of two languages L1; L2 S is Shu f (L1; L2) = fwj9n 2 N; u1; : : : ; un; v1; : : : ; vn 2 S ; such that w = u1v1u2v2 : : : unvn ^ u1 : : : un 2 L1 ^ v1 : : : vn 2 L2g.
In case of finite automata, the number of states is the
most natural and mostly used descriptional
complexity measure. In case of push-down automata (PDA)
the size of the stack alphabet is another important
parameter. It is known ([
Let us consider some subfamilies of push-down automata.
Notation 1. PDA(n; p) is the family of push down automata using at most n states and at most p stack symbols.
Since there is no function on pairs (n; p) assigning the same complexity to two minimal automata for the same language, we shall concentrate on the following two ’extreme’ subfamilies of PDA defining the whole family of context-free languages: • PDA(1; p) - the subfamily of one state PDA using the number of stack symbols to measure the complexity. • PDA(n; 2) - the subfamily of all PDA using at most two stack symbols, measuring complexity by the number of states.
For each of these subfamilies of PDA, we define a minimal complexity of a given context-free language L as follows: Definition 1. Let L be a context-free language. The stack symbol complexity of L, denoted by Gc(L), is the smallest number of stack symbols of any A in PDA(1; p) that accepts L.
Definition 2. Let L be a context-free language. The state complexity of L, denoted by Qc(L), is the smallest number of states of any A in PDA(n; 2) that accepts L.
In what follows, we shall use constructions and
results on reducing the number of stack symbols by
increasing the number of states in [
1Preserving the natural partial order on pairs (n; p) based on component wise comparison and assigning the same value to pairs (n1; p1) and (n2; p2) corresponding to two minimal PDA’s for the same language.
We shall first consider PDA on regular languages. We shall consider the question whether and to what extent the number of states of a finite state automaton (FSA) can be reduced by using stack with stack alphabet of certain size. We shall consider this question for both acceptance modes of PDA. Next, we shall prove some lower bounds for PDA in the two particular subfamilies of PDA mentioned above. 3.1
Given an arbitrary finite state automaton, we shall construct an equivalent push down automaton with fewer states. It is easy to see that by allowing any number of stack symbols it is possible to have a one state PDA. Suppose, we allow a particular number of stack symbols. How much can the number of states of an equivalent PDA be reduced compared to the number of states of a given finite state automaton? Theorem 1. For any n state FSA A1 there exists a n PDA A2 with d p e states and p stack symbols such that N(A2) = L(A1) Proof. The push down automaton represents each state of the finite state automaton A1 by a coding consisting of a state and a stack symbol on the top of the stack. The stack of A2 shall contain at most one symbol. Each transition of the automaton A1 from a state q to s is represented by a corresponding change of the state and the top stack symbol in the automaton A2. Each accepting state of A1 has also a corresponding coding s and Z. For each such coding corresponding to some accepting state of A1 can A2, in addition to the simulation of a step of A1, nondeterministically decide to pop this stack symbol and thus empty its stack. If the stack is emptied before the automaton A2 has finished processing the input word, A2 shall halt, otherwise A2 accepts the input word if and only if the automaton A1 accepts.
The construction in the proof of Theorem 1 can be easily modified for acceptance by accepting state. It suffices to replace the possibility of popping the stack by a transition to a new accepting state. We thus have the following lemma.
Lemma 1. For each n state FSA A1 there exists a n PDA A2 with d p e + 1 states and p stack symbols such that L(A2) = L(A1)
This upper bound construction introduces one more state, the accepting state, compared to the previous upper bound construction, but not in all cases the additional accepting state is necessary 2. The
question of necessity of the new state for a language is by itself an interesting independent problem.
It may seem that there is no significant impact of the choice of the accepting mode. By considering some lower bounds in the next subsection we shall see that this is not necessarily a case. 3.2
In this subsection, we shall consider lower bounds on the complexity of particular regular languages considering PDA in the two above mentioned subfamilies of PDA, namely PDA(1; p) and PDA(n; 2). We shall show that for the empty stack acceptance the upper bound construction in the proof of Theorem 1 is optimal for one state PDA.
We shall now introduce two particular sequences of regular languages to be used in our lower bound proofs.
Notation 2. Let a1; : : : ; an be distinct symbols for any n 1. Let • L1[n] = a1a2 : : : an • L2[n] = fak1njk
0g
It is easy to see that the state complexity for both L1[n] and L2[n] on finite state automata is n.
We shall show that the stack symbols complexity of L1[n] on one state PDA is n.
Theorem 2. Gc(L1[n]) = n; 8n 2 N.
Proof. We shall show that Gc(L1[n]) n by constructing a push-down automaton An. The automaton An uses the top stack symbol Zi as a "state". Its stack will contain at most one symbol. If Zi is on the top of the stack, the automaton knows that it already has processed all input symbols a1; : : : ; ai 1. The automaton can pop the top stack symbol at any time and empty its stack.
We shall prove Gc(L1[n]) n by contradiction.
Let An in PDA(1; p) be an automaton accepting the language L1[n] for p < n. By the pigeon hole principle, there exist two input symbols ai and a j such that i < j, on which the automaton An does a computation step on the same stack symbol Z during an accepting computation on a word w = a1m1 a2m2 : : : anmn for m1; : : : ; mn 2p.
Suppose the automaton An during an accepting computation on w pushes gi on the input symbol ai and g j on the input symbol a j, having the stack symbol Z on the top of the stack in each case. The automaton An accepts the word w by empty stack. Therefore, there exist some sequences of symbols ui and u j, on which An removes gi and g j from the stack3.
Let k; 1 k m j, be such that the automaton An has the stack symbol Z on the top of the stack after processing am1 a2m2 : : : aimi : : : akj. Using the accepting 1 computation of An on w we shall modify w and the accepting computation so that an accepting computation on a word not in L1[n] is obtained. Following am1 a2m2 : : : aimi : : : akj the automaton An can read the in1 put symbol ai and replace the stack symbol Z on the top by gi. Now, the word ui can follow on the input. After processing this next part of the input word, ui, the automaton can remove the gi and leave a word g f in4 on the stack. Note that g f in also appears on the stack during the accepting computation of An on w. Thus there exists some word v, on which the automaton An removes g f in from the stack and accepts the word w by empty stack. Therefore An also accepts wˆ = a1m1 a2m2 : : : aimi : : : akjaiuiv 2= L1[n].
We could use the upper bound construction in the proof of Theorem 1 on the minimal finite state automaton for the language5 L2[n]. However, this does not result in a minimal push down automaton in our complexity measures. Instead of using the combination of a state and a top stack symbol to represent the state of the minimal FSA, the minimal push down automaton uses its stack as a counter.
Before we present the construction and the proof, we shall prove that no push down automaton with one state and one stack symbol can accept L2[n] for 6 n 2.
Lemma 2. There does not exist a PDA using one state and one stack symbol accepting L2[n]; n 2. Proof. By contradiction, let there exist a push down automaton A using one state q and one stack symbol Z0 accepting L2[n]; n 2. We know that A must use the empty stack acceptance mode. Therefore, A has to pop Z0 from the stack on the input symbol a1 or e.
If A pops Z0 on the input symbol a1 then A accepts the word a1 2= L2[n] for any n 2.
If A pops Z0 on e and pushes on a1 a word g 2 Z0 on the stack then A accepts the word a1 2= L2[n] for any n 2.
Now, we are ready to prove matching upper and lower bounds for the language L2[n].
3If gi = e then ui = e 4Where g finZ was the content of the stack after processing a1m1 a52mT2h:e: :maimini i: m::aalkjfi.nite state automaton requires exactly n states.
6A finite state automaton using one state can accept L = fa1g = L2[n], for n = 1.
Theorem 3. Gc(L2[n]) = 2, for any n 2.
Proof. We shall prove that Gc(L2[n]) 2 by constructing A in PDA(1; 2) accepting the language L2[n].
The automaton uses the bottom of stack symbol Z0 to indicate the starting point of a block and Z1 as a representation of a1 in the stack. On Z0 it can nondeterministically decide to start processing a next block of n symbols a1 on the input or empty the stack. The automaton pushes n sized block of Z1 on the stack and for each a1 it pops Z1 from the stack until it reaches the symbol Z0. Then the process repeats.
The fact that Gc(L2[n]) 2 has been already shown in the Lemma 2.
Moreover, the construction in the proof of this theorem gives state complexity of each L2[n] when considering PDA in PDA(n; 2).
Corollary 1. Qc(L2[n]) = 1, for any n 1.
The previous construction results in a minimal push down automaton that accepts L2[n] by empty stack. The question arises, how many states are used by a minimal push down automaton using two stack symbols accepting the language L2[n] by final state? Clearly, it can not be one state. Therefore, the minimal PDA needs at least two states. The next theorem shows that two states are not only necessary, but also sufficient for two stack symbols PDA accepting L2[n] by accepting state.
Theorem 4. Let A be a push down automaton using two stack symbols accepting the language L2[n]; n 2. Then two states are necessary and sufficient to accept L2[n] by final state.
Proof. We first show that two states are sufficient to accept the language L2[n] by final state by constructing a PDA A. The construction of the minimal PDA is similar to that in the proof of the Theorem 3. Instead of popping nondeterministically the symbol Z0 from the stack and then accepting by empty stack, this automaton can move nondeterministically to the new accepting state.
We now show (by contradiction) that two states are necessary to accept the language L2[n] by final state using just 2 stack symbols. Let us assume that an automaton A using one state and two stack symbols exists. Hence, it has just one state, then this state has to be the accepting state. Since this automaton accepts the word an1, it has some transitions on a1. Therefore, the automaton also accepts the word a1 2= L2[n]. 3.3
In the previous part, we proved that any push down automaton in PDA(1; p) needs at least two stack symbols to accept the language L2[n] for n 2. Let us study one stack symbol PDA accepting the language L2[n], i.e., the PDA in PDA(n; 1). We shall show that there exists a minimal PDA using one stack symbol and two states accepting the language L2[n] by empty stack and a minimal PDA using one stack symbol and n states accepting the same language by final state.
We can conclude that the type of acceptance mode does have an effect on the complexity of a minimal PDA for a given language.
Let us consider push down automata using one stack
symbol and accepting by empty stack. In this setup,
we can construct a sequence of PDA A1; A2; : : : for
the sequence of languages L2[
Theorem 5. Let n 2. The minimal automaton An 2 PDA(n; 1) accepting the language L2[n] by empty stack has two states.
Proof. The automaton An guesses the number of blocks of length n in the initial state q0 by pushing blocks of the stack symbol Z0 on the stack in e moves. It can nondeterministically move to the second state q1 in which it compares the number of stack symbols in the stack to the number of symbols a1 on the input. Note that, the automaton pushes only n 1 symbols on the top of the stack when it changes state.
By Lemma 2, the automaton accepting L2[n], n 2 using one state and one stack symbol does not exists. Therefore, the automaton An is minimal.
Finally, we focus on the push down automata using one stack symbol accepting by final state. Even though, the previous automata had just one stack symbol, we were able to construct a sequence of automata accepting the languages L2[n] each using two states only. Let us show that this is not the case for automata using one stack symbol and accepting by final state.
Theorem 6. Let n 2. The minimal automaton An 2 PDA(n; 1) accepting the language L2[n] by accepting state has n states.
Proof. To show the upper bound, i.e., that n states are enough it suffices to consider the push down automaton which behaves in the same way as the finite state automaton accepting L2[n], ignoring the stack entirely.
We shall show (by contradiction) that the number of states has to be at least n. Let A be a push down automaton using one stack symbol and n 1 states accepting the language L2[n]. Thus A accepts w = am, 1 n divides m, for some m 2n. During the accepting computation of the automaton A on the input word w some state q will repeat.
Consider the part of the computation between the two occurrences of the state q where some number j, 1 j n 1 of symbols a1 was read. Suppose the size of the stack was not increased during this part of the computation. By leaving out this part of the computation we clearly obtain an accepting computation on the word w0 = a1m j 2= L2[n]. Similarly, in case the size of the stack was increased during this part of the computation, by repeating this part of the computation we clearly obtain an accepting computation on the word w” = am+ j 2= L2[n]. (Note that by consid1 ering the two cases we ensured that the computation on the modified word does not block because of the empty stack.) 4
In this section, we shall analyze complexity of (nonregular) context free languages using both subfamilies of PDA considered. In PDA(1; p), we shall show lower and upper bounds for a particular sequence of languages and in PDA(n; 2), we shall analyze the relation of complexities for the two modes of acceptance. Furthermore we shall show some upper bounds for a particular sequence of langauges. 4.1
Let us consider the following sequence of context free languages.
Notation 3. Let a1; : : : ; ap; b1; : : : ; bp be distinct symbols for any p 1. Let
Sp = fa1; : : : ; ap; b1; : : : ; bpg
Lp = fw(h(w))Rjw 2 fa1; a2; : : : ; apg g where h is the homomorphism defined by h(ai) = bi, for each i, 1 i p.
We can easily see that any PDA using one state has to use empty stack acceptance mode to accept the language Lp. This shows that the empty stack acceptance mode and the final state acceptance mode do not have the same power in PDA(1; p).
Our intention is to prove that the number of stack symbols complexity of the language Lp for one state PDA is exactly p + 1. To prove the lower bound, we shall first prove several lemmas. Each lemma exhibits a property, each push down automaton accepting Lp has to have.
Lemma 3. Let A in PDA(1; i) be an automaton accepting the language Lp, where p; i 2 N. Let x 2 Sp be an input symbol. Then in each accepting computation on w 2 Lp, w = ux jv; j 1; u; v 2 Sp, A has to modify the stack while reading x.
Proof. Let x 2 Sp be a symbol, which does not modify the stack in an accepting computation and let A accept w = ux jv 2 Lp; j 1; u; v 2 Sp. Then A also accepts wˆ = ux j+1v 2= Lp.
Lemma 4. Let A in PDA(1; p) be a minimal automaton accepting the language Lp, where p 2 N. Then 8i; 1 i p 9Z 2 G such that (q0; e) 2 d (q0; bi; Z). Proof. Let us consider words w1 = amb1m; : : : ; wp = 1 amb1m in Lp for sufficiently large m. Note that the 1 size of the stack after reading the a-part of the words cannot be bounded. (Otherwise, for sufficiently large m some stack content would repeat. Leaving out this part of the input and computation would lead to an accepting computation on a word with smaller number of a’s and unchanged number of b’s.) Thus, after reading the a-part of the words w1; : : : ; wp the stack will contain some (large) word in G+ which the next part of the accepting computation has to remove while reading the b-part of the word.7
Now, suppose that to the contrary of the statement of lemma there exists some bk such that A does not pop any stack symbol from the stack on bk. Formally, 8Z 2 G it holds that (q0; e) 2= d (q0; bk; Z).
Let us analyze the accepting computation on the word wk. Since A has to empty the stack while reading the b-part of wk and cannot pop the stack symbols while reading bk, the symbols on the stack have to be removed in e-transitions. Thus there are at least two distinct symbols Z1 used in the bk transition and Z2 used in the e-transition in G used in the b-part of the accepting computation on wk. (Having these symbols equal would enable accepting computation on a word with fewer bk’s.) Neither of these symbols can be popped from the stack by some bi, i 6= k since this would allow to modify accepting computations on the words w1; : : : ; wp to accepting computations on words not in Lp. (A detailed analysis of the accepting computations on the words the words w1; : : : ; wp shows that p symbols are not enough when bk cannot pop any symbol in G.) Lemma 5. Let A in PDA(1; p) be an automaton accepting the language Lp, where p 2 N. Suppose (q0; e) 2 d (qo; bi; Z) and (q0; e) 2 d (qo; b j; Zˆ ) for i 6= j. Then Z 6= Zˆ .
Proof. Suppose that one state push down automaton A accepting the language Lp pops on bi and b j the same stack symbol Z from the stack and let A accepts w = aimbim. Then A accepts wˆ = aimb mj 2= Lp.
Combining the previous lemmas 4 and 5, we can infer that one state push down automaton needs at least p stack symbols to accept Lp. The next theorem shows that in fact p + 1 stack symbols are required.
Before we show the proof of a lower bound and construct an upper bound, we shall infer some properties about the d function from the previous lemmas. Corollary 2. Let A = (fq0g; fa1; : : : ; ap; b1; : : : ; bpg; fZ1; Z2; : : : ; Zpg; d ; q0; Zi; 0/ ) in PDA(1; p) be an automaton accepting by empty stack the language Lp, where p 2 N. Then there exists some permutation s on f1; : : : ; pg, such that (q0; e) 2 d (q0; bi; Zs(i)), where Zi is a stack symbol used by the automaton A.
We are now ready to present the complexity of the languages Lp.
Theorem 7. Gc(Lp) = p + 1, 8p 2 N Proof. We shall show that Gc(Lp) p + 1 by constructing an automaton A in PDA(1; p + 1) accepting Lp by empty stack.
The automaton pushes on each input symbol ai the stack symbol Zi onto the stack. The automaton pops the Zi from the stack on the input symbol bi. The initial stack symbol is Z0 and is kept on the top of the stack while reading ai symbols. On any input symbol ai, it can nondeterministically change the top stack symbol to Zi instead of pushing the new Zi onto the stack. This moves the push down automaton to the next phase. In this phase it is comparing the reverse order of b symbols to a symbols by popping Z symbols from the stack. At the end of computation, the push down automaton A accepts by empty stack.
We shall prove Gc(Lp) p + 1 by contradiction.
Let A in PDA(1; p) be an automaton accepting the language Lp and let Zi be the initial stack symbol. By corollary (2): there exists some permutation s on f1; : : : ; pg, such that (q0; e) 2 d (q0; bi; Zs(i)). Then A accepts w = bs(i) 2= Lp.
note that this theorem shows that the number of stack symbols complexity hierarchy of one state PDA is not bounded. 4.2
We shall now discuss the influence of the acceptance mode on the complexity. The family of one state PDA was forced to use the empty stack acceptance mode since the final state acceptance mode could only be used for specific languages. The influence of the acceptance mode on the complexity thus was not an issue.
The family PDA(n; 2) of automata allows both types
of acceptance mode, empty stack or final state. Any
one of them can be used to accept arbitrary context
free language. It is known ([
Let us consider the influence of these two
acceptance modes on the complexity. We can not use
the standard constructions[
The new automaton has fewer stack symbols, each stack symbol Z is represented by a string h(Z). Naturally this increases the number of states. In our construction, let A in PDA(s; 3) be an automaton using stack symbols H1; H2; H3. We construct an equivalent automaton B using two stack symbols Z0; Z1. Each stack symbol Hi is represented in B by a string h(Hi) of symbols Z0 and Z1. The states of B are pairs of the form [q; g], where q is a state of A and g is a proper prefix8 of h(Hi). The idea is that the automaton B reads the encoded stack symbol from the stack and saves it to the current state. Then the automaton B does the same computation as A. For the mapping h, we have chosen: • h(H1) = Z1 • h(H2) = Z0Z0 • h(H3) = Z1Z0
q
PDA A
Stack : : : H j p : : : H j1 : : : H jk PDA B
Stack : : : Zi1 : : : Zis | h({Hzj) }
[q; e] [q; Zis : : : Zi2 ] : : : Zi1 [p; e] : : : Z f1 : : : Z fn | {z } h(Hj1 ):::h(Hjk )
Finally, the accepting states of B shall be all states [q; e], where q is an accepting state of A. The last item 8The string x is a proper prefix of xy if y 6= e. to specify is the initial stack symbol of B. Without loss of generality, we can assume that H1 is the initial stack symbol of A. Otherwise, we can rename the stack symbols of A.
We shall now describe our construction.
Lemma 6. Let A in PDA(s; 3) be an automaton. Then there exists a push down automaton B using two stack symbols and 2s states such that L(B) = L(A). Proof. The construction uses the h function as an encoding function for stack symbols of the automaton A to stack symbols of the automaton B. Then B simulates the automaton A by decoding the encoded stack symbols from the stack. If Z1 is on the top of the stack and the automaton is in the state [q; e] then it can simulate the step of the automaton A in the state q and H1 as the top stack symbol. On the other hand, if the top stack symbol is Z0 and it is in the state [q; e] then the automaton B needs to read one more stack symbol from the stack. So it saves the symbol read in the state. Then it reads the next stack symbol in the state [q; Z0] and simulates a computation step of A.
Let us now present the construction from the empty stack acceptance mode to the final state acceptance mode. We omit a formal description of the transformation since it is straightforward.
Theorem 8. Given a push down automaton A using two stack symbols and s states, there exists a push down automaton B using two stack symbols and 2s + 2 states such that L(B) = N(A).
Proof. Let us use a general construction (see, e.g.,
[
In order to replace the final state acceptance by the empty stack acceptance we need a lemma similar to Lemma 6 dealing with the empty stack acceptance mode.
Lemma 7. Let A in PDA(s; 3) be an automaton. Then there exists a push down automaton B using 2 stack symbols and 2s states such that N(B) = N(A). Proof. The automaton B shall have the states: Qb = Qa fe; Z0g and we shall use the same encoding9 h. Using the reduction and mapping h, we construct the dB transition function of B similarly as in the proof of Lemma 6. The automaton B uses two stack symbols and 2s states and N(B) = N(A).
Now, we are ready to present the construction from the final state acceptance mode to the empty stack acceptance mode.
9h(H1) = Z1; h(H2) = Z0Z0; h(H3) = Z1Z0 Theorem 9. Given a push down automaton A using two stack symbols and s states, there exists a push down automaton B using two stack symbols and 2s + 2 states such that N(B) = L(A).
Proof. Let us use a general construction (see, e.g.,
[
Upper bounds Let us consider the following sequence of context free languages.
Notation 4. Let a; b; c be distinct symbols. Let S = fa; b; cg. For each r 1 let • L = fw = ambmjm • L3[n] = fcmj0 m 1g ng • L4[n] = Shu f (L; L3[n])
At first, let us discuss the properties of the language L. Note that the language L coincides and thus has the same properties as the language Lp (defined in the Section 4.1), for p = 1. We proved that one state automaton needs at least two stack symbols to accept Lp; p = 1. Then using the general idea from Theorem 7, we can construct the minimal one state PDA accepting L.
We shall now modify the language L in order to "force" the PDA to check some additional property. Both stack symbols are used for keeping track of symbols a and b. Adding another property to this language should result in increasing the number of states. The property we shall use is the language L3[n], the number of c symbols should be equal or less then n. Mixing properties of L and L3[n] languages results in the language L4[n]
Finally, we should decide, which acceptance mode we shall use. Let us use the same acceptance mode as in the previous Section 4.1, empty stack acceptance mode. This results in an easier upper bound construction.
Our automaton has n + 1 states. Each state represents the number of c symbols read. If the automaton reads the (n + 1)st symbol c it blocks.
Theorem 10. There exists a PDA An using two stack symbols and n + 1 states such that N(An) = L4[n]. Proof. We shall construct a PDA An = (fq0; : : : ; qng; fa; b; cg; fZ1; Z2g; dr; q0; Z2; 0/ ) The stack symbol Z1 is used as a counter. On input symbol a, the automaton pushes Z1 on the stack and it keeps the stack symbol Z2 on the top. The automaton keeps Z2 on the top of the stack. This indicates An is still reading the part of the input containing the a symbols. The automaton An can nondeterministically pop Z2 on e and start to pop Z1 on each b. On symbol c, the automaton changes the state from qi to qi+1. In case An is in the state qn and reads the input symbol c, it blocks. 5
Since no function combining the number of states
and the number of stack symbols of PDA to a
descriptional complexity measure having desirable
properties exists, we studied complexity in two
’extreme’ sub classes of PDA each able to define all
context-free languages. It would be natural to study
behaviour of complexity when operations on
languages are performed (some upper bounds appear in
[