Lecture 10 (Push-down Automata), 2/20/18

Concepts, definitions (in italics):

  • Pushdown Automata (PDAs): NFAs with a stack -- we push symbols onto the stack and pop from the stack, one at a time
  • Formal definition (p. 113): PDA = (Q, Sigma, Gamma, delta, q0, F)
  • PDA transitions in delta: 5-tuples of the form (q1, c, x, y, q2);
    • Start in state q1, read char c, pop stack x, push stack y, go to state q2
    • the label on the arrow would be c,x -> y
  • To start computation, a PDA must be in initial state and have empty stack
  • Can only make transition that reads c (in Sigma) and pops a (in Gamma) if the remaining input starts with c and the stack has a on top
  • To accept a string, a PDA must be in a final state and have read all the input (just as for FSAs); however, it need not have an empty stack.
  • Our PDAs are non-deterministic (given a configuration, multiple transitions may be possible, or none)
  • Example: PDA M1 for {0n1m: n >= 1, 1 <= m <= n}
  • Example: PDA M2 for {0n1n: n >= 0} (p. 115)
  • PDA design trick: special "bottom of stack" character ($ in our textbook)
  • PDA configuration -- (state, remaining input, stack contents)

o   Starting configuration (initial state, complete input, empty stack)

o   ending configuration (?, empty input, any stack)

o   accepting configuration (final state, empty input, any stack)

o   Every transition takes one configuration to a different one.

  • Stack contents is represented as a string in Gamma*, with the topmost character on the left
  • A valid accepting PDA computation is a sequence of PDA transitions
    • It starts in a starting configuration, reads the whole input string, and ends in an ending configuration
  • NFAs are a special case of PDAs (which ignores its stack)
  • PDAs are strictly more powerful (i.e. have greater expressiveness) than NFAs (we saw one for {0n1n})
    • We will be showing that CFGs and PDAs have the same expressiveness.
  • This will give us an alternate definition of a CFL: one that is accepted by some PDA.
  • Example: PDA M3 for {w over {a,b}* : w contains equal number of a's and b's}
    • This is a context-free language, because there is a CFG for it
    • It is not regular, because of its intersection with a*b*
  • PDA design trick: using stack as a counter

Reading:

  • Chapter 2.2 to end of p. 116

Skills:

         Know new definitions, understand new concepts.

         Given a PDA M and a string w, show an accepting computation of M for w as a sequence of configurations and transitions

         Understand why NFAs are a special case of PDAs

Notes:

Question: design a PDA for the language L = {w in {a,b}* : w contains equal number of a's and b's}. 

1.      Consider any string w in L.  Imagine going along the string from left to right keeping a tally as follows: Start the tally at 0, add 1 for every a, subtract 1 for every b.  Our tally will be 0 at the end, and it may also be 0 in places along the way.  Here is an example for aabbba, where we show the characters and the tally

             0 a 1 a 2 b 1 b 0 b -1 a 0

2.      Use the stack to keep tally, with n 1's to represent positive number n and n -1's to represent negative number -n