title: Pushdown Automaton: Empty input versus empty stack
body: <p>I have a theoretical computation science final coming up and while studying I got stuck on drawing pushdown automaton (PDA) diagrams.</p>
  
  <p>The last transition is almost always </p>
  
  <p><img src="https://latex.codecogs.com/gif.latex?%5Cvarepsilon,&space;*&space;%5Crightarrow&space;%5Cvarepsilon" title="\varepsilon, * \rightarrow \varepsilon" /></p>
  
  <p>I understand this to mean consume none of the input string, pop the end of stack symbol and push nothing onto the stack.</p>
  
  <p>Where I am stuck is this does not check that the input string is empty, just that the end of stack symbol in on the top of the stack.</p>
  
  <p>For a language like 0<sup>n</sup>1<sup>n</sup> we push the end of stack symbol, then push a 0 every time a 0 is read from the input. On the first 1 we begin popping the 0s off the stack. In an ideal world once we get to the end of the input string the only thing on the stack will be the end of stack symbol and we can take that last transition. What happens if there are still 1s in the input. For example, an input string of 00111.</p>
  
  <p>Couldn't we use the <img src="https://latex.codecogs.com/gif.latex?%5Cvarepsilon,&space;*&space;%5Crightarrow&space;%5Cvarepsilon" title="\varepsilon, * \rightarrow \varepsilon" /> transition into the acceptance state while having remaining characters to consume?</p>
  
  <p>Should there be a transition out of the final state, to some dead state, to account for remaining input characters?</p>