Pushdown Automata (PDAs) represent a significant step up in computational power from Finite Automata. Unlike DFAs, which have finite memory, PDAs are equipped with an auxiliary memory structure called a stack. This stack operates on a Last-In, First-Out (LIFO) principle, allowing PDAs to "remember" an unbounded amount of information, but only in a highly constrained way (only the top of the stack is directly accessible). This added memory capability enables PDAs to recognize Context-Free Languages (CFLs), which include languages that require arbitrary counting or matching capabilities, beyond what a finite automaton can handle.

A Pushdown Automaton (PDA) is formally defined as a 7-tuple: M=(Q,Σ,Γ,δ,q0 ,Z0 ,F), where:
● Q: A finite, non-empty set of states. Similar to DFAs, these represent the control unit's current configuration.
● Σ: A finite, non-empty set of input symbols (the alphabet). This is the set of symbols that the PDA reads from its input tape.
● Γ: A finite, non-empty set of stack symbols (the stack alphabet). These are the symbols that can be pushed onto or popped from the stack. It's often distinct from the input alphabet.
● δ: The transition function. This is the core of the PDA's behavior. Unlike a DFA's transition function, it's typically a relation (allowing for non-determinism) and takes into account the current state, the current input symbol, and the symbol on top of the stack.
Formally, δ:Q×(Σ∪{ϵ})×Γ→P(Q×Γ∗).

Let's break down this complex definition:
○ The input to δ is a triple: (current state, input symbol (or ϵ), stack top symbol).
■ The input symbol can be an actual symbol from Σ or ϵ. An ϵ-transition means the PDA can make a move without reading any input symbol, only reacting to its current state and stack top. This is a source of non-determinism.
■ The stack top symbol γ∈Γ is read but not removed from the stack by the input part of the transition.
○ The output of δ is a finite set of pairs: (qnext ,γstring ).
■ qnext∈ Q is the next state the PDA transitions to.
■ γstring∈ Γ∗ is the string of symbols that replaces the top symbol on the stack.

A PDA processes an input string by reading one symbol at a time (or making an epsilon transition). At each step, its move depends on:
1. Its current state.
2. The input symbol it is currently reading (or if it makes an epsilon move).
3. The symbol currently on the top of its stack.
Based on these three pieces of information, the PDA makes a non-deterministic choice of what to do next:
1. Transition to a new state.
2. Modify the stack by popping the top symbol and then pushing zero or more new symbols onto the stack.

PDAs can be defined with two primary acceptance conditions. While seemingly different, they are equivalent in terms of the class of languages they recognize (i.e., Context-Free Languages).
1. Acceptance by Final State:
A PDA M=(Q,Σ,Γ,δ,q0 ,Z0 ,F) accepts an input string w∈Σ∗ if, starting from its initial state q0 with an initial stack symbol Z0 , and after reading the entire string w, the PDA can enter any state qf∈ F, regardless of the contents remaining on the stack.
2. Acceptance by Empty Stack:
A PDA M′=(Q′,Σ,Γ,δ′,q0′ ,Z0 ,∅) (note that F is empty, as final states are not used for this condition) accepts an input string w∈Σ∗ if, starting from its initial state q0′ with an initial stack symbol Z0 , and after reading the entire string w, the PDA can empty its stack, regardless of the state it ends up in.

For any language L, L can be accepted by a PDA by final state if and only if L can be accepted by some PDA by empty stack. This means that if a language is context-free, it can be recognized by a PDA using either acceptance criterion.
● Converting Final State Acceptance to Empty Stack Acceptance:
Given a PDA M=(Q,Σ,Γ,δ,q0 ,Z0 ,F) that accepts by final state, we can construct an equivalent PDA M′ that accepts by empty stack.