Popular Posts

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

Visitor's Feedback

"I am very thankful, providing good stuff for engg students. I got good information about TOC and its information valuable for me."
: - Ankur Loriya (Ahmedabad)

"An amazing work, i just love your work!! please please please keep updating application based problems as well, it will definitely add interests to those whose visit your blog!! Thank you"
: - Preethi Velmurughan (Coimbatore)

"I got chance to learn what is the theory of computation thats why thankh you very much for this blog"
: - Ajay Sapkota (Kathmandu)

"Very nice presentation ,easy to go through the content"
: - Dr. A ramesh babu(Trichy)

"Nice tutorial example of constructing dfa..... thanks"
: - Manoj kumar (Delhi)

"I am a lecturer who is handling TOC for B.E students ....This is blog is very much useful for me ..It gives a lot of informations."
: - Sivaranjani.s (Theni)

"This is very good material for theory of computation thank you sir"
: - Mohan lal jat (Udaipur)

"its very good for engg student to get a readymade questions at the exam time. thank you."
: - Asfiya Peerjade (Kolhapur)

"I am a lecturer....this blog is awussom for me to understand.... and to learn more practical example....thanx nd plzzzz update more 1"
: - Sumedha Bhagat (Lecturer, Pune)

"You are doing very good job for an engg student for getting more problems with solution."
: - Chandrakant (Student, Nanded)


Google+ Followers