Pushdown Automaton - Understanding The Computation Process

Understanding The Computation Process

The following illustrates how the above PDA computes on different input strings. The subscript from the step symbol is here omitted.

(a) Input string = 0011. There are various computations, depending on the moment the move from state to state is made. Only one of these is accepting.

(i) . The final state is accepting, but the input is not accepted this way as it has not been read.
(ii) . No further steps possible.
(iii) . Accepting computation: ends in accepting state, while complete input has been read.

(b) Input string = 00111. Again there are various computations. None of these is accepting.

(i) . The final state is accepting, but the input is not accepted this way as it has not been read.
(ii) . No further steps possible.
(iii) . The final state is accepting, but the input is not accepted this way as it has not been (completely) read.

Read more about this topic:  Pushdown Automaton

Famous quotes containing the words understanding the, computation and/or process:

    Nothing comes to pass in nature, which can be set down to a flaw therein; for nature is always the same and everywhere one and the same in her efficiency and power of action; that is, nature’s laws and ordinances whereby all things come to pass and change from one form to another, are everywhere and always; so that there should be one and the same method of understanding the nature of all things whatsoever, namely, through nature’s universal laws and rules.
    Baruch (Benedict)

    I suppose that Paderewski can play superbly, if not quite at his best, while his thoughts wander to the other end of the world, or possibly busy themselves with a computation of the receipts as he gazes out across the auditorium. I know a great actor, a master technician, can let his thoughts play truant from the scene ...
    Minnie Maddern Fiske (1865–1932)

    Science is a dynamic undertaking directed to lowering the degree of the empiricism involved in solving problems; or, if you prefer, science is a process of fabricating a web of interconnected concepts and conceptual schemes arising from experiments and observations and fruitful of further experiments and observations.
    James Conant (1893–1978)