Formal Stack

A collection of objects that can be pushed or popped from. Has:

• Push operation
• Pop operation
• Size
• Top of stack

Notation

$\text{ encountered symbol }:\text{top of stack}\to \text{ new top of stack}$

Push

$0:ϵ\to x$ Will push $0$ onto the stack

Push Initial Symbol

$$0 : \epsilon \to $$$ Oftentime used so that we know when the stack is near empty

Pop

$1:x\to ϵ$ Will pop $1$ from the stack