HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

How to understand pushdown automata intuitively?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
intuitivelyautomatapushdownunderstandhow

Problem

What is an intuitive way of understanding what a push down automaton is capable of computing?

Solution

Intuitively, a pushdown automaton uses a stack and using a stack we can do a depth first traversal of a parse tree. It means that we can accept strings which are in context free languages by using stack of a pushdown automaton (left-most derivation). This is not a rigorous proof that languages of pushdown automata are context free. For proofs you must see various textbooks on the subject.

Context

StackExchange Computer Science Q#56462, answer score: 4

Revisions (0)

No revisions yet.