3
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

Let's start with a finite automaton. Such a device can be viewed as a machine that has a fixed, finite number of boolean variables, like $s = $ "we've seen an even number of $0$'s in the input so far", or $s_i = $ "the input so far, when interpreted as a binary number, is congruent to $i\pmod 3$". Using such a machine, we can count, but only up to a fixed, finite value.

A PDA can be viewed as a FA with one other variable, a stack. With such a machine, we can count up to an arbitrary number. This means that while the language $$ L=\{a^nb^n\mid n\ge 0\} $$ can't be accepted by any FA, it can be recognized by a PDA: for each $a$ we see in the input, we push a marker on the stack and for each $b$ we pop a marker off the stack. When we've seen all the input we stop and accept if the stack is empty and reject if it's not.

In a similar way, we can use the stack to store patterns in our input, which is why the palindrome language $$ P=\{wcw^R\mid w\in \{a,b\}^*\} $$ can similarly be recognized by a PDA: we push the characters seen on the stack until we see a $c$ and then match the rest of the inputs against the contents of the stack. Since the stack will contain the characters in $w$, we can match the reverse, $w^R$ part of the input against the contents of the stack.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.