Lecture 10 (Push-down Automata), 10/2/17

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 (q, c, x, x’, q’);
    • Start in state q, read char c, pop stack x, push stack x’, go to state q’ 
    • the label on the arrow would be c,x -> x’
  • 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.
  • Example: PDA M1 for {0n1n: n >= 1, 1 <= m <= n}
  • Example: PDA M1 for {0n1n: n >= 0} (p. 115)
  • PDA design trick: special “bottom of stack” character ($ in our textbook)
  • PDA configuration – (state, stack contents)

o   Starting configuration (initial state, empty stack)

o   ending configuration (final state, any stack)

o   Every transition takes one configuration to a different one.

  • 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
  • Example: PDA M2 for {wwR : w over {a,b}* }  (p. 116)
  • Our PDAs are non-deterministic (given a configuration, multiple transitions may be possible, or none).
  • Deterministic PDAs can also be defined; their expressiveness is not the same, but between that of DFAs/NFAs and of PDAs
    • 0n1n can be done with deterministic PDA
    • wwR can’t
  • PDA, PDA computation, language of a PDA: formal definitions
  • 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 can be generated with a 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 -1s to represent negative number -n