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: enter image description here


1 Answer 1


That section is not talking about parsing. The algorithms referred to are algorithms for converting between CFGs and PDAs of different types. The question is, as usual, "what is the computational complexity of the algorithm", and the response is, as usual, expresseded in terms of the size of the input -- to the algorithm.

The input to an algorithm which converts a PDA to a CFG is the PDA, and the size of the input -- the metric stick for the algorithm's complexity -- is the size of the *PDA". That's what the authors intend n to be.

How does one measure the size of a PDA? Simple: you write the PDA out as a string in some PDA definition language, and count symbols in the description. That's a completely fair procedure, because in order to call the conversion algorithm on the PDA, it's necessary to give the converter an input which represents the PDA.

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.

  • $\begingroup$ 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 $\endgroup$ Apr 17, 2020 at 6:40
  • 1
    $\begingroup$ @abhishekGhosh: the total symbol count of all of the grammar rules is a perfectly reasonable measure of the size of the grammar. $\endgroup$
    – rici
    Apr 17, 2020 at 14:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.