=Paper= {{Paper |id=Vol-2718/paper25 |storemode=property |title=Descriptional Complexity of Push Down Automata |pdfUrl=https://ceur-ws.org/Vol-2718/paper25.pdf |volume=Vol-2718 |authors=Lukáš Kiss,Branislav Rovan |dblpUrl=https://dblp.org/rec/conf/itat/KissR20 }} ==Descriptional Complexity of Push Down Automata== https://ceur-ws.org/Vol-2718/paper25.pdf

Descriptional complexity of push down automata*

Lukáš Kiss and Branislav Rovan

Comenius University in Bratislava,
Faculty of Mathematics, Physics and Informatics

Abstract: We study descriptional complexity of push symbols measure. Both states and stack symbols
down automata (PDA) accepting regular languages are depended on each other. Goldstine, Price and
and context free languages. We have shown that the Wotschke showed that there exists a transformation
number of states of a PDA accepting a regular lan- for any PDA using n states and p stack symbols to an
guage can be smaller than that of a corresponding equivalent PDA reducing the number of states to any
finite state automaton by utilizing stack symbols. No desired number n0 ≥ 1 [4] by increasing the number
complexity function having desirable properties and of stack symbols. No complexity measure for PDA
combining the number of states and the number of having desirable properties and combining the num-
stack symbols exists. We therefore study the num- ber of states and the number of stack symbols exists.
ber of stack symbols complexity in the family of one Therefore, we consider two subfamilies of PDA, one
state PDA and the state complexity in the family of state PDA and max two stack symbols PDA. Note that
PDA using at most two stack symbols. We exhibit each of them defines the whole family of context-free
two infinite sequences of regular languages and prove languages. In the one state PDA subfamily, we fix the
tight bounds on their complexity using the above number of states to one and use the number of stack
families of PDA. We also prove upper and lower symbols as the measure. In the second subfamily, we
bounds on the complexity of sequences of context- fix the number of stack symbols to at most two and
free languages and analyze the impact of the mode measure the number of states.
of acceptance. In this paper, we study descriptional complexity of
PDA accepting regular and context-free languages.
We exhibit some infinite sequences of languages al-
Introduction lowing us to prove some lower and upper bounds on
their descriptional complexity using the above sub-
Although measuring complexity of problem solution
families of PDA. We also show that acceptance mode
by time and space requirements is most frequently
can have impact on the descriptional complexity. The
used, the descriptional complexity is achieving more
results presented are based on the Master Thesis of
interest in recent decades. The complexity of a prob-
Lukáš Kiss [10].
lem (given by a language L) solution is measured by
a complexity of a device (e.g., an automaton) defin-
ing L. Measuring complexity of finite automata by
the number of states dates back to the early days 1 Preliminaries and Notation
of automata theory. Majority of descriptional com-
plexity of automata research concerns finite automata
(see, e.g., survey papers [1], [2], [3]). The descrip- We shall assume basic knowledge and notation in
tional complexity of PDA was addressed by Gold- formal languages theory. We mention some of the
stine at al.[4] and [5] where relation of the number notation we shall use. The length of a word w is de-
of states and the number of stack symbols was stud- noted by |w|. We use ε to denote the empty word.
ied. Later particular types of PDA were considered The cardinality of a set S is denoted by |S|. A nonde-
(see, e.g., surveys [6], [7]) In connection to the re- terministic push down automaton (PDA) is a 7-tuple
search on usefulness of information (see, e.g., Rovan A = (Q, Σ, Γ, δ , q0 , Z0 , F) with the usual meaning of
and Sadovsky [8]) measuring complexity of PDA as its components. Note that a PDA can in one com-
a more powerful model became important (see the putation step replace the top of the stack symbol by
deterministic PDA case in Labáth and Rovan [9]). a word. Moreover, the PDA cannot move with the
The number of states was a natural descriptional empty stack. The language accepted by a PDA A
complexity measure for finite state automata (FSA). accepting by empty stack is denoted by N(A) and
In case of PDA there are two measures at hand – the the language accepted by a PDA A accepting by fi-
number of states measure and the number of stack nal state is denoted by L(A). The family of context-
free languages is denoted by LCF . We shall also use
* This research has been supported in part by the grant
the operation shuffle. Given an alphabet Σ, the Shuf-
1/0601/20 of the Slovak Scientific Grant Agency VEGA.
Copyright ©2020 for this paper by its authors. Use permit-
fle of two languages L1 , L2 ⊆ Σ∗ is Shu f (L1 , L2 ) =
ted under Creative Commons License Attribution 4.0 International {w|∃n ∈ N, u1 , . . . , un , v1 , . . . , vn ∈ Σ∗ ; such that w =
(CC BY 4.0). u1 v1 u2 v2 . . . un vn ∧ u1 . . . un ∈ L1 ∧ v1 . . . vn ∈ L2 }.
2 Descriptional Complexity of PDA 3 Push Down Automata on Regular
Languages
In case of finite automata, the number of states is the
most natural and mostly used descriptional complex-
We shall first consider PDA on regular languages.
ity measure. In case of push-down automata (PDA)
We shall consider the question whether and to what
the size of the stack alphabet is another important
extent the number of states of a finite state automa-
parameter. It is known ([4], [5]) that it is possible
ton (FSA) can be reduced by using stack with stack
to reduce the number of stack symbols by increas-
alphabet of certain size. We shall consider this ques-
ing the number of states and vice versa. It is also
tion for both acceptance modes of PDA. Next, we
known (see, e.g., [11]) that one state suffices to define
shall prove some lower bounds for PDA in the two
any context-free language and similarly two stack
particular subfamilies of PDA mentioned above.
symbols suffice to define any context-free language.
Thus it is natural to look for a descriptional complex-
ity measure for PDA that would "combine" the two 3.1 Saving States by Adding Stack
parameters – the number of states n and the number
of stack symbols (the size of the stack alphabet) p. Given an arbitrary finite state automaton, we shall
Just like in the case of deterministic PDA [9] it can construct an equivalent push down automaton with
be shown that a function assigning natural numbers fewer states. It is easy to see that by allowing any
to pairs (n, p) and having some desirable properties 1 number of stack symbols it is possible to have a one
does not exist. state PDA. Suppose, we allow a particular number of
Let us consider some subfamilies of push-down stack symbols. How much can the number of states
automata. of an equivalent PDA be reduced compared to the
number of states of a given finite state automaton?
Notation 1. PDA(n, p) is the family of push down
automata using at most n states and at most p stack Theorem 1. For any n state FSA A1 there exists a
symbols. PDA A2 with d np e states and p stack symbols such
Since there is no function on pairs (n, p) assigning that N(A2 ) = L(A1 )
the same complexity to two minimal automata for the Proof. The push down automaton represents each
same language, we shall concentrate on the following state of the finite state automaton A1 by a coding con-
two ’extreme’ subfamilies of PDA defining the whole sisting of a state and a stack symbol on the top of the
family of context-free languages: stack. The stack of A2 shall contain at most one sym-
• PDA(1, p) - the subfamily of one state PDA us- bol. Each transition of the automaton A1 from a state
ing the number of stack symbols to measure the q to s is represented by a corresponding change of the
complexity. state and the top stack symbol in the automaton A2 .
Each accepting state of A1 has also a corresponding
• PDA(n, 2) - the subfamily of all PDA using at coding s and Z. For each such coding corresponding
most two stack symbols, measuring complexity to some accepting state of A1 can A2 , in addition to
by the number of states. the simulation of a step of A1 , nondeterministically
For each of these subfamilies of PDA, we define a decide to pop this stack symbol and thus empty its
minimal complexity of a given context-free language stack. If the stack is emptied before the automaton
L as follows: A2 has finished processing the input word, A2 shall
halt, otherwise A2 accepts the input word if and only
Definition 1. Let L be a context-free language. The
if the automaton A1 accepts.
stack symbol complexity of L, denoted by Γc(L), is
the smallest number of stack symbols of any A in The construction in the proof of Theorem 1 can be
PDA(1, p) that accepts L. easily modified for acceptance by accepting state. It
Definition 2. Let L be a context-free language. The suffices to replace the possibility of popping the stack
state complexity of L, denoted by Qc(L), is the small- by a transition to a new accepting state. We thus have
est number of states of any A in PDA(n, 2) that ac- the following lemma.
cepts L.
Lemma 1. For each n state FSA A1 there exists a
In what follows, we shall use constructions and re- PDA A2 with d np e + 1 states and p stack symbols such
sults on reducing the number of stack symbols by in- that L(A2 ) = L(A1 )
creasing the number of states in [5] and on reduc-
ing the number of states by increasing the number of This upper bound construction introduces one
stack symbols in [4]. more state, the accepting state, compared to the pre-
1 Preserving the natural partial order on pairs (n, p) based on vious upper bound construction, but not in all cases
component wise comparison and assigning the same value to pairs the additional accepting state is necessary 2 . The
(n1 , p1 ) and (n2 , p2 ) corresponding to two minimal PDA’s for the
same language. 2 Consider, e.g., the languages Σ∗ or 0.
/
question of necessity of the new state for a language Therefore, there exist some sequences of symbols
is by itself an interesting independent problem. ui and u j , on which An removes γi and γ j from the
It may seem that there is no significant impact of stack3 .
the choice of the accepting mode. By considering Let k, 1 ≤ k ≤ m j , be such that the automaton An
some lower bounds in the next subsection we shall has the stack symbol Z on the top of the stack after
see that this is not necessarily a case. processing am 1 m2 mi k
1 a2 . . . ai . . . a j . Using the accepting
computation of An on w we shall modify w and the
accepting computation so that an accepting compu-
3.2 Lower Bounds for PDA on Regular
tation on a word not in L1 [n] is obtained. Following
Languages
am 1 m2 mi k
1 a2 . . . ai . . . a j the automaton An can read the in-
In this subsection, we shall consider lower bounds on put symbol ai and replace the stack symbol Z on the
the complexity of particular regular languages con- top by γi . Now, the word ui can follow on the input.
sidering PDA in the two above mentioned subfami- After processing this next part of the input word, ui ,
lies of PDA, namely PDA(1, p) and PDA(n, 2). We the automaton can remove the γi and leave a word
shall show that for the empty stack acceptance the γ f in 4 on the stack. Note that γ f in also appears on the
upper bound construction in the proof of Theorem 1 stack during the accepting computation of An on w.
is optimal for one state PDA. Thus there exists some word v, on which the automa-
We shall now introduce two particular sequences ton An removes γ f in from the stack and accepts the
of regular languages to be used in our lower bound word w by empty stack. Therefore An also accepts
proofs. ŵ = am 1 m2 mi k
1 a2 . . . ai . . . a j ai ui v ∈
/ L1 [n].

Notation 2. Let a1 , . . . , an be distinct symbols for any
n ≥ 1. Let The complexity of L2 [n]
We could use the upper bound construction in the
• L1 [n] = a∗1 a∗2 . . . a∗n
proof of Theorem 1 on the minimal finite state au-
• L2 [n] = {akn
1 |k ≥ 0}
tomaton for the language5 L2 [n]. However, this does
not result in a minimal push down automaton in our
It is easy to see that the state complexity for both complexity measures. Instead of using the combina-
L1 [n] and L2 [n] on finite state automata is n. tion of a state and a top stack symbol to represent the
state of the minimal FSA, the minimal push down
The complexity of L1 [n] automaton uses its stack as a counter.
Before we present the construction and the proof,
We shall show that the stack symbols complexity of we shall prove that no push down automaton with
L1 [n] on one state PDA is n. one state and one stack symbol can accept L2 [n] for 6
n ≥ 2.
Theorem 2. Γc(L1 [n]) = n, ∀n ∈ N.
Lemma 2. There does not exist a PDA using one
Proof. We shall show that Γc(L1 [n]) ≤ n by con- state and one stack symbol accepting L2 [n], n ≥ 2.
structing a push-down automaton An . The automa-
ton An uses the top stack symbol Zi as a "state". Its Proof. By contradiction, let there exist a push down
stack will contain at most one symbol. If Zi is on the automaton A using one state q and one stack symbol
top of the stack, the automaton knows that it already Z0 accepting L2 [n], n ≥ 2. We know that A must use
has processed all input symbols a1 , . . . , ai−1 . The au- the empty stack acceptance mode. Therefore, A has
tomaton can pop the top stack symbol at any time and to pop Z0 from the stack on the input symbol a1 or ε.
empty its stack. If A pops Z0 on the input symbol a1 then A accepts
the word a1 ∈ / L2 [n] for any n ≥ 2.
We shall prove Γc(L1 [n]) ≥ n by contradiction. If A pops Z0 on ε and pushes on a1 a word
Let An in PDA(1, p) be an automaton accepting the γ ∈ Z0∗ on the stack then A accepts the word a1 ∈ /
language L1 [n] for p < n. By the pigeon hole prin- L2 [n] for any n ≥ 2.
ciple, there exist two input symbols ai and a j such
that i < j, on which the automaton An does a com-
Now, we are ready to prove matching upper and
putation step on the same stack symbol Z during an
lower bounds for the language L2 [n].
accepting computation on a word w = am 1 m2 mn
1 a2 . . . an
for m1 , . . . , mn ≥ 2p.
3 If γ = ε then u = ε
Suppose the automaton An during an accepting i i
4 Where γ Z was the content of the stack after processing
f in
computation on w pushes γi on the input symbol ai m m
a1 1 a2 2 . . . am i
i ...aj.
k
and γ j on the input symbol a j , having the stack sym- 5 The minimal finite state automaton requires exactly n states.
bol Z on the top of the stack in each case. The 6 A finite state automaton using one state can accept L =

automaton An accepts the word w by empty stack. {a1 }∗ = L2 [n], for n = 1.
Theorem 3. Γc(L2 [n]) = 2, for any n ≥ 2. study one stack symbol PDA accepting the language
L2 [n], i.e., the PDA in PDA(n, 1). We shall show that
Proof. We shall prove that Γc(L2 [n]) ≤ 2 by con- there exists a minimal PDA using one stack symbol
structing A in PDA(1, 2) accepting the language and two states accepting the language L2 [n] by empty
L2 [n]. stack and a minimal PDA using one stack symbol and
The automaton uses the bottom of stack symbol n states accepting the same language by final state.
Z0 to indicate the starting point of a block and Z1 as a We can conclude that the type of acceptance mode
representation of a1 in the stack. On Z0 it can nonde- does have an effect on the complexity of a minimal
terministically decide to start processing a next block PDA for a given language.
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 Accepting by empty stack
reaches the symbol Z0 . Then the process repeats.
Let us consider push down automata using one stack
The fact that Γc(L2 [n]) ≥ 2 has been already
symbol and accepting by empty stack. In this setup,
shown in the Lemma 2.
we can construct a sequence of PDA A1 , A2 , . . . for
Moreover, the construction in the proof of this the- the sequence of languages L2 [1], L2 [2], . . . such that
orem gives state complexity of each L2 [n] when con- each PDA shall use one stack symbol and two states.
sidering PDA in PDA(n, 2). We shall prove this in the next Theorem.

Corollary 1. Qc(L2 [n]) = 1, for any n ≥ 1. Theorem 5. Let n ≥ 2. The minimal automaton An ∈
PDA(n, 1) accepting the language L2 [n] by empty
The previous construction results in a minimal stack has two states.
push down automaton that accepts L2 [n] by empty
stack. The question arises, how many states are used Proof. The automaton An guesses the number of
by a minimal push down automaton using two stack blocks of length n in the initial state q0 by push-
symbols accepting the language L2 [n] by final state? ing blocks of the stack symbol Z0 on the stack in ε
Clearly, it can not be one state. Therefore, the mini- moves. It can nondeterministically move to the sec-
mal PDA needs at least two states. The next theorem ond state q1 in which it compares the number of stack
shows that two states are not only necessary, but also symbols in the stack to the number of symbols a1 on
sufficient for two stack symbols PDA accepting L2 [n] the input. Note that, the automaton pushes only n − 1
by accepting state. symbols on the top of the stack when it changes state.
By Lemma 2, the automaton accepting L2 [n], n ≥ 2
Theorem 4. Let A be a push down automaton using using one state and one stack symbol does not exists.
two stack symbols accepting the language L2 [n], n ≥ Therefore, the automaton An is minimal.
2. Then two states are necessary and sufficient to
accept L2 [n] by final state.
Accepting by state
Proof. We first show that two states are sufficient to
accept the language L2 [n] by final state by construct- Finally, we focus on the push down automata us-
ing a PDA A. The construction of the minimal PDA ing one stack symbol accepting by final state. Even
is similar to that in the proof of the Theorem 3. In- though, the previous automata had just one stack
stead of popping nondeterministically the symbol Z0 symbol, we were able to construct a sequence of au-
from the stack and then accepting by empty stack, tomata accepting the languages L2 [n] each using two
this automaton can move nondeterministically to the states only. Let us show that this is not the case for
new accepting state. automata using one stack symbol and accepting by
We now show (by contradiction) that two states are final state.
necessary to accept the language L2 [n] by final state Theorem 6. Let n ≥ 2. The minimal automaton An ∈
using just 2 stack symbols. Let us assume that an PDA(n, 1) accepting the language L2 [n] by accepting
automaton A using one state and two stack symbols state has n states.
exists. Hence, it has just one state, then this state
has to be the accepting state. Since this automaton Proof. To show the upper bound, i.e., that n states
accepts the word an1 , it has some transitions on a1 . are enough it suffices to consider the push down au-
Therefore, the automaton also accepts the word a1 ∈ / tomaton which behaves in the same way as the finite
L2 [n]. state automaton accepting L2 [n], ignoring the stack
entirely.
3.3 The complexity on one stack symbol PDA We shall show (by contradiction) that the number
of states has to be at least n. Let A be a push down
In the previous part, we proved that any push down automaton using one stack symbol and n − 1 states
automaton in PDA(1, p) needs at least two stack sym- accepting the language L2 [n]. Thus A accepts w = am
1,
bols to accept the language L2 [n] for n ≥ 2. Let us n divides m, for some m ≥ 2n. During the accepting
computation of the automaton A on the input word w Proof. Let x ∈ Σ p be a symbol, which does not mod-
some state q will repeat. ify the stack in an accepting computation and let A
Consider the part of the computation between the accept w = ux j v ∈ L p , j ≥ 1, u, v ∈ Σ∗p . Then A also
two occurrences of the state q where some number j, accepts ŵ = ux j+1 v ∈
/ Lp.
1 ≤ j ≤ n − 1 of symbols a1 was read. Suppose the
size of the stack was not increased during this part of Lemma 4. Let A in PDA(1, p) be a minimal automa-
the computation. By leaving out this part of the com- ton accepting the language L p , where p ∈ N. Then
putation we clearly obtain an accepting computation ∀i, 1 ≤ i ≤ p ∃Z ∈ Γ such that (q0 , ε) ∈ δ (q0 , bi , Z).
on the word w0 = am− j
∈
/ L2 [n]. Similarly, in case the
1 Proof. Let us consider words w1 = am m
1 b1 , . . . , w p =
size of the stack was increased during this part of the m m
a1 b1 in L p for sufficiently large m. Note that the
computation, by repeating this part of the computa-
size of the stack after reading the a-part of the words
tion we clearly obtain an accepting computation on
cannot be bounded. (Otherwise, for sufficiently large
the word w” = am+ 1
j
∈
/ L2 [n]. (Note that by consid-
m some stack content would repeat. Leaving out this
ering the two cases we ensured that the computation
part of the input and computation would lead to an
on the modified word does not block because of the
accepting computation on a word with smaller num-
empty stack.)
ber of a’s and unchanged number of b’s.) Thus, af-
ter reading the a-part of the words w1 , . . . , w p the
stack will contain some (large) word in Γ+ which the
4 PDA on Nonregular Context Free next part of the accepting computation has to remove
Languages while reading the b-part of the word.7
Now, suppose that to the contrary of the statement
In this section, we shall analyze complexity of (non- of lemma there exists some bk such that A does not
regular) context free languages using both subfami- pop any stack symbol from the stack on bk . Formally,
lies of PDA considered. In PDA(1, p), we shall show ∀Z ∈ Γ it holds that (q0 , ε) ∈ / δ (q0 , bk , Z).
lower and upper bounds for a particular sequence of Let us analyze the accepting computation on the
languages and in PDA(n, 2), we shall analyze the word wk . Since A has to empty the stack while read-
relation of complexities for the two modes of ac- ing the b-part of wk and cannot pop the stack symbols
ceptance. Furthermore we shall show some upper while reading bk , the symbols on the stack have to be
bounds for a particular sequence of langauges. removed in ε-transitions. Thus there are at least two
distinct symbols Z1 used in the bk transition and Z2
4.1 The Number of Stack Symbols used in the ε-transition in Γ used in the b-part of the
accepting computation on wk . (Having these sym-
Let us consider the following sequence of context
bols equal would enable accepting computation on a
free languages.
word with fewer bk ’s.) Neither of these symbols can
Notation 3. Let a1 , . . . , a p , b1 , . . . , b p be distinct sym- be popped from the stack by some bi , i 6= k since this
bols for any p ≥ 1. Let would allow to modify accepting computations on
the words w1 , . . . , w p to accepting computations on
Σ p = {a1 , . . . , a p , b1 , . . . , b p } words not in L p . (A detailed analysis of the accept-
L p = {w(h(w))R |w ∈ {a1 , a2 , . . . , a p }∗ } ing computations on the words the words w1 , . . . , w p
shows that p symbols are not enough when bk cannot
where h is the homomorphism defined by h(ai ) = bi ,
pop any symbol in Γ.)
for each i, 1 ≤ i ≤ p.
We can easily see that any PDA using one state Lemma 5. Let A in PDA(1, p) be an automaton ac-
has to use empty stack acceptance mode to accept cepting the language L p , where p ∈ N. Suppose
the language L p . This shows that the empty stack (q0 , ε) ∈ δ (qo , bi , Z) and (q0 , ε) ∈ δ (qo , b j , Ẑ) for
acceptance mode and the final state acceptance mode i 6= j. Then Z 6= Ẑ.
do not have the same power in PDA(1, p).
Proof. Suppose that one state push down automaton
Our intention is to prove that the number of stack
A accepting the language L p pops on bi and b j the
symbols complexity of the language L p for one state
same stack symbol Z from the stack and let A accepts
PDA is exactly p + 1. To prove the lower bound,
w = am m m m /L .
i bi . Then A accepts ŵ = ai b j ∈ p
we shall first prove several lemmas. Each lemma ex-
hibits a property, each push down automaton accept- Combining the previous lemmas 4 and 5, we can
ing L p has to have. infer that one state push down automaton needs at
Lemma 3. Let A in PDA(1, i) be an automaton ac- least p stack symbols to accept L p . The next theorem
cepting the language L p , where p, i ∈ N. Let x ∈ Σ p shows that in fact p + 1 stack symbols are required.
be an input symbol. Then in each accepting compu-
tation on w ∈ L p , w = ux j v, j ≥ 1, u, v ∈ Σ∗p , A has to
modify the stack while reading x. 7 The acceptance is by empty stack.
Before we show the proof of a lower bound and con- free language. It is known ([11]) that at least two
struct an upper bound, we shall infer some properties stack symbols are necessary to accept all context-free
about the δ function from the previous lemmas. languages by empty stack or final state.
Let us consider the influence of these two accep-
Corollary 2. Let A = ({q0 }, {a1 , . . . , a p , b1 , . . . , b p }, tance modes on the complexity. We can not use
{Z1 , Z2 , . . . , Z p }, δ , q0 , Zi , 0)
/ in PDA(1, p) be an au- the standard constructions[11] to prove equivalence
tomaton accepting by empty stack the language L p , of the computational power of the two acceptance
where p ∈ N. Then there exists some permutation modes, because both of them introduce a new stack
s on {1, . . . , p}, such that (q0 , ε) ∈ δ (q0 , bi , Zs(i) ), symbol. The family of automata we consider allows
where Zi is a stack symbol used by the automaton at most two stack symbols. The problem can be
A. solved by prefix encoding used by Goldstine, Price
We are now ready to present the complexity of the and Wotschke in their paper On reducing the num-
languages L p . ber of stack symbols[5]. The results they present
show the upper and lower bounds for the number of
Theorem 7. Γc(L p ) = p + 1, ∀p ∈ N states. These results cannot be directly applied in our
case, due to their approximate form. That is why we
Proof. We shall show that Γc(L p ) ≤ p + 1 by con-
present a lemma, which shows exact upper bound for
structing an automaton A in PDA(1, p + 1) accepting
three to two stack symbol transformation.
L p by empty stack.
The new automaton has fewer stack symbols, each
The automaton pushes on each input symbol ai the
stack symbol Z is represented by a string h(Z). Nat-
stack symbol Zi onto the stack. The automaton pops
urally this increases the number of states. In our con-
the Zi from the stack on the input symbol bi . The ini-
struction, let A in PDA(s, 3) be an automaton using
tial stack symbol is Z0 and is kept on the top of the
stack symbols H1 , H2 , H3 . We construct an equiv-
stack while reading ai symbols. On any input symbol
alent automaton B using two stack symbols Z0 , Z1 .
ai , it can nondeterministically change the top stack
Each stack symbol Hi is represented in B by a string
symbol to Zi instead of pushing the new Zi onto the
h(Hi ) of symbols Z0 and Z1 . The states of B are pairs
stack. This moves the push down automaton to the
of the form [q, γ], where q is a state of A and γ is a
next phase. In this phase it is comparing the reverse
proper prefix8 of h(Hi ). The idea is that the automa-
order of b symbols to a symbols by popping Z sym-
ton B reads the encoded stack symbol from the stack
bols from the stack. At the end of computation, the
and saves it to the current state. Then the automaton
push down automaton A accepts by empty stack.
B does the same computation as A. For the mapping
h, we have chosen:

We shall prove Γc(L p ) ≥ p + 1 by contradiction. • h(H1 ) = Z1
Let A in PDA(1, p) be an automaton accepting the
• h(H2 ) = Z0 Z0
language L p and let Zi be the initial stack symbol.
By corollary (2): there exists some permutation s on • h(H3 ) = Z1 Z0
{1, . . . , p}, such that (q0 , ε) ∈ δ (q0 , bi , Zs(i) ). Then A
accepts w = bs(i) ∈ / Lp.
PDA A PDA B
note that this theorem shows that the number of State Stack State Stack
stack symbols complexity hierarchy of one state PDA q ...Hj [q, ε] . . . Zi1 . . . Zis
is not bounded. | {z }
h(H j )
[q, Zis . . . Zi2 ] . . . Zi1
4.2 The Number of States p . . . H j1 . . . H jk [p, ε] . . . Z f1 . . . Z fn
| {z }
We shall now discuss the influence of the acceptance h(H j1 )...h(H jk )
mode on the complexity. The family of one state
PDA was forced to use the empty stack acceptance
Figure 1: Example of one computation step of
mode since the final state acceptance mode could
PDA A simulated on PDA B using (p, H j1 . . . H jk ) ∈
only be used for specific languages. The influence
δ (q, a, H j ), where a is some input symbol. The fig-
of the acceptance mode on the complexity thus was
ure illustrates the general case encoding an arbitrary
not an issue.
number of symbols Hi . In our case s can be at most
two.
Comparison of Acceptance Modes
Finally, the accepting states of B shall be all states
The family PDA(n, 2) of automata allows both types [q, ε], where q is an accepting state of A. The last item
of acceptance mode, empty stack or final state. Any
one of them can be used to accept arbitrary context 8 The string x is a proper prefix of xy if y 6= ε.
to specify is the initial stack symbol of B. Without Theorem 9. Given a push down automaton A using
loss of generality, we can assume that H1 is the initial two stack symbols and s states, there exists a push
stack symbol of A. Otherwise, we can rename the down automaton B using two stack symbols and 2s +
stack symbols of A. 2 states such that N(B) = L(A).
We shall now describe our construction.
Proof. Let us use a general construction (see, e.g.,
Lemma 6. Let A in PDA(s, 3) be an automaton. [11]), which constructs a new automaton C. The au-
Then there exists a push down automaton B using two tomaton C is using three stack symbols and s + 1
stack symbols and 2s states such that L(B) = L(A). states. By the previous Lemma 7, there exists a
push down automaton B using two stack symbols and
Proof. The construction uses the h function as an en-
2s + 2 states such that N(B) = L(C).
coding function for stack symbols of the automaton
A to stack symbols of the automaton B. Then B simu-
lates the automaton A by decoding the encoded stack Upper bounds Let us consider the following se-
symbols from the stack. If Z1 is on the top of the quence of context free languages.
stack and the automaton is in the state [q, ε] then it
can simulate the step of the automaton A in the state Notation 4. Let a, b, c be distinct symbols. Let Σ =
q and H1 as the top stack symbol. On the other hand, {a, b, c}. For each r ≥ 1 let
if the top stack symbol is Z0 and it is in the state [q, ε] • L = {w = am bm |m ≥ 1}
then the automaton B needs to read one more stack
symbol from the stack. So it saves the symbol read • L3 [n] = {cm |0 ≤ m ≤ n}
in the state. Then it reads the next stack symbol in
the state [q, Z0 ] and simulates a computation step of • L4 [n] = Shu f (L, L3 [n])
A. At first, let us discuss the properties of the lan-
Let us now present the construction from the guage L. Note that the language L coincides and thus
empty stack acceptance mode to the final state ac- has the same properties as the language L p (defined
ceptance mode. We omit a formal description of the in the Section 4.1), for p = 1. We proved that one
transformation since it is straightforward. state automaton needs at least two stack symbols to
accept L p , p = 1. Then using the general idea from
Theorem 8. Given a push down automaton A using Theorem 7, we can construct the minimal one state
two stack symbols and s states, there exists a push PDA accepting L.
down automaton B using two stack symbols and 2s + We shall now modify the language L in order to
2 states such that L(B) = N(A). "force" the PDA to check some additional property.
Both stack symbols are used for keeping track of
Proof. Let us use a general construction (see, e.g.,
symbols a and b. Adding another property to this
[11]), which for a given PDA A constructs a PDA C
language should result in increasing the number of
such that L(C) = N(A). This PDA C uses three stack
states. The property we shall use is the language
symbols and s + 1 states. By Lemma 6, there exists
L3 [n], the number of c symbols should be equal or
a push down automaton B using two stack symbols
less then n. Mixing properties of L and L3 [n] lan-
and 2s + 2 states such that L(B) = L(C).
guages results in the language L4 [n]
In order to replace the final state acceptance by the Finally, we should decide, which acceptance mode
empty stack acceptance we need a lemma similar to we shall use. Let us use the same acceptance mode
Lemma 6 dealing with the empty stack acceptance as in the previous Section 4.1, empty stack accep-
mode. tance mode. This results in an easier upper bound
construction.
Lemma 7. Let A in PDA(s, 3) be an automaton. Our automaton has n + 1 states. Each state repre-
Then there exists a push down automaton B using 2 sents the number of c symbols read. If the automaton
stack symbols and 2s states such that N(B) = N(A). reads the (n + 1)st symbol c it blocks.
Proof. The automaton B shall have the states: Qb =
Theorem 10. There exists a PDA An using two stack
Qa × {ε, Z0 } and we shall use the same encoding9 h.
symbols and n + 1 states such that N(An ) = L4 [n].
Using the reduction and mapping h, we construct the
δB transition function of B similarly as in the proof of Proof. We shall construct a PDA An =
Lemma 6. The automaton B uses two stack symbols ({q0 , . . . , qn }, {a, b, c}, {Z1 , Z2 }, δr , q0 , Z2 , 0)
/
and 2s states and N(B) = N(A). The stack symbol Z1 is used as a counter. On input
symbol a, the automaton pushes Z1 on the stack
Now, we are ready to present the construction from
and it keeps the stack symbol Z2 on the top. The
the final state acceptance mode to the empty stack
automaton keeps Z2 on the top of the stack. This
acceptance mode.
indicates An is still reading the part of the input
9 h(H ) = Z , h(H ) = Z Z , h(H ) = Z Z containing the a symbols. The automaton An can
1 1 2 0 0 3 1 0
nondeterministically pop Z2 on ε and start to pop Z1 [11] J. E. Hopcroft, R. Motwani, and J. D. Ullman, Intro-
on each b. On symbol c, the automaton changes the duction to Automata Theory, Languages, and Com-
state from qi to qi+1 . In case An is in the state qn and putation (3rd Edition). USA: Addison-Wesley Long-
reads the input symbol c, it blocks. man Publishing Co., Inc., 2006.

5 Conclusion

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 ’ex-
treme’ sub classes of PDA each able to define all
context-free languages. It would be natural to study
behaviour of complexity when operations on lan-
guages are performed (some upper bounds appear in
[10]) or when some transformations are performed
on PDA.

References
[1] M. Holzer and M. Kutrib, “Descriptional complex-
ity — an introductory survey,” in Scientific Applica-
tions of Language Methods, pp. 1–58, World Scien-
tific, 2011.
[2] M. Holzer and M. Kutrib, “Descriptional and compu-
tational complexity of finite automata—a survey,” In-
formation and Computation, vol. 209, no. 3, pp. 456–
470, 2011.
[3] J. Dassow, “Descriptional complexity and operations
– two non-classical cases,” in Descriptional Com-
plexity of Formal Systems (G. Pighizzini and C. Câm-
peanu, eds.), pp. 33–44, Springer International Pub-
lishing, 2017.
[4] J. Goldstine, J. K. Price, and D. Wotschke, “On re-
ducing the number of states in a pda,” Mathematical
systems theory, vol. 15, no. 1, pp. 315–321, 1981.
[5] J. Goldstine, J. K. Price, and D. Wotschke, “On re-
ducing the number of stack symbols in a pda,” Math-
ematical systems theory, vol. 26, no. 4, pp. 313–326,
1993.
[6] A. Okhotin, X. Piao, and K. Salomaa, “Descriptional
complexity of input-driven pushdown automata,” in
Languages Alive, pp. 186–206, Springer, 2012.
[7] J. Goldstine, M. Kappes, C. M. Kintala, H. Leung,
A. Malcher, and D. Wotschke, “Descriptional com-
plexity of machines with limited resources,” J. UCS,
vol. 8, no. 2, pp. 193–234, 2002.
[8] B. Rovan and S. Sadovsky, “On usefulness of infor-
mation: Framework and nfa case,” in Adventures Be-
tween Lower Bounds and Higher Altitudes: Essays
Dedicated to Juraj Hromkovič on the Occasion of His
60th Birthday, pp. 85–99, Springer, 2018.
[9] P. Labath and B. Rovan, “Simplifying dpda using
supplementary information,” in International Confer-
ence on Language and Automata Theory and Appli-
cations, pp. 342–353, Springer, 2011.
[10] L. Kiss, “Descriptional complexity of push down
automata.” Master Thesis, Comenius University in
Bratislava, 2020.