7.1.1. PDA: Pushdown Automata¶

A significant characteristic of DFAs and NFAs is that they have no memory. So there is no history or way to store information aside from the state that they are currently in. This restricts what languages they can recognize.

Consider what adding the ability to make use of just a single counter variable can do. For example, it is easy to recognize the language of balanced parentheses with a counter. Simply increment the counter when a left parenthesis is seen, and decrement when a right parenthesis is seen. If the counter ever goes negative, then reject. If it is zero after processing the string then accept, otherwise reject. Likewise, a counter will allow recognizing the language comprised of strings of the form $a^nb^n$.

But another alternative to storing a counter is to use a stack. Balanced parentheses can be recognized by pushing left parentheses onto the stack, and popping the top of the stack when encountering a right parentheses. Strings of the form $a^nb^n$ can likewise be recognized by pushing the initial a’s onto the stack, and then popping them off as the b’s are processed. Using a stack gives all of the capabilities of a counter, with a bit more flexibility.

In the next few chapters we will study two types of machine with memory. The Pushdown Automata (PDA) uses a stack for its memory, and we will see that this allows it to recognize a wider range of languages than can the DFA or NFA. The Turing Machine has a more flexible form of memory than does the PDA, which will allow it to recognize an even broader range of languages.

1 / 13 Settings

<<<>>>

Recall that a DFA is formally defined as $(Q, \Sigma, \delta, q_0, F)$.

In a DFA, the tape is read only, the head moves to the right only. DFAs are limited in power. They recognize regular languages but cannot recognize many other 'simple' languages like $a^nb^n$

input tape

1. a
2. a
3. a
4. a
5. b
6. b

tape head

current state

1

0

head moves

a

a

Z

Stack

Saving...
Server Error
Resubmit

7.1.2. Transitions Types for PDAs¶

0 / 0 Settings

<<<>>>

Consider this transition: $\delta(q_0, a, b) = \{(q_1, b),\ (q_2, ab),\ (q_3, \lambda)\}$.
This means that when in state $q_0$ with $a$ the current symbol on the tape and $b$ on the top of the stack, one of three things can happen: (1) Change to state $q_1$ and push $b$ onto the stack, or (2) Change to state $q_2$ and push $b$ then $ab$ onto the stack (work right to left), or (3) Change to state $q_3$ and put nothing onto the stack.

Saving...
Server Error
Resubmit

7.1.3. PDA Acceptace Models - Final State Acceptace¶

0 / 0 Settings

<<<>>>

Consider the following PDA.

Saving...
Server Error
Resubmit

7.1.4. PDA Acceptace Models - Empty Stack Acceptace¶

0 / 0 Settings

<<<>>>

Saving...
Server Error
Resubmit

7.1.5. Equivalence of Acceptance Definitions¶

1 / 19 Settings

<<<>>>

A given PDA might operate under one of two language acceptance criteria: Final state or empty stack. A natural question then becomes: Is there any differnce in the languages that each type of PDA can recognize?

q

s

M

q

0

q

f

λ, Z; ZZ'

λ, x; λ

λ, x; λ

λ, x; λ

λ, x; λ

λ, Z'; λ

λ, Z'; λ

λ, Z'; λ

Saving...
Server Error
Resubmit

7.1.6. Something to Think About¶

1. The PDA with its stack can easily recognize the language comprised of strings of the form $a^nb^n$. Can it also recognize the language comprised of strings of the form $a^nb^nc^n$?

2. Can the PDA recognize the language $wcw^R$? That is the language with a string $w$ followed by the symbol $c$ followed by the reverse of $w$. Certainly it can, but can it do this deterministically?

3. Can the PDA recognize the language $ww^R$? Yes, but can it do this deterministically?