Pushdown Automata

Sat 9:30 AM

Prof. Calvin

CSCI 5100

Sketch

  • Schematic View of Automata
  • The Stack
  • The Automaton
  • Conversions

Schematic View

Vs CFG

  • CFGs Pāṇini ~2500 years ago
  • Formalized 1950s (Chomsky)
  • Then PDAs 1960s (Chomsky)

Overview

  • We abstract the automata into a unit called the “Finite Control”
    • In a *FA, this denotes the current state.
    • We often denote it as a box
  • We imagine input as coming on a tape.
    • In practice, early devices did use tapes.
    • Modern devices use block reads of SSDs (same thing)

Tapes

Terms

  • Finite Control: Represents the finite state, or states, of an automata.
  • Input: Represents the input string to some automata.
    • *FAs can only read in one direction - not so for all automata.
  • This abstraction made it easier for me to separate letters and states in my mind.

New Terms

  • Stack: Memory of the automata
    • *FAs had no memory other than internal state - not so for all automata.
  • Head: Refer to “wherever the automata is currently pointed” as where the head of the automata is.
    • Think, perhaps, of a vinyl player.
    • My first job was on Hard Disk Drives (HDDs) with a “head” which wrote/read bits from a rotating magnetic disk.

The Stack

The Stack

  • PDA has unlimited but restricted memory.
  • It can only write certain symbols.
  • It can only read the most recent symbol.
  • Think the stack abstract data structure.
stack = []
stack.append('a')
stack.append('b')
stack.append('a')
print(stack.pop())
a

Intuition

  • Think of an NFA
  • Which write/add and read/remove symbols from the stack.
  • There is no “peek” operation.
    • But if can be synthesize from read+write.

Exercise

  • Recognize \(D = \{ 0^k1^k | k \in \mathbb{N}\}\) in Python
  • Read every character individually.
  • Only use one stack.
  • If you’re not sure of goals, read the solution and translate it to def from lambda

Solution

q_1 = lambda s, stack : [stack.append('0'), q_1(s[1:], stack)][-1] if s[0] == '0' and len(s) > 1 else [stack.pop(), q_2(s[1:], stack)][-1]
q_2 = lambda s, stack : [stack.pop(), q_2(s[1:],stack)][-1] if s[0] == '1' and len(s) > 1 else q_n(s, stack)
q_n = lambda s, stack : s == '1' and len(stack) == 1
q_1('000111', []), q_1('00111', []), q_1('00011', [])
(True, False, False)

The Automaton

Formal Definition…

A Pushdown Automaton (PDA) is formally defined as a 6-tuple:

  • \(Q\): A finite, non-empty set of states.
  • \(\Sigma\): A finite, non-empty set of input symbols called the input alphabet.
  • \(\Gamma\): A finite, non-empty set of stack symbols called the stack alphabet.
  • \(\delta\): The transition function, a mapping

Formal Definition..

A PDA is a 6-tuple \((Q, \Sigma, \Gamma, \delta, \ldots)\)

  • \(\delta\): The transition function, a mapping
    • \(\delta : Q \times (\Sigma_{\varepsilon} \cup \Gamma_{\varepsilon}) \rightarrow \mathcal{P} (Q \times \Gamma_{\varepsilon})\)
    • Given a state, letter, and stack symbol
    • Get a set of states and stack symbols.
    • \(\delta(q, a, c) = {(r_1, d), (r_2, e)}\)
      • In state \(q\), reading \(a\) on tape and \(c\) on stack, either write \(d\) and go to state \(r_1\) or write \(e\) and go to state \(r_2\)

Formal Definition.

A PDA is a 6-tuple \((Q, \Sigma, \Gamma, \delta, q_0, F)\)

  • \(q_0, F\) as in the *FAs.
  • It’s a *FA with a new alphabet that delta reads.

Example

  • Introduce reverse operation \(w^\mathcal{R}\)
  • Easiest to define with Python.
superscript_r = lambda w : w[::-1]
w = "stressed"
print('w =', w, 'w^R =', superscript_r(w))
w = stressed w^R = desserts
  • Take \(B = \{ww^\mathcal{R} | w \in \{0,1\}*\}\)

g n 0 0 1 1 1 1 0 0

Intuition

  • Read symbol, push to stack
  • At halfway mark, pop off stack and read.
    • If same, continue
    • If different, reject
  • How do we know we are the middle?
    • Nondeterminism - it doesn’t matter!
    • Each nondeterministic branch gets its own stack!

Empty stack

  • Wait… how do we see if the stack is empty.
    • Easy.
    • Invent a novel symbol.
    • Necessarily write it in the first state.
      • Can simply add a new state, transition, as needed.
    • These simplifying assumptions are useful convenience that doesn’t adversely impact rigor or change results.

Exercise

  • Accept \(D\) in Python.

Stretch Break