Since a PDA halts when its stack is empty and this causes no run for inputs with remaining unread letters, it is forbidden by (iii) for DPDAs to empty their stack.
This in turn prohibits the use of empty stack acceptance in DPDAs.
The availability of _-moves will subsequently be very helpful so they are retained in DPDAs. But restrictions (i) and (ii) are imposed on DPDAs so that at each step either an _-move or a _-move is possible, but never both.
Definition 5.3.2: a language L is deterministic context- free if there exists a DPDA M so that L = L(M).
| Previous slide | Next slide | Back to first slide | View graphic version |