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.
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.
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: