Close
Close Window

CS4114 Formal Languages and Automata

Chapter 7 Pushdown Automata

Show Source |    | About   «  6.4. Transforming Grammars Exercises   ::   Contents   ::   7.2. PDA Exercises  »

7.1. Pushdown automaton

7.1.1. PDA: Pushdown Automata

One of defining characteristics of DFAs and NFAs is that they have no memory. So there is no history or way to store information aside from what state they are currently in. In this and future chapters, we will study two types of machine with memory: The Pushdown Automata (or PDA, so-called because it has a stack) and the Turing Machine (that has a somewhat more flexible form of memory). Not coincidentally, we will find that these machines have more capability than do DFAs in terms of the languages that they can recognize.

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$

Created with Raphaël 2.1.2
input tape
  1. a
  2. a
  3. a
  4. a
  5. b
  6. b
tape head
current state
1
0
head moves
Proficient Saving... Error 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).

Proficient Saving... Error 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.

Proficient Saving... Error 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.

Proficient Saving... Error 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?

Created with Raphaël 2.1.2
Proficient Saving... Error Saving
Server Error
Resubmit

   «  6.4. Transforming Grammars Exercises   ::   Contents   ::   7.2. PDA Exercises  »

nsf
Close Window