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:
“Awareness of the stars and their light pervades the Koran, which reflects the brightness of the heavenly bodies in many verses. The blossoming of mathematics and astronomy was a natural consequence of this awareness. Understanding the cosmos and the movements of the stars means understanding the marvels created by Allah. There would be no persecuted Galileo in Islam, because Islam, unlike Christianity, did not force people to believe in a “fixed” heaven.”
—Fatima Mernissi, Moroccan sociologist. Islam and Democracy, ch. 9, Addison-Wesley Publishing Co. (Trans. 1992)
“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)
“To exist as an advertisement of her husband’s income, or her father’s generosity, has become a second nature to many a woman who must have undergone, one would say, some long and subtle process of degradation before she sunk [sic] so low, or grovelled so serenely.”
—Elizabeth Stuart Phelps (1844–1911)