My Youtube Video Channel ( With Theory of Computations)

Loading...

Sunday, December 26, 2010

Pushdown Automata

Pushdown Automata (PDA) is a computational model equivalent to Context Free Grammar (CFG).

A Pushdown Automata (PDA) is an Non-Deterministic Finite Automata (NFA) augmented with an infinitely large stack.

The additional memory enables recognition of some non-regular languages.


A Pushdown Automata (PDA) is essentially a Finite Automata with a Stack data structure as shown above.

A Pushdown Automata (PDA) can write an unbounded number of stack symbols on the stack and read these symbols later.

Writing a symbol onto the stack is called Pushing and it pushes all symbols on the stack one stack cell down.

Removing a symbol off the stack is called Poping and every symbol on the stack moves one stack cell up.

A Pushdown Automata (PDA) can access only the stack's topmost symbol in LIFO manner.

Now, We Consider how to describe precisely the abstract machine whose operations.we have sketched each move of the machine will be determined by three things.

(1) The Current State
(2) The Next Input
(3) The Symbol on top of the Stack

and will consist of two parts.

(1) Changing state ( Or staying in the same state)
(2) Replacing the top stack symbol by a string of zero or more symbols.

No comments:

Post a Comment