# The total length of input to a pushdown automata which accepts by empty stack is an upper bound on the number states and stack symbols

I was going through the classic text "Introduction to Automata Theory, Languages, and Computation" (3rd Edition) by Jeffrey Ullman ,John Hopcroft, Rajeev Motwani, where I came across few statements about a pushdown automata (PDA) which accepts by empty stack, as:

1. $$n$$, the total length of the input, is surely an upper bound on the number of states and stack symbols.

2. One rule could place almost n symbols on the stack.

The following statements were made while the authors were about to make some notes about the decision properties of CFLs(Context Free Languages)

Now here are some points by which I am possibly able to contradict the claim rather than proving it correct.

1. Suppose $$n$$, is the total length of the input, but as per the design of the PDA it might so happen that to accept the input string all the states of the PDA is not involved, so by this we can't say that $$n$$ is an upper bound on the number of states the PDA has.

2. Though the PDA accepts by empty stack, it might so happen that a transition function adds more than $$n$$ elements on the top of the stack, but at the end on consuming the $$n$$ input symbols we can stay on the particular state and use epsilon transitions to just remain in the same state and pop the elements from the stack till it becomes empty. So how can we say that $$n$$ is an upper bound on the number elements on the stack? We arrive at a contradiction...

I don't understand where I am making the mistake, because the same statements are written in the 3rd edition of the book without any changes being made from the second edition which makes it probable that the statement is correct.

I have attached the corresponding portion of the text below:

Given that definition, the claims are not at all surprising. Every state and every alphabet symbol must be present at least once in the PDA description, so the size if that description is an upper bound. Similarly, it is possible that most of the description of the PDA is the description of a single rule, which could push almost n symbols.
• it is possible that most of the description of the PDA is the description of a single rule, which could push almost n symbols. This statement is well written. One more informal question to you, while reading the book the authors delt with the concept of size of a grammar being n , can you please also specify what it meant probably, as the authors do not give definition for the same but use them in the text. Is it the same as total symbol count in the total description of the grammar as you said here in case of the size of the PDA? thank you Apr 17, 2020 at 6:40