Stack primer and the push-down automaton

1. Derivation steps for a length-n string in CNF?
   Stuck? Peek at 3.2.2 Chomsky and Greibach normal forms

   • CNF: A → BC | a (+ S → ε). Length n ⇒ 2n − 1 steps; n − 1 binary nodes. Height h ⇒ |w| ≤ 2^(h−1).
   • Conversion: simplify, replace terminals in long bodies, split long bodies.
   • GNF: A → aα. Length n ⇒ n steps. No left recursion.

   Read lesson 3.2.2

2. CFG for aⁿbⁿ?
   Stuck? Peek at 3.1.2 Writing CFGs for standard languages

   • Wrap: S → aSb | ε (aⁿbⁿ); ratios S → aSbb.
   • Nested: outer wrap → inner wrap. Concatenation: S → XY. Union: S → S₁ | S₂. Star: S → S₁S | ε.
   • Palindromes S → aSa | bSb | a | b | ε. Balanced S → SS | (S) | ε. #a = #b: S → aSbS | bSaS | ε.
   • i ≠ j: S → AC | CB, C → aCb | ε, A → aA | a, B → bB | b.

   Read lesson 3.1.2

3. Which memory does the course story add after finite memory?
   Stuck? Peek at 0.1.1 What “computation” means

   • Machine: reads a finite input symbol by symbol, changes mode, ends with yes (accept) / no (reject) — or may never end.
   • Decision problem: a question whose answer is yes or no for every input.
   • Machines differ by memory: finite modes → pile of plates → endless notebook → beyond all machines.
   • Finite memory works iff the fact you must carry stays bounded (even/odd, remainder, “seen x?”). Unbounded counts/comparisons break it.

   Read lesson 0.1.1

Your code editor matches brackets: every time it sees ( it remembers one, every ) forgets one, and at the end nothing must be left over. That memory is a stack — a pile of plates where you only touch the top. Bolt a stack onto a finite automaton and you get a push-down automaton (PDA). It finally counts without limit — exactly what aⁿbⁿ needed.

A machine reads aaabbb. For each a it puts a plate on the pile; for each b it removes one. What must be true about the pile at the end for the string to be aⁿbⁿ?

Prediction check

The pile must be back to its starting state (only the bottom marker left), and no b may arrive when the pile is already empty of a-plates. Too many b’s → nothing to remove; too few → plates left over.

Stack primer

• push X: put X on top.
• pop: remove the top symbol.
• Only the top can be read. Last in, first out (LIFO).
• A special bottom marker Z₀ tells the machine the stack is otherwise empty.

Unlimited height means unlimited counting — but access only at the top limits what can be compared (that limit shows up in 3.4).

PDA definition (7-tuple)

A move “in state q, reading a (or ε), with X on top, go to p and replace X by γ”. γ = ε pops; γ = X keeps; γ = YX pushes Y. We write it on arrows as a, X / γ. The PDA is nondeterministic by default.

Instantaneous descriptions

Transition traces

Below is the aⁿbⁿ PDA: state q0 pushes A for each a; the first b moves to q1 popping; q1 keeps popping; when Z is on top, an ε-move goes to accepting q2. Step through accepted and rejected strings — the stack is drawn live.

Putting it together

• A PDA is a finite automaton with one unbounded stack, accessed only at the top.
• Moves read a symbol or ε, look at the top, and replace it by a string.
• IDs (q, w, γ) record a run step by step.

transition table of the aⁿbⁿ PDA (top of stack before → after)
 state  input  top   →  state  push
 q0     a      Z         q0     AZ
 q0     a      A         q0     AA
 q0     b      A         q1     ε      (pop)
 q1     b      A         q1     ε
 q1     ε      Z         q2     Z      (accept)
 q0     ε      Z         q2     Z      (accepts ε)

rejected "aab": (q0,aab,Z) ⊢ (q0,ab,AZ) ⊢ (q0,b,AAZ) ⊢ (q1,ε,AZ)   stuck with A on top

When does a PDA say yes: when it reaches an accepting state, or when its stack becomes empty? Both conventions exist; the next lesson shows when they agree and when they don’t.

1. MCQ

   In a PDA, δ maps Q × (Σ ∪ {ε}) × Γ to:

   1. Q
   2. Q × Γ
   3. finite subsets of Q × Γ*
   4. P(Q)
2. MSQ

   Which are true for the aⁿbⁿ PDA above?

   1. It accepts ε
   2. It accepts aabb
   3. It accepts abab
   4. After reading aaa its stack is AAAZ
3. NAT

   ID (q, abc, XYZ). Move δ(q, a, X) ∋ (p, ε). How many symbols are on the stack after it?

   Write your answer before opening the key.

4. MCQ

   What extra memory does a PDA have compared with an NFA?

   1. a second tape
   2. one stack
   3. a counter bounded by the input
   4. random access memory

• stack (push, pop, top, LIFO)
• bottom marker Z₀
• stack alphabet Γ
• push-down automaton (PDA)
• PDA transition a, X / γ
• instantaneous description (q, w, γ)
• move relation ⊢, ⊢*

1. PDA 7-tuple?
   Reveal answer

   (Q, Σ, Γ, δ, q₀, Z₀, F)
2. What does the label a, X / ε mean?
   Reveal answer

   Read a with X on top, pop X.
3. What is an ID of a PDA?
   Reveal answer

   (state, unread input, stack contents top-first).