What is push down automata? Describe in brief.

Push down Automata (PDA): A push down automaton is a way to implement a context-free-grammar in a similar way we design DFA for a regular grammar.

Basically a push down automaton is –
“Finite state machine” + “a stack”
A push down automaton has three components -
an input tape
a control unit and
a stack with infinite size.
A stack has does two operations –
PUSH – a new symbol is added at the top.
POP – the top symbol is read and removed.
Formally, a push down automaton (PDA) is defined by –
P = (Q, Σ, Γ, δ, q_0, Z_0, F)
Where,
Q: A finite set of states.
Σ: A finite set of input symbols called input alphabet.
Γ: A finite set of stack symbols called stack alphabet.
δ: The transition function mapping from Q × (Σ ∪ {ϵ}) × Γ^* × Q to finite subset of Q × Γ^*
q₀: The initial state.
Z₀: The initial stack symbol.
F: A finite set of accepted states; F ⊆ Q.
A language can be accepted by PDA in two ways:
(i) Accepted by final state.
(ii) Accepted by empty stack.