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¶

1 / 14 Settings

<<<>>>

Next we will look more closely at PDA transitions.

Similar to a NFA, PDAs can have different behaviors on the same input. That is, an NFA can have multiple choices about what to do on the input symbol 'a'. This is the fundamental concept of non-determinism. In a similar way, a PDA can choose between multiple behaviors on a given input condition (current state, current input, and current top of the stack). A PDA that has multiple behaviors on a given input is called a Non-deterministic PDA (NPDA).

q0

q1

q2

q3

a,b;b

a,b;ab

a,b;λ

Saving...
Server Error
Resubmit

7.1.3. PDA Acceptace Models - Final State Acceptace¶

1 / 35 Settings

<<<>>>

A DFA or NFA accepts a string if and only if it is in a final state when it completes processing the string. A given PDA might use one of two different definitions for string acceptance. A PDA might operate under the defintion that it accepts a string if and only if it is in a final state after completing processing the string, like a DFA or NFA. The other definition is that the stack is empty when the string has been processed.

q0

q1

q2

q3

a,Z;aZ

a,a;aa

b,a;λ

b,a;λ

λ,Z;Z

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

Input Tape

5. Z

PDA Stack

1. a
2. b
3. a
4. b

Saving...
Server Error
Resubmit

7.1.4. PDA Acceptace Models - Empty Stack Acceptace¶

1 / 36 Settings

<<<>>>

PDAs, like DFAs and NFAs, can accept a string based on being in a final state once the string has been processed. Unsurprisingly, this is referred to as Final State acceptance, and it ignores the contents of the stack when it makes the decision about whether to accept. However, there is a second type of acceptance that PDAs might use. We will call this Empty Stack acceptance.

q0

q1

q2

q3

q4

a,Z;0Z

a,0;00

b,0;00

b,0;00

c,0;λ

c,0;λ

λ,Z;λ

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

Input Tape

5. Z

PDA Stack

1. a
2. a
3. b
4. c

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?