Pushdown Automaton - Relation To Backtracking

Relation To Backtracking

Nondeterministic PDAs are able to handle situations where more than one choices of action are available. In principle it is enough to create in every such case new automaton instances that will handle the extra choices. The problem with this approach is that in practice most of these instances quickly fail. This can severely affect the automaton's performance as the execution of multiple instances is a costly operation. Situations such as these can be identified in the design phase of the automaton by examining the grammar the automaton uses. This makes possible the use of backtracking in every such case in order to improve performance.

Read more about this topic:  Pushdown Automaton

Famous quotes containing the words relation to and/or relation:

    There is the falsely mystical view of art that assumes a kind of supernatural inspiration, a possession by universal forces unrelated to questions of power and privilege or the artist’s relation to bread and blood. In this view, the channel of art can only become clogged and misdirected by the artist’s concern with merely temporary and local disturbances. The song is higher than the struggle.
    Adrienne Rich (b. 1929)

    Parents ought, through their own behavior and the values by which they live, to provide direction for their children. But they need to rid themselves of the idea that there are surefire methods which, when well applied, will produce certain predictable results. Whatever we do with and for our children ought to flow from our understanding of and our feelings for the particular situation and the relation we wish to exist between us and our child.
    Bruno Bettelheim (20th century)