The DPDA restrictions on _-moves prove inadequate to insure exactly one run for each input sequence. The difficulty occurs when there is an unending cycle of _-moves. This can result in either of the outcomes:
• there is no run if the DPDA encounters the infinite cycle before reading its entire input, or
• there are infinitely many runs if the infinite cycle is encountered after the entire input has been read
| Previous slide | Next slide | Back to first slide | View graphic version |